Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/Analysis/LoopCacheAnalysis.h ------------------------*- 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

//

//===----------------------------------------------------------------------===//

///

/// \file

/// This file defines the interface for the loop cache analysis.

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_LOOPCACHEANALYSIS_H

#define LLVM_ANALYSIS_LOOPCACHEANALYSIS_H

#include "llvm/Analysis/LoopAnalysisManager.h"

#include "llvm/IR/PassManager.h"

#include <optional>

namespace llvm {

class AAResults;

class DependenceInfo;

class Instruction;

class LPMUpdater;

class raw_ostream;

class LoopInfo;

class Loop;

class ScalarEvolution;

class SCEV;

class TargetTransformInfo;

using CacheCostTy = int64_t;

using LoopVectorTy = SmallVector<Loop *, 8>;

/// Represents a memory reference as a base pointer and a set of indexing

/// operations. For example given the array reference A[i][2j+1][3k+2] in a

/// 3-dim loop nest:

///   for(i=0;i<n;++i)

///     for(j=0;j<m;++j)

///       for(k=0;k<o;++k)

///         ... A[i][2j+1][3k+2] ...

/// We expect:

///   BasePointer -> A

///   Subscripts -> [{0,+,1}<%for.i>][{1,+,2}<%for.j>][{2,+,3}<%for.k>]

///   Sizes -> [m][o][4]

class IndexedReference {

  friend raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R);

public:

  /// Construct an indexed reference given a \p StoreOrLoadInst instruction.

  IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI,

                   ScalarEvolution &SE);

  bool isValid() const { return IsValid; }

  const SCEV *getBasePointer() const { return BasePointer; }

  size_t getNumSubscripts() const { return Subscripts.size(); }

  const SCEV *getSubscript(unsigned SubNum) const {

    assert(SubNum < getNumSubscripts() && "Invalid subscript number");

    return Subscripts[SubNum];

  }

  const SCEV *getFirstSubscript() const {

    assert(!Subscripts.empty() && "Expecting non-empty container");

    return Subscripts.front();

  }

  const SCEV *getLastSubscript() const {

    assert(!Subscripts.empty() && "Expecting non-empty container");

    return Subscripts.back();

  }

  /// Return true/false if the current object and the indexed reference \p Other

  /// are/aren't in the same cache line of size \p CLS. Two references are in

  /// the same chace line iff the distance between them in the innermost

  /// dimension is less than the cache line size. Return std::nullopt if unsure.

  std::optional<bool> hasSpacialReuse(const IndexedReference &Other,

                                      unsigned CLS, AAResults &AA) const;

  /// Return true if the current object and the indexed reference \p Other

  /// have distance smaller than \p MaxDistance in the dimension associated with

  /// the given loop \p L. Return false if the distance is not smaller than \p

  /// MaxDistance and std::nullopt if unsure.

  std::optional<bool> hasTemporalReuse(const IndexedReference &Other,

                                       unsigned MaxDistance, const Loop &L,

                                       DependenceInfo &DI, AAResults &AA) const;

  /// Compute the cost of the reference w.r.t. the given loop \p L when it is

  /// considered in the innermost position in the loop nest.

  /// The cost is defined as:

  ///   - equal to one if the reference is loop invariant, or

  ///   - equal to '(TripCount * stride) / cache_line_size' if:

  ///     + the reference stride is less than the cache line size, and

  ///     + the coefficient of this loop's index variable used in all other

  ///       subscripts is zero

  ///   - or otherwise equal to 'TripCount'.

  CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const;

