File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/include/llvm/Analysis

usr / src / contrib / llvm-project / llvm / include / llvm / Analysis /

📁 ..
📄 AliasAnalysis.h(51.98 KB)
📄 AliasAnalysisEvaluator.h(2.7 KB)
📄 AliasSetTracker.h(15.42 KB)
📄 AssumeBundleQueries.h(6.66 KB)
📄 AssumptionCache.h(8.39 KB)
📄 BasicAliasAnalysis.h(10.2 KB)
📄 BlockFrequencyInfo.h(5.59 KB)
📄 BlockFrequencyInfoImpl.h(56.46 KB)
📄 BranchProbabilityInfo.h(10.1 KB)
📄 CFG.h(7.76 KB)
📄 CFGPrinter.h(9.31 KB)
📄 CFLAliasAnalysisUtils.h(1.66 KB)
📄 CFLAndersAliasAnalysis.h(3.97 KB)
📄 CFLSteensAliasAnalysis.h(4.58 KB)
📄 CGSCCPassManager.h(41.2 KB)
📄 CallGraph.h(18.88 KB)
📄 CallGraphSCCPass.h(5.01 KB)
📄 CallPrinter.h(799 B)
📄 CaptureTracking.h(4.78 KB)
📄 CmpInstAnalysis.h(2.57 KB)
📄 CodeMetrics.h(3.15 KB)
📄 ConstantFolding.h(8.01 KB)
📄 DDG.h(19.15 KB)
📄 DOTGraphTraitsPass.h(5.5 KB)
📄 DemandedBits.h(4.07 KB)
📄 DependenceAnalysis.h(41.83 KB)
📄 DependenceGraphBuilder.h(7.74 KB)
📄 DivergenceAnalysis.h(7.38 KB)
📄 DomPrinter.h(1.04 KB)
📄 DomTreeUpdater.h(13.2 KB)
📄 DominanceFrontier.h(6.63 KB)
📄 DominanceFrontierImpl.h(7.12 KB)
📄 EHPersonalities.h(3.22 KB)
📄 GlobalsModRef.h(5.96 KB)
📄 GuardUtils.h(2.11 KB)
📄 HeatUtils.h(1.16 KB)
📄 IVDescriptors.h(14.56 KB)
📄 IVUsers.h(6.07 KB)
📄 IndirectCallPromotionAnalysis.h(2.61 KB)
📄 IndirectCallVisitor.h(1.16 KB)
📄 InlineAdvisor.h(8.71 KB)
📄 InlineCost.h(11.33 KB)
📄 InlineFeaturesAnalysis.h(1.5 KB)
📄 InlineModelFeatureMaps.h(3.41 KB)
📄 InlineSizeEstimatorAnalysis.h(1.07 KB)
📄 InstructionPrecedenceTracking.h(5.9 KB)
📄 InstructionSimplify.h(13.36 KB)
📄 Interval.h(4.84 KB)
📄 IntervalIterator.h(10.64 KB)
📄 IntervalPartition.h(4.05 KB)
📄 IteratedDominanceFrontier.h(2.62 KB)
📄 LazyBlockFrequencyInfo.h(4.34 KB)
📄 LazyBranchProbabilityInfo.h(4.21 KB)
📄 LazyCallGraph.h(50.13 KB)
📄 LazyValueInfo.h(5.4 KB)
📄 LegacyDivergenceAnalysis.h(2.53 KB)
📄 Lint.h(1.35 KB)
📄 Loads.h(7.86 KB)
📄 LoopAccessAnalysis.h(29.75 KB)
📄 LoopAnalysisManager.h(5.83 KB)
📄 LoopCacheAnalysis.h(11.91 KB)
📄 LoopInfo.h(48.27 KB)
📄 LoopInfoImpl.h(27.14 KB)
📄 LoopIterator.h(8.83 KB)
📄 LoopNestAnalysis.h(5.61 KB)
📄 LoopPass.h(4.29 KB)
📄 LoopUnrollAnalyzer.h(3.42 KB)
📄 MLInlineAdvisor.h(3.48 KB)
📄 MLModelRunner.h(1.16 KB)
📄 MemoryBuiltins.h(13.42 KB)
📄 MemoryDependenceAnalysis.h(20.82 KB)
📄 MemoryLocation.h(10.99 KB)
📄 MemorySSA.h(45.92 KB)
📄 MemorySSAUpdater.h(14.55 KB)
📄 ModuleSummaryAnalysis.h(3.44 KB)
📄 MustExecute.h(20.2 KB)
📄 ObjCARCAliasAnalysis.h(3.35 KB)
📄 ObjCARCAnalysisUtils.h(10.22 KB)
📄 ObjCARCInstKind.h(4.87 KB)
📄 OptimizationRemarkEmitter.h(5.93 KB)
📄 PHITransAddr.h(4.77 KB)
📄 Passes.h(3.88 KB)
📄 PhiValues.h(5.25 KB)
📄 PostDominators.h(3.41 KB)
📄 ProfileSummaryInfo.h(9.3 KB)
📄 PtrUseVisitor.h(9.96 KB)
📄 RegionInfo.h(35.23 KB)
📄 RegionInfoImpl.h(25.16 KB)
📄 RegionIterator.h(14.07 KB)
📄 RegionPass.h(4.05 KB)
📄 RegionPrinter.h(2.25 KB)
📄 ScalarEvolution.h(89.21 KB)
📄 ScalarEvolutionAliasAnalysis.h(2.09 KB)
📄 ScalarEvolutionDivision.h(2.48 KB)
📄 ScalarEvolutionExpressions.h(28.61 KB)
📄 ScalarEvolutionNormalization.h(2.47 KB)
📄 ScopedNoAliasAA.h(2.83 KB)
📄 SparsePropagation.h(19.43 KB)
📄 StackLifetime.h(6.16 KB)
📄 StackSafetyAnalysis.h(4.91 KB)
📄 SyncDependenceAnalysis.h(2.85 KB)
📄 SyntheticCountsUtils.h(1.85 KB)
📄 TargetFolder.h(11.04 KB)
📄 TargetLibraryInfo.def(55.35 KB)
📄 TargetLibraryInfo.h(16.86 KB)
📄 TargetTransformInfo.h(96.51 KB)
📄 TargetTransformInfoImpl.h(37.63 KB)
📄 Trace.h(4.1 KB)
📄 TypeBasedAliasAnalysis.h(3.05 KB)
📄 TypeMetadataUtils.h(1.94 KB)
📁 Utils
📄 ValueLattice.h(15.14 KB)
📄 ValueLatticeUtils.h(1.66 KB)
📄 ValueTracking.h(35.82 KB)
📄 VecFuncs.def(10.94 KB)
📄 VectorUtils.h(37.26 KB)

