llvm/lib/Transforms/Vectorize/SLPVectorizer/SLPMemoryUtils.h

//===- SLPMemoryUtils.h - SLP pointer/stride helpers -----------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// Internal header used by SLPVectorizer.cpp. It declares free pointer and
// stride helpers that do not depend on BoUpSLP or any other SLP-private type.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPMEMORYUTILS_H
#define LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPMEMORYUTILS_H

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Support/Alignment.h"

#include <cstdint>
#include <optional>
#include <tuple>

namespace llvm {
class AssumptionCache;
class BasicBlock;
class ConstantInt;
class DataLayout;
class DominatorTree;
class FixedVectorType;
class IRBuilderBase;
class SCEV;
class ScalarEvolution;
class TargetLibraryInfo;
class Type;
class Value;
class VectorType;
} // namespace llvm

namespace llvm::slpvectorizer {

/// Caches the results of the expensive analyses that are queried repeatedly
/// for the same values while the vectorization trees are built and their costs
/// are estimated. The results may change once the vectorized code is emitted
/// and the scalars are erased, so the cache is cleared after each successful
/// vectorizeTree().
class SLPAnalysisCache {
public:
  /// Cached llvm::getPointersDiff(), a miss may require SCEV analysis. The
  /// result for (\p PtrA, \p PtrB) also serves the query for the swapped
  /// pointers.
  std::optional<int64_t>
  getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB,
                  const DataLayout &DL, ScalarEvolution &SE,
                  bool StrictCheck = false, bool CheckType = true);

  /// Cached llvm::isGuaranteedNotToBePoison().
  bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC);

  void clear() {
    PtrsDiffCache.clear();
    NotPoisonCache.clear();
  }

private:
  using PtrsDiffKeyT = std::tuple<Type *, Value *, Type *, Value *, unsigned>;
  SmallDenseMap<PtrsDiffKeyT, std::optional<int64_t>, 16> PtrsDiffCache;
  SmallDenseMap<const Value *, bool, 16> NotPoisonCache;
};

/// \p MaxDepth is the recursion limit for getUnderlyingObject.
bool arePointersCompatible(Value *Ptr1, Value *Ptr2,
                           const TargetLibraryInfo &TLI, unsigned MaxDepth,
                           bool CompareOpcodes = true);

/// Returns \p Stride scaled by the allocation size of \p ScalarTy, negated if
/// \p IsReverse is set, or nullptr if \p Stride is not a constant.
ConstantInt *getStrideBytesIfConstant(Value *Stride, Type *ScalarTy,
                                      const DataLayout &DL,
                                      bool IsReverse = false);

/// Casts \p V between the widened strided access type and the entry vector
/// type \p DstTy.
Value *createWidenedStridedCast(IRBuilderBase &Builder, Value *V, Type *DstTy,
                                const DataLayout &DL);

/// Calculates minimal alignment as a common alignment.
template <typename T> Align computeCommonAlignment(ArrayRef<Value *> VL);

/// Checks if the provided list of pointers \p Pointers represents the strided
/// pointers for type ElemTy. If they are not, nullptr is returned.
/// Otherwise, SCEV* of the stride value is returned.
/// If `PointerOps` can be rearranged into the following sequence:
/// ```
/// %x + c_0 * stride,
/// %x + c_1 * stride,
/// %x + c_2 * stride
/// ...
/// ```
/// where each `c_i` is constant. The SCEV of the `stride` will be returned.
const SCEV *calculateRtStride(ArrayRef<Value *> PointerOps, Type *ElemTy,
                              const DataLayout &DL, ScalarEvolution &SE,
                              SmallVectorImpl<unsigned> &SortedIndices);

/// Checks if the \p VL can be transformed to a (masked)load + compress or
/// (masked) interleaved load.
bool isMaskedLoadCompress(
    ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
    ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
    const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
    const DominatorTree &DT, const TargetLibraryInfo &TLI,
    const TargetTransformInfo::TargetCostKind CostKind,
    const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
    bool &IsMasked, unsigned &InterleaveFactor,
    SmallVectorImpl<int> &CompressMask, VectorType *&LoadVecTy,
    SLPAnalysisCache &Cache);

/// Checks if the \p VL can be transformed to a (masked)load + compress or
/// (masked) interleaved load.
bool isMaskedLoadCompress(
    ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
    ArrayRef<unsigned> Order, const TargetTransformInfo &TTI,
    const DataLayout &DL, ScalarEvolution &SE, AssumptionCache &AC,
    const DominatorTree &DT, const TargetLibraryInfo &TLI,
    const TargetTransformInfo::TargetCostKind CostKind,
    const function_ref<bool(Value *)> AreAllUsersVectorized, bool ReVec,
    SLPAnalysisCache &Cache);

/// Checks if the simple loads of \p VL, mixed with the undef and poison lanes,
/// can be replaced by a single load of the whole \p VL width. The loads must be
/// consecutive and match their lanes, and the whole accessed range must be safe
/// to load unconditionally.
bool canWidenLoadsOverUndefLanes(ArrayRef<Value *> VL, const DataLayout &DL,
                                 ScalarEvolution &SE, AssumptionCache &AC,
                                 const DominatorTree &DT,
                                 const TargetLibraryInfo &TLI);

/// Returns the distance in bytes from the start of the vector load to the
/// first load of \p Scalars: the leading undef lanes are covered by the vector
/// load.
uint64_t getVectorLoadShift(ArrayRef<Value *> Scalars);

/// Checks if the stores \p VL with pointers \p PointerOps can be lowered as a
/// single masked store. On success \p StoreVecTy is the widened store type and
/// \p ReuseShuffleIndices is the expand mask that places each stored value at
/// its element offset from the base (poison in the gaps).
bool isMaskedStoreCompress(ArrayRef<Value *> VL, ArrayRef<Value *> PointerOps,
                           ArrayRef<unsigned> Order,
                           const TargetTransformInfo &TTI, const DataLayout &DL,
                           ScalarEvolution &SE, Align CommonAlignment,
                           SmallVectorImpl<int> &ReuseShuffleIndices,
                           FixedVectorType *&StoreVecTy,
                           SLPAnalysisCache &Cache);

/// Clusters \p VL pointers by (basic block, underlying object) pair and sorts
/// each cluster by offset. Returns false and leaves \p SortedIndices empty if
/// the accesses are not worth reordering.
bool clusterSortPtrAccesses(ArrayRef<Value *> VL, ArrayRef<BasicBlock *> BBs,
                            Type *ElemTy, const DataLayout &DL,
                            ScalarEvolution &SE, unsigned MaxDepth,
                            SmallVectorImpl<unsigned> &SortedIndices,
                            SLPAnalysisCache &Cache);

} // namespace llvm::slpvectorizer

#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPMEMORYUTILS_H