llvm/llvm/include/llvm/Analysis/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/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;

CacheCostTy;
LoopVectorTy;

/// 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 { … };

/// 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.
ReferenceGroupTy;
ReferenceGroupsTy;

/// \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 { … };

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> { … };

} // namespace llvm

#endif // LLVM_ANALYSIS_LOOPCACHEANALYSIS_H