private:

  /// Attempt to delinearize the indexed reference.

  bool delinearize(const LoopInfo &LI);

  /// Attempt to delinearize \p AccessFn for fixed-size arrays.

  bool tryDelinearizeFixedSize(const SCEV *AccessFn,

                               SmallVectorImpl<const SCEV *> &Subscripts);

  /// Return true if the index reference is invariant with respect to loop \p L.

  bool isLoopInvariant(const Loop &L) const;

  /// Return true if the indexed reference is 'consecutive' in loop \p L.

  /// An indexed reference is 'consecutive' if the only coefficient that uses

  /// the loop induction variable is the rightmost one, and the access stride is

  /// smaller than the cache line size \p CLS. Provide a valid \p Stride value

  /// if the indexed reference is 'consecutive'.

  bool isConsecutive(const Loop &L, const SCEV *&Stride, unsigned CLS) const;

  /// Retrieve the index of the subscript corresponding to the given loop \p

  /// L. Return a zero-based positive index if the subscript index is

  /// succesfully located and a negative value otherwise. For example given the

  /// indexed reference 'A[i][2j+1][3k+2]', the call

  /// 'getSubscriptIndex(loop-k)' would return value 2.

  int getSubscriptIndex(const Loop &L) const;

  /// Return the coefficient used in the rightmost dimension.

  const SCEV *getLastCoefficient() const;

  /// Return true if the coefficient corresponding to induction variable of

  /// loop \p L in the given \p Subscript is zero or is loop invariant in \p L.

  bool isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,

                                     const Loop &L) const;

  /// Verify that the given \p Subscript is 'well formed' (must be a simple add

  /// recurrence).

  bool isSimpleAddRecurrence(const SCEV &Subscript, const Loop &L) const;

  /// Return true if the given reference \p Other is definetely aliased with

  /// the indexed reference represented by this class.

  bool isAliased(const IndexedReference &Other, AAResults &AA) const;

private:

  /// True if the reference can be delinearized, false otherwise.

  bool IsValid = false;

  /// Represent the memory reference instruction.

  Instruction &StoreOrLoadInst;

  /// The base pointer of the memory reference.

  const SCEV *BasePointer = nullptr;

  /// The subscript (indexes) of the memory reference.

  SmallVector<const SCEV *, 3> Subscripts;

  /// The dimensions of the memory reference.

  SmallVector<const SCEV *, 3> Sizes;

  ScalarEvolution &SE;

};

/// A reference group represents a set of memory references that exhibit

/// temporal or spacial reuse. Two references belong to the same

/// reference group with respect to a inner loop L iff:

/// 1. they have a loop independent dependency, or

/// 2. they have a loop carried dependence with a small dependence distance

///    (e.g. less than 2) carried by the inner loop, or

/// 3. they refer to the same array, and the subscript in their innermost

///    dimension is less than or equal to 'd' (where 'd' is less than the cache

///    line size)

///

/// Intuitively a reference group represents memory references that access

/// the same cache line. Conditions 1,2 above account for temporal reuse, while

/// contition 3 accounts for spacial reuse.

using ReferenceGroupTy = SmallVector<std::unique_ptr<IndexedReference>, 8>;

using ReferenceGroupsTy = SmallVector<ReferenceGroupTy, 8>;

/// \c CacheCost represents the estimated cost of a inner loop as the number of

/// cache lines used by the memory references it contains.

/// The 'cache cost' of a loop 'L' in a loop nest 'LN' is computed as the sum of

/// the cache costs of all of its reference groups when the loop is considered

/// to be in the innermost position in the nest.

/// A reference group represents memory references that fall into the same cache

/// line. Each reference group is analysed with respect to the innermost loop in

/// a loop nest. The cost of a reference is defined as follow:

///  - one if it is loop invariant w.r.t the innermost loop,

///  - equal to the loop trip count divided by the cache line times the

///    reference stride if the reference stride is less than the cache line

///    size (CLS), and the coefficient of this loop's index variable used in all

///    other subscripts is zero (e.g. RefCost = TripCount/(CLS/RefStride))

///  - equal to the innermost loop trip count if the reference stride is greater

///    or equal to the cache line size CLS.

class CacheCost {

  friend raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC);

  using LoopTripCountTy = std::pair<const Loop *, unsigned>;

  using LoopCacheCostTy = std::pair<const Loop *, CacheCostTy>;