Editing: LoopCacheAnalysis.h

//===- 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/AliasAnalysis.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"

namespace llvm {

class LPMUpdater;
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 None if unsure.
  Optional<bool> hasSpacialReuse(const IndexedReference &Other, unsigned CLS,
                                 AliasAnalysis &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 None if unsure.
  Optional<bool> hasTemporalReuse(const IndexedReference &Other,
                                  unsigned MaxDistance, const Loop &L,
                                  DependenceInfo &DI, AliasAnalysis &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);

/// 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.
  bool isConsecutive(const Loop &L, unsigned CLS) 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, AliasAnalysis &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, AliasAnalysis &AA, DependenceInfo &DI,
            Optional<unsigned> TRT = None);

/// 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,
               Optional<unsigned> TRT = None);

/// 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 = std::find_if(
        LoopCosts.begin(), LoopCosts.end(),
        [&L](const LoopCacheCostTy &LCC) { return LCC.first == &L; });
    return (IT != LoopCosts.end()) ? (*IT).second : -1;
  }

/// Return the estimated ordered loop costs.
  const 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() {
    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.
  Optional<unsigned> TRT;

const LoopInfo &LI;
  ScalarEvolution &SE;
  TargetTransformInfo &TTI;
  AliasAnalysis &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

003 File Manager

Editing: LoopCacheAnalysis.h

Upload File

Create Folder