llvm/llvm/lib/Analysis/LoopCacheAnalysis.cpp

//===- LoopCacheAnalysis.cpp - Loop Cache Analysis -------------------------==//
//
//                     The LLVM Compiler Infrastructure
//
// 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 implementation for the loop cache analysis.
/// The implementation is largely based on the following paper:
///
///       Compiler Optimizations for Improving Data Locality
///       By: Steve Carr, Katherine S. McKinley, Chau-Wen Tseng
///       http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf
///
/// The general approach taken to estimate the number of cache lines used by the
/// memory references in an inner loop is:
///    1. Partition memory references that exhibit temporal or spacial reuse
///       into reference groups.
///    2. For each loop L in the a loop nest LN:
///       a. Compute the cost of the reference group
///       b. Compute the loop cost by summing up the reference groups costs
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopCacheAnalysis.h"
#include "llvm/ADT/BreadthFirstIterator.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Delinearization.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<unsigned> DefaultTripCount(
    "default-trip-count", cl::init(100), cl::Hidden,
    cl::desc("Use this to specify the default trip count of a loop"));

// In this analysis two array references are considered to exhibit temporal
// reuse if they access either the same memory location, or a memory location
// with distance smaller than a configurable threshold.
static cl::opt<unsigned> TemporalReuseThreshold(
    "temporal-reuse-threshold", cl::init(2), cl::Hidden,
    cl::desc("Use this to specify the max. distance between array elements "
             "accessed in a loop so that the elements are classified to have "
             "temporal reuse"));

/// Retrieve the innermost loop in the given loop nest \p Loops. It returns a
/// nullptr if any loops in the loop vector supplied has more than one sibling.
/// The loop vector is expected to contain loops collected in breadth-first
/// order.
static Loop *getInnerMostLoop(const LoopVectorTy &Loops) { … }

static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize,
                                  const Loop &L, ScalarEvolution &SE) { … }

/// Compute the trip count for the given loop \p L or assume a default value if
/// it is not a compile time constant. Return the SCEV expression for the trip
/// count.
static const SCEV *computeTripCount(const Loop &L, const SCEV &ElemSize,
                                    ScalarEvolution &SE) { … }

//===----------------------------------------------------------------------===//
// IndexedReference implementation
//
raw_ostream &llvm::operator<<(raw_ostream &OS, const IndexedReference &R) { … }

IndexedReference::IndexedReference(Instruction &StoreOrLoadInst,
                                   const LoopInfo &LI, ScalarEvolution &SE)
    : … { … }

std::optional<bool>
IndexedReference::hasSpacialReuse(const IndexedReference &Other, unsigned CLS,
                                  AAResults &AA) const { … }

std::optional<bool>
IndexedReference::hasTemporalReuse(const IndexedReference &Other,
                                   unsigned MaxDistance, const Loop &L,
                                   DependenceInfo &DI, AAResults &AA) const { … }

CacheCostTy IndexedReference::computeRefCost(const Loop &L,
                                             unsigned CLS) const { … }

bool IndexedReference::tryDelinearizeFixedSize(
    const SCEV *AccessFn, SmallVectorImpl<const SCEV *> &Subscripts) { … }

bool IndexedReference::delinearize(const LoopInfo &LI) { … }

bool IndexedReference::isLoopInvariant(const Loop &L) const { … }

bool IndexedReference::isConsecutive(const Loop &L, const SCEV *&Stride,
                                     unsigned CLS) const { … }

int IndexedReference::getSubscriptIndex(const Loop &L) const { … }

const SCEV *IndexedReference::getLastCoefficient() const { … }

bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
                                                     const Loop &L) const { … }

bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,
                                             const Loop &L) const { … }

bool IndexedReference::isAliased(const IndexedReference &Other,
                                 AAResults &AA) const { … }

//===----------------------------------------------------------------------===//
// CacheCost implementation
//
raw_ostream &llvm::operator<<(raw_ostream &OS, const CacheCost &CC) { … }

CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI,
                     ScalarEvolution &SE, TargetTransformInfo &TTI,
                     AAResults &AA, DependenceInfo &DI,
                     std::optional<unsigned> TRT)
    : … { … }

std::unique_ptr<CacheCost>
CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR,
                        DependenceInfo &DI, std::optional<unsigned> TRT) { … }

void CacheCost::calculateCacheFootprint() { … }

bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const { … }

CacheCostTy
CacheCost::computeLoopCacheCost(const Loop &L,
                                const ReferenceGroupsTy &RefGroups) const { … }

CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG,
                                                const Loop &L) const { … }

//===----------------------------------------------------------------------===//
// LoopCachePrinterPass implementation
//
PreservedAnalyses LoopCachePrinterPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &U) { … }