Author: Graham Hunter Date: 2024-07-11T16:14:47+01:00 New Revision: 2dae7c40fdd7233b6ac5d5a7513417c4f5d4f398
URL: https://github.com/llvm/llvm-project/commit/2dae7c40fdd7233b6ac5d5a7513417c4f5d4f398 DIFF: https://github.com/llvm/llvm-project/commit/2dae7c40fdd7233b6ac5d5a7513417c4f5d4f398.diff LOG: Revert "[LV] Autovectorization for the all-in-one histogram intrinsic (#91458)" This reverts commit 1860fd049e35055fccac14e439227fae803976b8. Added: Modified: llvm/include/llvm/Analysis/LoopAccessAnalysis.h llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h llvm/lib/Analysis/LoopAccessAnalysis.cpp llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp llvm/lib/Transforms/Vectorize/LoopVectorize.cpp llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h llvm/lib/Transforms/Vectorize/VPlan.h llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp llvm/lib/Transforms/Vectorize/VPlanValue.h Removed: llvm/test/Analysis/LoopAccessAnalysis/histogram.ll llvm/test/Transforms/LoopVectorize/AArch64/sve2-histcnt.ll ################################################################################ diff --git a/llvm/include/llvm/Analysis/LoopAccessAnalysis.h b/llvm/include/llvm/Analysis/LoopAccessAnalysis.h index 9cca70459edef..f6bb044392938 100644 --- a/llvm/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopAccessAnalysis.h @@ -144,9 +144,7 @@ class MemoryDepChecker { // on MinDepDistBytes. BackwardVectorizable, // Same, but may prevent store-to-load forwarding. - BackwardVectorizableButPreventsForwarding, - // Access is to a loop loaded value, but is part of a histogram operation. - Histogram + BackwardVectorizableButPreventsForwarding }; /// String version of the types. @@ -203,8 +201,7 @@ class MemoryDepChecker { /// Only checks sets with elements in \p CheckDeps. bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const DenseMap<Value *, SmallVector<const Value *, 16>> - &UnderlyingObjects, - const SmallPtrSetImpl<const Value *> &HistogramPtrs); + &UnderlyingObjects); /// No memory dependence was encountered that would inhibit /// vectorization. @@ -355,8 +352,7 @@ class MemoryDepChecker { isDependent(const MemAccessInfo &A, unsigned AIdx, const MemAccessInfo &B, unsigned BIdx, const DenseMap<Value *, SmallVector<const Value *, 16>> - &UnderlyingObjects, - const SmallPtrSetImpl<const Value *> &HistogramPtrs); + &UnderlyingObjects); /// Check whether the data dependence could prevent store-load /// forwarding. @@ -397,8 +393,7 @@ class MemoryDepChecker { const MemAccessInfo &A, Instruction *AInst, const MemAccessInfo &B, Instruction *BInst, const DenseMap<Value *, SmallVector<const Value *, 16>> - &UnderlyingObjects, - const SmallPtrSetImpl<const Value *> &HistogramPtrs); + &UnderlyingObjects); }; class RuntimePointerChecking; @@ -450,15 +445,6 @@ struct PointerDiffInfo { NeedsFreeze(NeedsFreeze) {} }; -struct HistogramInfo { - LoadInst *Load; - Instruction *Update; - StoreInst *Store; - - HistogramInfo(LoadInst *Load, Instruction *Update, StoreInst *Store) - : Load(Load), Update(Update), Store(Store) {} -}; - /// Holds information about the memory runtime legality checks to verify /// that a group of pointers do not overlap. class RuntimePointerChecking { @@ -639,13 +625,6 @@ class RuntimePointerChecking { /// Checks for both memory dependences and the SCEV predicates contained in the /// PSE must be emitted in order for the results of this analysis to be valid. class LoopAccessInfo { - /// Represents whether the memory access dependencies in the loop: - /// * Prohibit vectorization - /// * Allow for vectorization (possibly with runtime checks) - /// * Allow for vectorization (possibly with runtime checks), - /// as long as histogram operations are supported. - enum VecMemPossible { CantVec = 0, NormalVec = 1, HistogramVec = 2 }; - public: LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetTransformInfo *TTI, const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT, @@ -657,11 +636,7 @@ class LoopAccessInfo { /// hasStoreStoreDependenceInvolvingLoopInvariantAddress and /// hasLoadStoreDependenceInvolvingLoopInvariantAddress also need to be /// checked. - bool canVectorizeMemory() const { return CanVecMem == NormalVec; } - - bool canVectorizeMemoryWithHistogram() const { - return CanVecMem == NormalVec || CanVecMem == HistogramVec; - } + bool canVectorizeMemory() const { return CanVecMem; } /// Return true if there is a convergent operation in the loop. There may /// still be reported runtime pointer checks that would be required, but it is @@ -689,10 +664,6 @@ class LoopAccessInfo { unsigned getNumStores() const { return NumStores; } unsigned getNumLoads() const { return NumLoads;} - const SmallVectorImpl<HistogramInfo> &getHistograms() const { - return Histograms; - } - /// The diagnostics report generated for the analysis. E.g. why we /// couldn't analyze the loop. const OptimizationRemarkAnalysis *getReport() const { return Report.get(); } @@ -744,8 +715,8 @@ class LoopAccessInfo { private: /// Analyze the loop. Returns true if all memory access in the loop can be /// vectorized. - VecMemPossible analyzeLoop(AAResults *AA, LoopInfo *LI, - const TargetLibraryInfo *TLI, DominatorTree *DT); + bool analyzeLoop(AAResults *AA, LoopInfo *LI, const TargetLibraryInfo *TLI, + DominatorTree *DT); /// Check if the structure of the loop allows it to be analyzed by this /// pass. @@ -786,7 +757,7 @@ class LoopAccessInfo { unsigned NumStores = 0; /// Cache the result of analyzeLoop. - VecMemPossible CanVecMem = CantVec; + bool CanVecMem = false; bool HasConvergentOp = false; /// Indicator that there are two non vectorizable stores to the same uniform @@ -806,13 +777,6 @@ class LoopAccessInfo { /// If an access has a symbolic strides, this maps the pointer value to /// the stride symbol. DenseMap<Value *, const SCEV *> SymbolicStrides; - - /// Holds the load, update, and store instructions for all histogram-style - /// operations found in the loop. - SmallVector<HistogramInfo, 2> Histograms; - - /// Storing Histogram Pointers - SmallPtrSet<const Value *, 2> HistogramPtrs; }; /// Return the SCEV corresponding to a pointer with the symbolic stride diff --git a/llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h b/llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h index 4361e0f2cf038..2ff17bd2f7a71 100644 --- a/llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h +++ b/llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h @@ -390,23 +390,6 @@ class LoopVectorizationLegality { unsigned getNumStores() const { return LAI->getNumStores(); } unsigned getNumLoads() const { return LAI->getNumLoads(); } - std::optional<const HistogramInfo *> getHistogramInfo(Instruction *I) const { - for (const HistogramInfo &HGram : LAI->getHistograms()) - if (HGram.Load == I || HGram.Update == I || HGram.Store == I) - return &HGram; - - return std::nullopt; - } - - std::optional<const HistogramInfo *> - getHistogramForStore(StoreInst *SI) const { - for (const HistogramInfo &HGram : LAI->getHistograms()) - if (HGram.Store == SI) - return &HGram; - - return std::nullopt; - } - PredicatedScalarEvolution *getPredicatedScalarEvolution() const { return &PSE; } diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp index dd9827003d200..018861a665c4c 100644 --- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp +++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp @@ -21,7 +21,6 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/LoopAnalysisManager.h" @@ -71,8 +70,6 @@ using namespace llvm::PatternMatch; #define DEBUG_TYPE "loop-accesses" -STATISTIC(HistogramsDetected, "Number of Histograms detected"); - static cl::opt<unsigned, true> VectorizationFactor("force-vector-width", cl::Hidden, cl::desc("Sets the SIMD width. Zero is autoselect."), @@ -735,23 +732,6 @@ class AccessAnalysis { return UnderlyingObjects; } - /// Find Histogram counts that match high-level code in loops: - /// \code - /// buckets[indices[i]]+=step; - /// \endcode - /// - /// It matches a pattern starting from \p HSt, which Stores to the 'buckets' - /// array the computed histogram. It uses a BinOp to sum all counts, storing - /// them using a loop-variant index Load from the 'indices' input array. - /// - /// On successful matches it updates the STATISTIC 'HistogramsDetected', - /// regardless of hardware support. When there is support, it additionally - /// stores the BinOp/Load pairs in \p HistogramCounts, as well the pointers - /// used to update histogram in \p HistogramPtrs. - void findHistograms(StoreInst *HSt, Loop *TheLoop, - SmallVectorImpl<HistogramInfo> &Histograms, - SmallPtrSetImpl<const Value *> &HistogramPtrs); - private: typedef MapVector<MemAccessInfo, SmallSetVector<Type *, 1>> PtrAccessMap; @@ -1718,7 +1698,6 @@ MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) { case NoDep: case Forward: case BackwardVectorizable: - case Histogram: return VectorizationSafetyStatus::Safe; case Unknown: @@ -1739,7 +1718,6 @@ bool MemoryDepChecker::Dependence::isBackward() const { case ForwardButPreventsForwarding: case Unknown: case IndirectUnsafe: - case Histogram: return false; case BackwardVectorizable: @@ -1751,7 +1729,7 @@ bool MemoryDepChecker::Dependence::isBackward() const { } bool MemoryDepChecker::Dependence::isPossiblyBackward() const { - return isBackward() || Type == Unknown || Type == Histogram; + return isBackward() || Type == Unknown; } bool MemoryDepChecker::Dependence::isForward() const { @@ -1766,7 +1744,6 @@ bool MemoryDepChecker::Dependence::isForward() const { case Backward: case BackwardVectorizableButPreventsForwarding: case IndirectUnsafe: - case Histogram: return false; } llvm_unreachable("unexpected DepType!"); @@ -1936,8 +1913,8 @@ std::variant<MemoryDepChecker::Dependence::DepType, MemoryDepChecker::getDependenceDistanceStrideAndSize( const AccessAnalysis::MemAccessInfo &A, Instruction *AInst, const AccessAnalysis::MemAccessInfo &B, Instruction *BInst, - const DenseMap<Value *, SmallVector<const Value *, 16>> &UnderlyingObjects, - const SmallPtrSetImpl<const Value *> &HistogramPtrs) { + const DenseMap<Value *, SmallVector<const Value *, 16>> + &UnderlyingObjects) { auto &DL = InnermostLoop->getHeader()->getDataLayout(); auto &SE = *PSE.getSE(); auto [APtr, AIsWrite] = A; @@ -1955,12 +1932,6 @@ MemoryDepChecker::getDependenceDistanceStrideAndSize( BPtr->getType()->getPointerAddressSpace()) return MemoryDepChecker::Dependence::Unknown; - // Ignore Histogram count updates as they are handled by the Intrinsic. This - // happens when the same pointer is first used to read from and then is used - // to write to. - if (!AIsWrite && BIsWrite && APtr == BPtr && HistogramPtrs.contains(APtr)) - return MemoryDepChecker::Dependence::Histogram; - int64_t StrideAPtr = getPtrStride(PSE, ATy, APtr, InnermostLoop, SymbolicStrides, true) .value_or(0); @@ -2037,14 +2008,14 @@ MemoryDepChecker::getDependenceDistanceStrideAndSize( MemoryDepChecker::Dependence::DepType MemoryDepChecker::isDependent( const MemAccessInfo &A, unsigned AIdx, const MemAccessInfo &B, unsigned BIdx, - const DenseMap<Value *, SmallVector<const Value *, 16>> &UnderlyingObjects, - const SmallPtrSetImpl<const Value *> &HistogramPtrs) { + const DenseMap<Value *, SmallVector<const Value *, 16>> + &UnderlyingObjects) { assert(AIdx < BIdx && "Must pass arguments in program order"); // Get the dependence distance, stride, type size and what access writes for // the dependence between A and B. auto Res = getDependenceDistanceStrideAndSize( - A, InstMap[AIdx], B, InstMap[BIdx], UnderlyingObjects, HistogramPtrs); + A, InstMap[AIdx], B, InstMap[BIdx], UnderlyingObjects); if (std::holds_alternative<Dependence::DepType>(Res)) return std::get<Dependence::DepType>(Res); @@ -2280,8 +2251,8 @@ MemoryDepChecker::Dependence::DepType MemoryDepChecker::isDependent( bool MemoryDepChecker::areDepsSafe( DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, - const DenseMap<Value *, SmallVector<const Value *, 16>> &UnderlyingObjects, - const SmallPtrSetImpl<const Value *> &HistogramPtrs) { + const DenseMap<Value *, SmallVector<const Value *, 16>> + &UnderlyingObjects) { MinDepDistBytes = -1; SmallPtrSet<MemAccessInfo, 8> Visited; @@ -2324,9 +2295,8 @@ bool MemoryDepChecker::areDepsSafe( if (*I1 > *I2) std::swap(A, B); - Dependence::DepType Type = - isDependent(*A.first, A.second, *B.first, B.second, - UnderlyingObjects, HistogramPtrs); + Dependence::DepType Type = isDependent(*A.first, A.second, *B.first, + B.second, UnderlyingObjects); mergeInStatus(Dependence::isSafeForVectorization(Type)); // Gather dependences unless we accumulated MaxDependences @@ -2377,8 +2347,7 @@ const char *MemoryDepChecker::Dependence::DepName[] = { "ForwardButPreventsForwarding", "Backward", "BackwardVectorizable", - "BackwardVectorizableButPreventsForwarding", - "Histogram"}; + "BackwardVectorizableButPreventsForwarding"}; void MemoryDepChecker::Dependence::print( raw_ostream &OS, unsigned Depth, @@ -2426,9 +2395,9 @@ bool LoopAccessInfo::canAnalyzeLoop() { return true; } -LoopAccessInfo::VecMemPossible -LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, - const TargetLibraryInfo *TLI, DominatorTree *DT) { +bool LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, + const TargetLibraryInfo *TLI, + DominatorTree *DT) { // Holds the Load and Store instructions. SmallVector<LoadInst *, 16> Loads; SmallVector<StoreInst *, 16> Stores; @@ -2468,7 +2437,7 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, // With both a non-vectorizable memory instruction and a convergent // operation, found in this loop, no reason to continue the search. if (HasComplexMemInst && HasConvergentOp) - return CantVec; + return false; // Avoid hitting recordAnalysis multiple times. if (HasComplexMemInst) @@ -2544,7 +2513,7 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, } // Next block. if (HasComplexMemInst) - return CantVec; + return false; // Now we have two lists that hold the loads and the stores. // Next, we find the pointers that they use. @@ -2553,7 +2522,7 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, // care if the pointers are *restrict*. if (!Stores.size()) { LLVM_DEBUG(dbgs() << "LAA: Found a read-only loop!\n"); - return NormalVec; + return true; } MemoryDepChecker::DepCandidates DependentAccesses; @@ -2606,7 +2575,7 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, LLVM_DEBUG( dbgs() << "LAA: A loop annotated parallel, ignore memory dependency " << "checks.\n"); - return NormalVec; + return true; } for (LoadInst *LD : Loads) { @@ -2653,16 +2622,13 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, // other reads in this loop then is it safe to vectorize. if (NumReadWrites == 1 && NumReads == 0) { LLVM_DEBUG(dbgs() << "LAA: Found a write-only loop!\n"); - return NormalVec; + return true; } // Build dependence sets and check whether we need a runtime pointer bounds // check. Accesses.buildDependenceSets(); - for (StoreInst *ST : Stores) - Accesses.findHistograms(ST, TheLoop, Histograms, HistogramPtrs); - // Find pointers with computable bounds. We are going to use this information // to place a runtime bound check. Value *UncomputablePtr = nullptr; @@ -2675,7 +2641,7 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, << "cannot identify array bounds"; LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because we can't find " << "the array bounds.\n"); - return CantVec; + return false; } LLVM_DEBUG( @@ -2684,9 +2650,9 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, bool DepsAreSafe = true; if (Accesses.isDependencyCheckNeeded()) { LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n"); - DepsAreSafe = DepChecker->areDepsSafe( - DependentAccesses, Accesses.getDependenciesToCheck(), - Accesses.getUnderlyingObjects(), HistogramPtrs); + DepsAreSafe = DepChecker->areDepsSafe(DependentAccesses, + Accesses.getDependenciesToCheck(), + Accesses.getUnderlyingObjects()); if (!DepsAreSafe && DepChecker->shouldRetryWithRuntimeCheck()) { LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n"); @@ -2708,7 +2674,7 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, recordAnalysis("CantCheckMemDepsAtRunTime", I) << "cannot check memory dependencies at runtime"; LLVM_DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n"); - return CantVec; + return false; } DepsAreSafe = true; } @@ -2719,7 +2685,7 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, << "cannot add control dependency to convergent operation"; LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because a runtime check " "would be needed with a convergent operation\n"); - return CantVec; + return false; } if (DepsAreSafe) { @@ -2727,11 +2693,11 @@ LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI, dbgs() << "LAA: No unsafe dependent memory operations in loop. We" << (PtrRtChecking->Need ? "" : " don't") << " need runtime memory checks.\n"); - return Histograms.empty() ? NormalVec : HistogramVec; + return true; } emitUnsafeDependenceRemark(); - return CantVec; + return false; } void LoopAccessInfo::emitUnsafeDependenceRemark() { @@ -2791,9 +2757,6 @@ void LoopAccessInfo::emitUnsafeDependenceRemark() { case MemoryDepChecker::Dependence::Unknown: R << "\nUnknown data dependence."; break; - case MemoryDepChecker::Dependence::Histogram: - R << "\nHistogram data dependence."; - break; } if (Instruction *I = Dep.getSource(getDepChecker())) { @@ -3065,7 +3028,7 @@ LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE, } void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const { - if (CanVecMem != CantVec) { + if (CanVecMem) { OS.indent(Depth) << "Memory dependences are safe"; const MemoryDepChecker &DC = getDepChecker(); if (!DC.isSafeForAnyVectorWidth()) @@ -3138,79 +3101,6 @@ void LoopAccessInfoManager::clear() { LoopAccessInfoMap.erase(L); } -void AccessAnalysis::findHistograms( - StoreInst *HSt, Loop *TheLoop, SmallVectorImpl<HistogramInfo> &Histograms, - SmallPtrSetImpl<const Value *> &HistogramPtrs) { - - // Store value must come from a Binary Operation. - Instruction *HPtrInstr = nullptr; - BinaryOperator *HBinOp = nullptr; - if (!match(HSt, m_Store(m_BinOp(HBinOp), m_Instruction(HPtrInstr)))) - return; - - // BinOp must be an Add or a Sub modifying the bucket value by a - // loop invariant amount. - // FIXME: We assume the loop invariant term is on the RHS. - // Fine for an immediate/constant, but maybe not a generic value? - Value *HIncVal = nullptr; - if (!match(HBinOp, m_Add(m_Load(m_Specific(HPtrInstr)), m_Value(HIncVal))) && - !match(HBinOp, m_Sub(m_Load(m_Specific(HPtrInstr)), m_Value(HIncVal)))) - return; - - // Make sure the increment value is loop invariant. - if (!TheLoop->isLoopInvariant(HIncVal)) - return; - - // The address to store is calculated through a GEP Instruction. - // FIXME: Support GEPs with more operands. - GetElementPtrInst *HPtr = dyn_cast<GetElementPtrInst>(HPtrInstr); - if (!HPtr || HPtr->getNumOperands() > 2) - return; - - // Check that the index is calculated by loading from another array. Ignore - // any extensions. - // FIXME: Support indices from other sources that a linear load from memory? - Value *HIdx = HPtr->getOperand(1); - Instruction *IdxInst = nullptr; - if (!match(HIdx, m_ZExtOrSExtOrSelf(m_Instruction(IdxInst)))) - return; - - // Currently restricting this to linear addressing when loading indices. - LoadInst *VLoad = dyn_cast<LoadInst>(IdxInst); - Value *VPtrVal; - if (!VLoad || !match(VLoad, m_Load(m_Value(VPtrVal)))) - return; - - if (!isa<SCEVAddRecExpr>(PSE.getSCEV(VPtrVal))) - return; - - // Ensure we'll have the same mask by checking that all parts of the histogram - // (gather load, update, scatter store) are in the same block. - LoadInst *IndexedLoad = cast<LoadInst>(HBinOp->getOperand(0)); - BasicBlock *LdBB = IndexedLoad->getParent(); - if (LdBB != HBinOp->getParent() || LdBB != HSt->getParent()) - return; - - // A histogram pointer may only alias to itself, and must only have two uses, - // the load and the store. - // We may be able to relax these constraints later. - for (AliasSet &AS : AST) - if (AS.isMustAlias() || AS.isMayAlias()) - if ((is_contained(AS.getPointers(), HPtr) && AS.size() > 1) || - HPtr->getNumUses() != 2) - return; - - HistogramsDetected++; - - LLVM_DEBUG(dbgs() << "LAA: Found histogram for load: " << *IndexedLoad - << " and store: " << *HSt << "\n"); - - // Store the operations that make up the histogram. - Histograms.emplace_back(IndexedLoad, HBinOp, HSt); - // Store pointers used to write those counts in the computed histogram. - HistogramPtrs.insert(HPtr); -} - bool LoopAccessInfoManager::invalidate( Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv) { diff --git a/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp b/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp index e61c0352be3bd..489f12e689d31 100644 --- a/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp +++ b/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp @@ -199,7 +199,6 @@ class LoadEliminationForLoop { Instruction *Destination = Dep.getDestination(DepChecker); if (Dep.Type == MemoryDepChecker::Dependence::Unknown || - Dep.Type == MemoryDepChecker::Dependence::Histogram || Dep.Type == MemoryDepChecker::Dependence::IndirectUnsafe) { if (isa<LoadInst>(Source)) LoadsWithUnknownDepedence.insert(Source); diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp index bb32e1d38d33c..f54eebb2874ab 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp @@ -78,10 +78,6 @@ static cl::opt<LoopVectorizeHints::ScalableForceKind> "Scalable vectorization is available and favored when the " "cost is inconclusive."))); -static cl::opt<bool> EnableHistogramVectorization( - "enable-histogram-loop-vectorization", cl::init(false), cl::Hidden, - cl::desc("Enables autovectorization of some loops containing histograms")); - /// Maximum vectorization interleave count. static const unsigned MaxInterleaveFactor = 16; @@ -1069,9 +1065,7 @@ bool LoopVectorizationLegality::canVectorizeMemory() { } if (!LAI->canVectorizeMemory()) - if (!EnableHistogramVectorization || - !LAI->canVectorizeMemoryWithHistogram()) - return false; + return false; if (LAI->hasLoadStoreDependenceInvolvingLoopInvariantAddress()) { reportVectorizationFailure("We don't allow storing to uniform addresses", diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp index df36851965977..93ec64440439c 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -5168,11 +5168,6 @@ LoopVectorizationCostModel::selectInterleaveCount(ElementCount VF, if (!Legal->isSafeForAnyVectorWidth()) return 1; - if (!Legal->getLAI()->getHistograms().empty()) { - LLVM_DEBUG(dbgs() << "LV: Not interleaving histogram operations.\n"); - return 1; - } - auto BestKnownTC = getSmallBestKnownTC(*PSE.getSE(), TheLoop); const bool HasReductions = !Legal->getReductionVars().empty(); @@ -6777,33 +6772,8 @@ LoopVectorizationCostModel::getInstructionCost(Instruction *I, // We've proven all lanes safe to speculate, fall through. [[fallthrough]]; case Instruction::Add: - case Instruction::Sub: { - auto Info = Legal->getHistogramInfo(I); - if (Info && VF.isVector()) { - const HistogramInfo *HGram = Info.value(); - // Assume that a non-constant update value (or a constant != 1) requires - // a multiply, and add that into the cost. - InstructionCost MulCost = TTI::TCC_Free; - ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1)); - if (!RHS || RHS->getZExtValue() != 1) - MulCost = TTI.getArithmeticInstrCost(Instruction::Mul, VectorTy); - - // Find the cost of the histogram operation itself. - Type *PtrTy = VectorType::get(HGram->Load->getPointerOperandType(), VF); - Type *ScalarTy = I->getType(); - Type *MaskTy = VectorType::get(Type::getInt1Ty(I->getContext()), VF); - IntrinsicCostAttributes ICA(Intrinsic::experimental_vector_histogram_add, - Type::getVoidTy(I->getContext()), - {PtrTy, ScalarTy, MaskTy}); - - // Add the costs together with the add/sub operation. - return TTI.getIntrinsicInstrCost( - ICA, TargetTransformInfo::TCK_RecipThroughput) + - MulCost + TTI.getArithmeticInstrCost(I->getOpcode(), VectorTy); - } - [[fallthrough]]; - } case Instruction::FAdd: + case Instruction::Sub: case Instruction::FSub: case Instruction::Mul: case Instruction::FMul: @@ -8509,36 +8479,6 @@ VPWidenRecipe *VPRecipeBuilder::tryToWiden(Instruction *I, }; } -VPHistogramRecipe * -VPRecipeBuilder::tryToWidenHistogram(const HistogramInfo *HI, - ArrayRef<VPValue *> Operands) { - // FIXME: Support other operations. - unsigned Opcode = HI->Update->getOpcode(); - assert((Opcode == Instruction::Add || Opcode == Instruction::Sub) && - "Histogram update operation must be an Add or Sub"); - - SmallVector<VPValue *, 3> HGramOps; - // Bucket address. - HGramOps.push_back(Operands[1]); - // Increment value. - HGramOps.push_back(getVPValueOrAddLiveIn(HI->Update->getOperand(1), Plan)); - - // In case of predicated execution (due to tail-folding, or conditional - // execution, or both), pass the relevant mask. When there is no such mask, - // generate an all-true mask. - VPValue *Mask = nullptr; - if (Legal->isMaskRequired(HI->Store)) - Mask = getBlockInMask(HI->Store->getParent()); - else - Mask = Plan.getOrAddLiveIn( - ConstantInt::getTrue(IntegerType::getInt1Ty(HI->Load->getContext()))); - HGramOps.push_back(Mask); - - return new VPHistogramRecipe(Opcode, - make_range(HGramOps.begin(), HGramOps.end()), - HI->Store->getDebugLoc()); -} - void VPRecipeBuilder::fixHeaderPhis() { BasicBlock *OrigLatch = OrigLoop->getLoopLatch(); for (VPHeaderPHIRecipe *R : PhisToFix) { @@ -8656,10 +8596,6 @@ VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr, if (auto *CI = dyn_cast<CallInst>(Instr)) return tryToWidenCall(CI, Operands, Range); - if (StoreInst *SI = dyn_cast<StoreInst>(Instr)) - if (auto HistInfo = Legal->getHistogramForStore(SI)) - return tryToWidenHistogram(*HistInfo, Operands); - if (isa<LoadInst>(Instr) || isa<StoreInst>(Instr)) return tryToWidenMemory(Instr, Operands, Range); @@ -8919,11 +8855,6 @@ LoopVectorizationPlanner::tryToBuildVPlanWithVPRecipes(VFRange &Range) { Operands = {OpRange.begin(), OpRange.end()}; } - // If this is a load instruction or a binop associated with a histogram, - // leave it until the store instruction to emit a combined intrinsic. - if (Legal->getHistogramInfo(Instr) && !isa<StoreInst>(Instr)) - continue; - // Invariant stores inside loop will be deleted and a single store // with the final reduction value will be added to the exit block StoreInst *SI; diff --git a/llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h b/llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h index d8c9465576807..b4c7ab02f928f 100644 --- a/llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h +++ b/llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h @@ -102,13 +102,6 @@ class VPRecipeBuilder { VPWidenRecipe *tryToWiden(Instruction *I, ArrayRef<VPValue *> Operands, VPBasicBlock *VPBB); - /// Makes Histogram count operations safe for vectorization, by emitting a - /// llvm.experimental.vector.histogram.add intrinsic in place of the - /// Load + Add|Sub + Store operations that perform the histogram in the - /// original scalar loop. - VPHistogramRecipe *tryToWidenHistogram(const HistogramInfo *HI, - ArrayRef<VPValue *> Operands); - public: VPRecipeBuilder(VPlan &Plan, Loop *OrigLoop, const TargetLibraryInfo *TLI, LoopVectorizationLegality *Legal, diff --git a/llvm/lib/Transforms/Vectorize/VPlan.h b/llvm/lib/Transforms/Vectorize/VPlan.h index a7ecf27a1bf98..e3b78700e1018 100644 --- a/llvm/lib/Transforms/Vectorize/VPlan.h +++ b/llvm/lib/Transforms/Vectorize/VPlan.h @@ -936,7 +936,6 @@ class VPSingleDefRecipe : public VPRecipeBase, public VPValue { case VPRecipeBase::VPWidenLoadSC: case VPRecipeBase::VPWidenStoreEVLSC: case VPRecipeBase::VPWidenStoreSC: - case VPRecipeBase::VPHistogramSC: // TODO: Widened stores don't define a value, but widened loads do. Split // the recipes to be able to make widened loads VPSingleDefRecipes. return false; @@ -1573,35 +1572,6 @@ class VPWidenCallRecipe : public VPSingleDefRecipe { #endif }; -class VPHistogramRecipe : public VPRecipeBase { - unsigned Opcode; - -public: - template <typename IterT> - VPHistogramRecipe(unsigned Opcode, iterator_range<IterT> Operands, - DebugLoc DL = {}) - : VPRecipeBase(VPDef::VPHistogramSC, Operands, DL), Opcode(Opcode) {} - - ~VPHistogramRecipe() override = default; - - VPHistogramRecipe *clone() override { - llvm_unreachable("cloning not supported"); - } - - VP_CLASSOF_IMPL(VPDef::VPHistogramSC); - - // Produce a histogram operation with widened ingredients - void execute(VPTransformState &State) override; - - unsigned getOpcode() { return Opcode; } - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - /// Print the recipe - void print(raw_ostream &O, const Twine &Indent, - VPSlotTracker &SlotTracker) const override; -#endif -}; - /// A recipe for widening select instructions. struct VPWidenSelectRecipe : public VPSingleDefRecipe { template <typename IterT> diff --git a/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp b/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp index fd53fae61007c..53d91ee27b73f 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp @@ -21,7 +21,6 @@ #include "llvm/IR/IRBuilder.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" -#include "llvm/IR/Intrinsics.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" @@ -956,42 +955,6 @@ void VPWidenCallRecipe::print(raw_ostream &O, const Twine &Indent, O << ")"; } } -#endif - -void VPHistogramRecipe::execute(VPTransformState &State) { - assert(State.UF == 1 && "Tried interleaving histogram operation"); - State.setDebugLocFrom(getDebugLoc()); - IRBuilderBase &Builder = State.Builder; - Value *Address = State.get(getOperand(0), 0); - Value *IncVec = State.get(getOperand(1), 0); - Value *Mask = State.get(getOperand(2), 0); - - // Not sure how to make IncAmt stay scalar yet. For now just extract the - // first element and tidy up later. - // FIXME: Do we actually want this to be scalar? We just splat it in the - // backend anyway... - Value *IncAmt = Builder.CreateExtractElement(IncVec, Builder.getInt64(0)); - - // If this is a subtract, we want to invert the increment amount. We may - // add a separate intrinsic in future, but for now we'll try this. - if (Opcode == Instruction::Sub) - IncAmt = Builder.CreateNeg(IncAmt); - - State.Builder.CreateIntrinsic(Intrinsic::experimental_vector_histogram_add, - {Address->getType(), IncAmt->getType()}, - {Address, IncAmt, Mask}); -} - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -void VPHistogramRecipe::print(raw_ostream &O, const Twine &Indent, - VPSlotTracker &SlotTracker) const { - O << Indent << "WIDEN-HISTOGRAM buckets: "; - getOperand(0)->printAsOperand(O, SlotTracker); - O << ", inc: "; - getOperand(1)->printAsOperand(O, SlotTracker); - O << ", mask: "; - getOperand(2)->printAsOperand(O, SlotTracker); -} void VPWidenSelectRecipe::print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const { diff --git a/llvm/lib/Transforms/Vectorize/VPlanValue.h b/llvm/lib/Transforms/Vectorize/VPlanValue.h index a1faae7c95f55..fa6a65ff2f3ad 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanValue.h +++ b/llvm/lib/Transforms/Vectorize/VPlanValue.h @@ -357,7 +357,6 @@ class VPDef { VPWidenSC, VPWidenSelectSC, VPBlendSC, - VPHistogramSC, // START: Phi-like recipes. Need to be kept together. VPWidenPHISC, VPPredInstPHISC, diff --git a/llvm/test/Analysis/LoopAccessAnalysis/histogram.ll b/llvm/test/Analysis/LoopAccessAnalysis/histogram.ll deleted file mode 100644 index a3cb1b9afc18d..0000000000000 --- a/llvm/test/Analysis/LoopAccessAnalysis/histogram.ll +++ /dev/null @@ -1,40 +0,0 @@ -; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5 -; RUN: opt -disable-output -passes='print<access-info>' %s 2>&1 | FileCheck %s - - -define void @simple_histogram(ptr noalias %buckets, ptr readonly %indices, i64 %N) { -; CHECK-LABEL: 'simple_histogram' -; CHECK-NEXT: for.body: -; CHECK-NEXT: Memory dependences are safe -; CHECK-NEXT: Dependences: -; CHECK-NEXT: Histogram: -; CHECK-NEXT: %1 = load i32, ptr %arrayidx2, align 4 -> -; CHECK-NEXT: store i32 %inc, ptr %arrayidx2, align 4 -; CHECK-EMPTY: -; CHECK-NEXT: Run-time memory checks: -; CHECK-NEXT: Grouped accesses: -; CHECK-EMPTY: -; CHECK-NEXT: Non vectorizable stores to invariant address were not found in loop. -; CHECK-NEXT: SCEV assumptions: -; CHECK-EMPTY: -; CHECK-NEXT: Expressions re-written: -; -entry: - br label %for.body - -for.body: - %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] - %arrayidx = getelementptr inbounds i32, ptr %indices, i64 %iv - %0 = load i32, ptr %arrayidx, align 4 - %idxprom1 = zext i32 %0 to i64 - %arrayidx2 = getelementptr inbounds i32, ptr %buckets, i64 %idxprom1 - %1 = load i32, ptr %arrayidx2, align 4 - %inc = add nsw i32 %1, 1 - store i32 %inc, ptr %arrayidx2, align 4 - %iv.next = add nuw nsw i64 %iv, 1 - %exitcond = icmp eq i64 %iv.next, %N - br i1 %exitcond, label %for.exit, label %for.body - -for.exit: - ret void -} diff --git a/llvm/test/Transforms/LoopVectorize/AArch64/sve2-histcnt.ll b/llvm/test/Transforms/LoopVectorize/AArch64/sve2-histcnt.ll deleted file mode 100644 index a0dbe5494f24d..0000000000000 --- a/llvm/test/Transforms/LoopVectorize/AArch64/sve2-histcnt.ll +++ /dev/null @@ -1,367 +0,0 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 3 -; RUN: opt < %s -passes=loop-vectorize -force-vector-interleave=1 -enable-histogram-loop-vectorization -sve-gather-overhead=2 -sve-scatter-overhead=2 -S | FileCheck %s - -target triple = "aarch64-unknown-linux-gnu" - -;; Based on the following C code: -;; -;; void simple_histogram(int *buckets, unsigned *indices, int N) { -;; for (int i = 0; i < N; ++i) -;; buckets[indices[i]]++; -;; } - -define void @simple_histogram(ptr noalias %buckets, ptr readonly %indices, i64 %N) #0 { -; CHECK-LABEL: define void @simple_histogram( -; CHECK-SAME: ptr noalias [[BUCKETS:%.*]], ptr readonly [[INDICES:%.*]], i64 [[N:%.*]]) #[[ATTR0:[0-9]+]] { -; CHECK-NEXT: entry: -; CHECK-NEXT: [[TMP0:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[TMP0]], 4 -; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], [[TMP1]] -; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]] -; CHECK: vector.ph: -; CHECK-NEXT: [[TMP2:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], 4 -; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[N]], [[TMP3]] -; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[N_MOD_VF]] -; CHECK-NEXT: [[TMP4:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[TMP4]], 4 -; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] -; CHECK: vector.body: -; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] -; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[TMP6]] -; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[TMP7]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <vscale x 4 x i32>, ptr [[TMP8]], align 4 -; CHECK-NEXT: [[TMP9:%.*]] = zext <vscale x 4 x i32> [[WIDE_LOAD]] to <vscale x 4 x i64> -; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[BUCKETS]], <vscale x 4 x i64> [[TMP9]] -; CHECK-NEXT: call void @llvm.experimental.vector.histogram.add.nxv4p0.i32(<vscale x 4 x ptr> [[TMP10]], i32 1, <vscale x 4 x i1> shufflevector (<vscale x 4 x i1> insertelement (<vscale x 4 x i1> poison, i1 true, i64 0), <vscale x 4 x i1> poison, <vscale x 4 x i32> zeroinitializer)) -; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], [[TMP5]] -; CHECK-NEXT: [[TMP11:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP11]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]] -; CHECK: middle.block: -; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]] -; CHECK-NEXT: br i1 [[CMP_N]], label [[FOR_EXIT:%.*]], label [[SCALAR_PH]] -; CHECK: scalar.ph: -; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ] -; CHECK-NEXT: br label [[FOR_BODY:%.*]] -; CHECK: for.body: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[FOR_BODY]] ] -; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[IV]] -; CHECK-NEXT: [[TMP12:%.*]] = load i32, ptr [[ARRAYIDX]], align 4 -; CHECK-NEXT: [[IDXPROM1:%.*]] = zext i32 [[TMP12]] to i64 -; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[BUCKETS]], i64 [[IDXPROM1]] -; CHECK-NEXT: [[TMP13:%.*]] = load i32, ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[INC:%.*]] = add nsw i32 [[TMP13]], 1 -; CHECK-NEXT: store i32 [[INC]], ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT]], label [[FOR_BODY]], !llvm.loop [[LOOP3:![0-9]+]] -; CHECK: for.exit: -; CHECK-NEXT: ret void -; -entry: - br label %for.body - -for.body: - %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] - %arrayidx = getelementptr inbounds i32, ptr %indices, i64 %iv - %0 = load i32, ptr %arrayidx, align 4 - %idxprom1 = zext i32 %0 to i64 - %arrayidx2 = getelementptr inbounds i32, ptr %buckets, i64 %idxprom1 - %1 = load i32, ptr %arrayidx2, align 4 - %inc = add nsw i32 %1, 1 - store i32 %inc, ptr %arrayidx2, align 4 - %iv.next = add nuw nsw i64 %iv, 1 - %exitcond = icmp eq i64 %iv.next, %N - br i1 %exitcond, label %for.exit, label %for.body - -for.exit: - ret void -} - -define void @simple_histogram_sub(ptr noalias %buckets, ptr readonly %indices, i64 %N) #0 { -; CHECK-LABEL: define void @simple_histogram_sub( -; CHECK-SAME: ptr noalias [[BUCKETS:%.*]], ptr readonly [[INDICES:%.*]], i64 [[N:%.*]]) #[[ATTR0]] { -; CHECK-NEXT: entry: -; CHECK-NEXT: [[TMP0:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP1:%.*]] = mul i64 [[TMP0]], 4 -; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], [[TMP1]] -; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]] -; CHECK: vector.ph: -; CHECK-NEXT: [[TMP2:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], 4 -; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[N]], [[TMP3]] -; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[N_MOD_VF]] -; CHECK-NEXT: [[TMP4:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[TMP4]], 4 -; CHECK-NEXT: br label [[VECTOR_BODY:%.*]] -; CHECK: vector.body: -; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ] -; CHECK-NEXT: [[TMP6:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[TMP7:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[TMP6]] -; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[TMP7]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <vscale x 4 x i32>, ptr [[TMP8]], align 4 -; CHECK-NEXT: [[TMP9:%.*]] = zext <vscale x 4 x i32> [[WIDE_LOAD]] to <vscale x 4 x i64> -; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[BUCKETS]], <vscale x 4 x i64> [[TMP9]] -; CHECK-NEXT: call void @llvm.experimental.vector.histogram.add.nxv4p0.i32(<vscale x 4 x ptr> [[TMP10]], i32 -1, <vscale x 4 x i1> shufflevector (<vscale x 4 x i1> insertelement (<vscale x 4 x i1> poison, i1 true, i64 0), <vscale x 4 x i1> poison, <vscale x 4 x i32> zeroinitializer)) -; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], [[TMP5]] -; CHECK-NEXT: [[TMP11:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP11]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]] -; CHECK: middle.block: -; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]] -; CHECK-NEXT: br i1 [[CMP_N]], label [[FOR_EXIT:%.*]], label [[SCALAR_PH]] -; CHECK: scalar.ph: -; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ] -; CHECK-NEXT: br label [[FOR_BODY:%.*]] -; CHECK: for.body: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[FOR_BODY]] ] -; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[IV]] -; CHECK-NEXT: [[TMP12:%.*]] = load i32, ptr [[ARRAYIDX]], align 4 -; CHECK-NEXT: [[IDXPROM1:%.*]] = zext i32 [[TMP12]] to i64 -; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[BUCKETS]], i64 [[IDXPROM1]] -; CHECK-NEXT: [[TMP13:%.*]] = load i32, ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[INC:%.*]] = sub nsw i32 [[TMP13]], 1 -; CHECK-NEXT: store i32 [[INC]], ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT]], label [[FOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]] -; CHECK: for.exit: -; CHECK-NEXT: ret void -; -entry: - br label %for.body - -for.body: - %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] - %arrayidx = getelementptr inbounds i32, ptr %indices, i64 %iv - %0 = load i32, ptr %arrayidx, align 4 - %idxprom1 = zext i32 %0 to i64 - %arrayidx2 = getelementptr inbounds i32, ptr %buckets, i64 %idxprom1 - %1 = load i32, ptr %arrayidx2, align 4 - %inc = sub nsw i32 %1, 1 - store i32 %inc, ptr %arrayidx2, align 4 - %iv.next = add nuw nsw i64 %iv, 1 - %exitcond = icmp eq i64 %iv.next, %N - br i1 %exitcond, label %for.exit, label %for.body - -for.exit: - ret void -} - -define void @conditional_histogram(ptr noalias %buckets, ptr readonly %indices, ptr readonly %conds, i64 %N) #0 { -; CHECK-LABEL: define void @conditional_histogram( -; CHECK-SAME: ptr noalias [[BUCKETS:%.*]], ptr readonly [[INDICES:%.*]], ptr readonly [[CONDS:%.*]], i64 [[N:%.*]]) #[[ATTR0]] { -; CHECK-NEXT: entry: -; CHECK-NEXT: [[TMP6:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP7:%.*]] = mul i64 [[TMP6]], 4 -; CHECK-NEXT: [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[N]], [[TMP7]] -; CHECK-NEXT: br i1 [[MIN_ITERS_CHECK]], label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]] -; CHECK: vector.ph: -; CHECK-NEXT: [[TMP2:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP3:%.*]] = mul i64 [[TMP2]], 4 -; CHECK-NEXT: [[N_MOD_VF:%.*]] = urem i64 [[N]], [[TMP3]] -; CHECK-NEXT: [[N_VEC:%.*]] = sub i64 [[N]], [[N_MOD_VF]] -; CHECK-NEXT: [[TMP4:%.*]] = call i64 @llvm.vscale.i64() -; CHECK-NEXT: [[TMP5:%.*]] = mul i64 [[TMP4]], 4 -; CHECK-NEXT: br label [[FOR_BODY:%.*]] -; CHECK: vector.body: -; CHECK-NEXT: [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[FOR_BODY]] ] -; CHECK-NEXT: [[IV:%.*]] = add i64 [[INDEX]], 0 -; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[IV]] -; CHECK-NEXT: [[TMP8:%.*]] = getelementptr inbounds i32, ptr [[ARRAYIDX]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD:%.*]] = load <vscale x 4 x i32>, ptr [[TMP8]], align 4 -; CHECK-NEXT: [[TMP9:%.*]] = zext <vscale x 4 x i32> [[WIDE_LOAD]] to <vscale x 4 x i64> -; CHECK-NEXT: [[TMP10:%.*]] = getelementptr inbounds i32, ptr [[BUCKETS]], <vscale x 4 x i64> [[TMP9]] -; CHECK-NEXT: [[TMP11:%.*]] = getelementptr inbounds i32, ptr [[CONDS]], i64 [[IV]] -; CHECK-NEXT: [[TMP12:%.*]] = getelementptr inbounds i32, ptr [[TMP11]], i32 0 -; CHECK-NEXT: [[WIDE_LOAD1:%.*]] = load <vscale x 4 x i32>, ptr [[TMP12]], align 4 -; CHECK-NEXT: [[TMP13:%.*]] = icmp sgt <vscale x 4 x i32> [[WIDE_LOAD1]], shufflevector (<vscale x 4 x i32> insertelement (<vscale x 4 x i32> poison, i32 5100, i64 0), <vscale x 4 x i32> poison, <vscale x 4 x i32> zeroinitializer) -; CHECK-NEXT: call void @llvm.experimental.vector.histogram.add.nxv4p0.i32(<vscale x 4 x ptr> [[TMP10]], i32 1, <vscale x 4 x i1> [[TMP13]]) -; CHECK-NEXT: [[INDEX_NEXT]] = add nuw i64 [[INDEX]], [[TMP5]] -; CHECK-NEXT: [[TMP14:%.*]] = icmp eq i64 [[INDEX_NEXT]], [[N_VEC]] -; CHECK-NEXT: br i1 [[TMP14]], label [[MIDDLE_BLOCK:%.*]], label [[FOR_BODY]], !llvm.loop [[LOOP6:![0-9]+]] -; CHECK: middle.block: -; CHECK-NEXT: [[CMP_N:%.*]] = icmp eq i64 [[N]], [[N_VEC]] -; CHECK-NEXT: br i1 [[CMP_N]], label [[FOR_EXIT:%.*]], label [[SCALAR_PH]] -; CHECK: scalar.ph: -; CHECK-NEXT: [[BC_RESUME_VAL:%.*]] = phi i64 [ [[N_VEC]], [[MIDDLE_BLOCK]] ], [ 0, [[ENTRY:%.*]] ] -; CHECK-NEXT: br label [[FOR_BODY1:%.*]] -; CHECK: for.body: -; CHECK-NEXT: [[IV1:%.*]] = phi i64 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[IV_NEXT:%.*]], [[NEXT:%.*]] ] -; CHECK-NEXT: [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[IV1]] -; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX1]], align 4 -; CHECK-NEXT: [[IDXPROM1:%.*]] = zext i32 [[TMP0]] to i64 -; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[BUCKETS]], i64 [[IDXPROM1]] -; CHECK-NEXT: [[CONDIDX:%.*]] = getelementptr inbounds i32, ptr [[CONDS]], i64 [[IV1]] -; CHECK-NEXT: [[CONDDATA:%.*]] = load i32, ptr [[CONDIDX]], align 4 -; CHECK-NEXT: [[IFCOND:%.*]] = icmp sgt i32 [[CONDDATA]], 5100 -; CHECK-NEXT: br i1 [[IFCOND]], label [[IFTRUE:%.*]], label [[NEXT]] -; CHECK: iftrue: -; CHECK-NEXT: [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[INC:%.*]] = add nsw i32 [[TMP1]], 1 -; CHECK-NEXT: store i32 [[INC]], ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: br label [[NEXT]] -; CHECK: next: -; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV1]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT]], label [[FOR_BODY1]], !llvm.loop [[LOOP7:![0-9]+]] -; CHECK: for.exit: -; CHECK-NEXT: ret void -; -entry: - br label %for.body - -for.body: - %iv = phi i64 [ 0, %entry ], [ %iv.next, %next ] - %arrayidx = getelementptr inbounds i32, ptr %indices, i64 %iv - %0 = load i32, ptr %arrayidx, align 4 - %idxprom1 = zext i32 %0 to i64 - %arrayidx2 = getelementptr inbounds i32, ptr %buckets, i64 %idxprom1 - %condidx = getelementptr inbounds i32, ptr %conds, i64 %iv - %conddata = load i32, ptr %condidx, align 4 - %ifcond = icmp sgt i32 %conddata, 5100 - br i1 %ifcond, label %iftrue, label %next - -iftrue: - %1 = load i32, ptr %arrayidx2, align 4 - %inc = add nsw i32 %1, 1 - store i32 %inc, ptr %arrayidx2, align 4 - br label %next - -next: - %iv.next = add nuw nsw i64 %iv, 1 - %exitcond = icmp eq i64 %iv.next, %N - br i1 %exitcond, label %for.exit, label %for.body - -for.exit: - ret void -} - -;; Need to support legalization of smaller int types. -define void @histogram_8bit(ptr noalias %buckets, ptr readonly %indices, i64 %N) #0 { -; CHECK-LABEL: define void @histogram_8bit( -; CHECK-SAME: ptr noalias [[BUCKETS:%.*]], ptr readonly [[INDICES:%.*]], i64 [[N:%.*]]) #[[ATTR0]] { -; CHECK-NEXT: entry: -; CHECK-NEXT: br label [[FOR_BODY:%.*]] -; CHECK: for.body: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[FOR_BODY]] ] -; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[IV]] -; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4 -; CHECK-NEXT: [[IDXPROM1:%.*]] = zext i32 [[TMP0]] to i64 -; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i8, ptr [[BUCKETS]], i64 [[IDXPROM1]] -; CHECK-NEXT: [[TMP1:%.*]] = load i8, ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[INC:%.*]] = add nsw i8 [[TMP1]], 1 -; CHECK-NEXT: store i8 [[INC]], ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT:%.*]], label [[FOR_BODY]] -; CHECK: for.exit: -; CHECK-NEXT: ret void -; -entry: - br label %for.body - -for.body: - %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] - %arrayidx = getelementptr inbounds i32, ptr %indices, i64 %iv - %0 = load i32, ptr %arrayidx, align 4 - %idxprom1 = zext i32 %0 to i64 - %arrayidx2 = getelementptr inbounds i8, ptr %buckets, i64 %idxprom1 - %1 = load i8, ptr %arrayidx2, align 4 - %inc = add nsw i8 %1, 1 - store i8 %inc, ptr %arrayidx2, align 4 - %iv.next = add nuw nsw i64 %iv, 1 - %exitcond = icmp eq i64 %iv.next, %N - br i1 %exitcond, label %for.exit, label %for.body - -for.exit: - ret void -} - -;; We don't currently support floating point histograms. -define void @histogram_float(ptr noalias %buckets, ptr readonly %indices, i64 %N) #0 { -; CHECK-LABEL: define void @histogram_float( -; CHECK-SAME: ptr noalias [[BUCKETS:%.*]], ptr readonly [[INDICES:%.*]], i64 [[N:%.*]]) #[[ATTR0]] { -; CHECK-NEXT: entry: -; CHECK-NEXT: br label [[FOR_BODY:%.*]] -; CHECK: for.body: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[FOR_BODY]] ] -; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[IV]] -; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4 -; CHECK-NEXT: [[IDXPROM1:%.*]] = zext i32 [[TMP0]] to i64 -; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds float, ptr [[BUCKETS]], i64 [[IDXPROM1]] -; CHECK-NEXT: [[TMP1:%.*]] = load float, ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[INC:%.*]] = fadd fast float [[TMP1]], 1.000000e+00 -; CHECK-NEXT: store float [[INC]], ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT:%.*]], label [[FOR_BODY]] -; CHECK: for.exit: -; CHECK-NEXT: ret void -; -entry: - br label %for.body - -for.body: - %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] - %arrayidx = getelementptr inbounds i32, ptr %indices, i64 %iv - %0 = load i32, ptr %arrayidx, align 4 - %idxprom1 = zext i32 %0 to i64 - %arrayidx2 = getelementptr inbounds float, ptr %buckets, i64 %idxprom1 - %1 = load float, ptr %arrayidx2, align 4 - %inc = fadd fast float %1, 1.0 - store float %inc, ptr %arrayidx2, align 4 - %iv.next = add nuw nsw i64 %iv, 1 - %exitcond = icmp eq i64 %iv.next, %N - br i1 %exitcond, label %for.exit, label %for.body - -for.exit: - ret void -} - -;; We don't support histograms with a update value that's not loop-invariant. -define void @histogram_varying_increment(ptr noalias %buckets, ptr readonly %indices, ptr readonly %incvals, i64 %N) #0 { -; CHECK-LABEL: define void @histogram_varying_increment( -; CHECK-SAME: ptr noalias [[BUCKETS:%.*]], ptr readonly [[INDICES:%.*]], ptr readonly [[INCVALS:%.*]], i64 [[N:%.*]]) #[[ATTR0]] { -; CHECK-NEXT: entry: -; CHECK-NEXT: br label [[FOR_BODY:%.*]] -; CHECK: for.body: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[FOR_BODY]] ] -; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[INDICES]], i64 [[IV]] -; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[ARRAYIDX]], align 4 -; CHECK-NEXT: [[IDXPROM1:%.*]] = zext i32 [[TMP0]] to i64 -; CHECK-NEXT: [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, ptr [[BUCKETS]], i64 [[IDXPROM1]] -; CHECK-NEXT: [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[INCIDX:%.*]] = getelementptr inbounds i32, ptr [[INCVALS]], i64 [[IV]] -; CHECK-NEXT: [[INCVAL:%.*]] = load i32, ptr [[INCIDX]], align 4 -; CHECK-NEXT: [[INC:%.*]] = add nsw i32 [[TMP1]], [[INCVAL]] -; CHECK-NEXT: store i32 [[INC]], ptr [[ARRAYIDX2]], align 4 -; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 -; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[IV_NEXT]], [[N]] -; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_EXIT:%.*]], label [[FOR_BODY]] -; CHECK: for.exit: -; CHECK-NEXT: ret void -; -entry: - br label %for.body - -for.body: - %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ] - %arrayidx = getelementptr inbounds i32, ptr %indices, i64 %iv - %0 = load i32, ptr %arrayidx, align 4 - %idxprom1 = zext i32 %0 to i64 - %arrayidx2 = getelementptr inbounds i32, ptr %buckets, i64 %idxprom1 - %1 = load i32, ptr %arrayidx2, align 4 - %incidx = getelementptr inbounds i32, ptr %incvals, i64 %iv - %incval = load i32, ptr %incidx, align 4 - %inc = add nsw i32 %1, %incval - store i32 %inc, ptr %arrayidx2, align 4 - %iv.next = add nuw nsw i64 %iv, 1 - %exitcond = icmp eq i64 %iv.next, %N - br i1 %exitcond, label %for.exit, label %for.body - -for.exit: - ret void -} - -attributes #0 = { "target-features"="+sve2" vscale_range(1,16) } _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