public:

  static CacheCostTy constexpr InvalidCost = -1;

  /// Construct a CacheCost object for the loop nest described by \p Loops.

  /// The optional parameter \p TRT can be used to specify the max. distance

  /// between array elements accessed in a loop so that the elements are

  /// classified to have temporal reuse.

  CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE,

            TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI,

            std::optional<unsigned> TRT = std::nullopt);

  /// Create a CacheCost for the loop nest rooted by \p Root.

  /// The optional parameter \p TRT can be used to specify the max. distance

  /// between array elements accessed in a loop so that the elements are

  /// classified to have temporal reuse.

  static std::unique_ptr<CacheCost>

  getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI,

               std::optional<unsigned> TRT = std::nullopt);

  /// Return the estimated cost of loop \p L if the given loop is part of the

  /// loop nest associated with this object. Return -1 otherwise.

  CacheCostTy getLoopCost(const Loop &L) const {

    auto IT = llvm::find_if(LoopCosts, [&L](const LoopCacheCostTy &LCC) {

      return LCC.first == &L;

    });

    return (IT != LoopCosts.end()) ? (*IT).second : -1;

  }

  /// Return the estimated ordered loop costs.

  ArrayRef<LoopCacheCostTy> getLoopCosts() const { return LoopCosts; }

private:

  /// Calculate the cache footprint of each loop in the nest (when it is

  /// considered to be in the innermost position).

  void calculateCacheFootprint();

  /// Partition store/load instructions in the loop nest into reference groups.

  /// Two or more memory accesses belong in the same reference group if they

  /// share the same cache line.

  bool populateReferenceGroups(ReferenceGroupsTy &RefGroups) const;

  /// Calculate the cost of the given loop \p L assuming it is the innermost

  /// loop in nest.

  CacheCostTy computeLoopCacheCost(const Loop &L,

                                   const ReferenceGroupsTy &RefGroups) const;

  /// Compute the cost of a representative reference in reference group \p RG

  /// when the given loop \p L is considered as the innermost loop in the nest.

  /// The computed cost is an estimate for the number of cache lines used by the

  /// reference group. The representative reference cost is defined as:

  ///   - equal to one if the reference is loop invariant, or

  ///   - equal to '(TripCount * stride) / cache_line_size' if (a) loop \p L's

  ///     induction variable is used only in the reference subscript associated

  ///     with loop \p L, and (b) the reference stride is less than the cache

  ///     line size, or

  ///   - TripCount otherwise

  CacheCostTy computeRefGroupCacheCost(const ReferenceGroupTy &RG,

                                       const Loop &L) const;

  /// Sort the LoopCosts vector by decreasing cache cost.

  void sortLoopCosts() {

    stable_sort(LoopCosts,

                [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {

                  return A.second > B.second;

                });

  }

private:

  /// Loops in the loop nest associated with this object.

  LoopVectorTy Loops;

  /// Trip counts for the loops in the loop nest associated with this object.

  SmallVector<LoopTripCountTy, 3> TripCounts;

  /// Cache costs for the loops in the loop nest associated with this object.

  SmallVector<LoopCacheCostTy, 3> LoopCosts;

  /// The max. distance between array elements accessed in a loop so that the

  /// elements are classified to have temporal reuse.

  std::optional<unsigned> TRT;

  const LoopInfo &LI;

  ScalarEvolution &SE;

  TargetTransformInfo &TTI;

  AAResults &AA;

  DependenceInfo &DI;

};

raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R);

raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC);

/// Printer pass for the \c CacheCost results.

class LoopCachePrinterPass : public PassInfoMixin<LoopCachePrinterPass> {

  raw_ostream &OS;

public:

  explicit LoopCachePrinterPass(raw_ostream &OS) : OS(OS) {}

  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,

                        LoopStandardAnalysisResults &AR, LPMUpdater &U);

};

} // namespace llvm

#endif // LLVM_ANALYSIS_LOOPCACHEANALYSIS_H