xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
18bcb0991SDimitry Andric //===- LoopCacheAnalysis.cpp - Loop Cache Analysis -------------------------==//
28bcb0991SDimitry Andric //
38bcb0991SDimitry Andric //                     The LLVM Compiler Infrastructure
48bcb0991SDimitry Andric //
58bcb0991SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
68bcb0991SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
78bcb0991SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
88bcb0991SDimitry Andric //
98bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
108bcb0991SDimitry Andric ///
118bcb0991SDimitry Andric /// \file
128bcb0991SDimitry Andric /// This file defines the implementation for the loop cache analysis.
138bcb0991SDimitry Andric /// The implementation is largely based on the following paper:
148bcb0991SDimitry Andric ///
158bcb0991SDimitry Andric ///       Compiler Optimizations for Improving Data Locality
168bcb0991SDimitry Andric ///       By: Steve Carr, Katherine S. McKinley, Chau-Wen Tseng
178bcb0991SDimitry Andric ///       http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf
188bcb0991SDimitry Andric ///
198bcb0991SDimitry Andric /// The general approach taken to estimate the number of cache lines used by the
208bcb0991SDimitry Andric /// memory references in an inner loop is:
218bcb0991SDimitry Andric ///    1. Partition memory references that exhibit temporal or spacial reuse
228bcb0991SDimitry Andric ///       into reference groups.
238bcb0991SDimitry Andric ///    2. For each loop L in the a loop nest LN:
248bcb0991SDimitry Andric ///       a. Compute the cost of the reference group
258bcb0991SDimitry Andric ///       b. Compute the loop cost by summing up the reference groups costs
268bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
278bcb0991SDimitry Andric 
288bcb0991SDimitry Andric #include "llvm/Analysis/LoopCacheAnalysis.h"
298bcb0991SDimitry Andric #include "llvm/ADT/BreadthFirstIterator.h"
308bcb0991SDimitry Andric #include "llvm/ADT/Sequence.h"
318bcb0991SDimitry Andric #include "llvm/ADT/SmallVector.h"
32e8d8bef9SDimitry Andric #include "llvm/Analysis/AliasAnalysis.h"
33349cc55cSDimitry Andric #include "llvm/Analysis/Delinearization.h"
34e8d8bef9SDimitry Andric #include "llvm/Analysis/DependenceAnalysis.h"
35e8d8bef9SDimitry Andric #include "llvm/Analysis/LoopInfo.h"
365ffd83dbSDimitry Andric #include "llvm/Analysis/ScalarEvolutionExpressions.h"
37e8d8bef9SDimitry Andric #include "llvm/Analysis/TargetTransformInfo.h"
38480093f4SDimitry Andric #include "llvm/Support/CommandLine.h"
398bcb0991SDimitry Andric #include "llvm/Support/Debug.h"
408bcb0991SDimitry Andric 
418bcb0991SDimitry Andric using namespace llvm;
428bcb0991SDimitry Andric 
438bcb0991SDimitry Andric #define DEBUG_TYPE "loop-cache-cost"
448bcb0991SDimitry Andric 
458bcb0991SDimitry Andric static cl::opt<unsigned> DefaultTripCount(
468bcb0991SDimitry Andric     "default-trip-count", cl::init(100), cl::Hidden,
478bcb0991SDimitry Andric     cl::desc("Use this to specify the default trip count of a loop"));
488bcb0991SDimitry Andric 
498bcb0991SDimitry Andric // In this analysis two array references are considered to exhibit temporal
508bcb0991SDimitry Andric // reuse if they access either the same memory location, or a memory location
518bcb0991SDimitry Andric // with distance smaller than a configurable threshold.
528bcb0991SDimitry Andric static cl::opt<unsigned> TemporalReuseThreshold(
538bcb0991SDimitry Andric     "temporal-reuse-threshold", cl::init(2), cl::Hidden,
548bcb0991SDimitry Andric     cl::desc("Use this to specify the max. distance between array elements "
558bcb0991SDimitry Andric              "accessed in a loop so that the elements are classified to have "
568bcb0991SDimitry Andric              "temporal reuse"));
578bcb0991SDimitry Andric 
588bcb0991SDimitry Andric /// Retrieve the innermost loop in the given loop nest \p Loops. It returns a
598bcb0991SDimitry Andric /// nullptr if any loops in the loop vector supplied has more than one sibling.
608bcb0991SDimitry Andric /// The loop vector is expected to contain loops collected in breadth-first
618bcb0991SDimitry Andric /// order.
getInnerMostLoop(const LoopVectorTy & Loops)628bcb0991SDimitry Andric static Loop *getInnerMostLoop(const LoopVectorTy &Loops) {
638bcb0991SDimitry Andric   assert(!Loops.empty() && "Expecting a non-empy loop vector");
648bcb0991SDimitry Andric 
658bcb0991SDimitry Andric   Loop *LastLoop = Loops.back();
668bcb0991SDimitry Andric   Loop *ParentLoop = LastLoop->getParentLoop();
678bcb0991SDimitry Andric 
688bcb0991SDimitry Andric   if (ParentLoop == nullptr) {
698bcb0991SDimitry Andric     assert(Loops.size() == 1 && "Expecting a single loop");
708bcb0991SDimitry Andric     return LastLoop;
718bcb0991SDimitry Andric   }
728bcb0991SDimitry Andric 
735ffd83dbSDimitry Andric   return (llvm::is_sorted(Loops,
748bcb0991SDimitry Andric                           [](const Loop *L1, const Loop *L2) {
758bcb0991SDimitry Andric                             return L1->getLoopDepth() < L2->getLoopDepth();
768bcb0991SDimitry Andric                           }))
778bcb0991SDimitry Andric              ? LastLoop
788bcb0991SDimitry Andric              : nullptr;
798bcb0991SDimitry Andric }
808bcb0991SDimitry Andric 
isOneDimensionalArray(const SCEV & AccessFn,const SCEV & ElemSize,const Loop & L,ScalarEvolution & SE)818bcb0991SDimitry Andric static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize,
828bcb0991SDimitry Andric                                   const Loop &L, ScalarEvolution &SE) {
838bcb0991SDimitry Andric   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&AccessFn);
848bcb0991SDimitry Andric   if (!AR || !AR->isAffine())
858bcb0991SDimitry Andric     return false;
868bcb0991SDimitry Andric 
878bcb0991SDimitry Andric   assert(AR->getLoop() && "AR should have a loop");
888bcb0991SDimitry Andric 
898bcb0991SDimitry Andric   // Check that start and increment are not add recurrences.
908bcb0991SDimitry Andric   const SCEV *Start = AR->getStart();
918bcb0991SDimitry Andric   const SCEV *Step = AR->getStepRecurrence(SE);
928bcb0991SDimitry Andric   if (isa<SCEVAddRecExpr>(Start) || isa<SCEVAddRecExpr>(Step))
938bcb0991SDimitry Andric     return false;
948bcb0991SDimitry Andric 
958bcb0991SDimitry Andric   // Check that start and increment are both invariant in the loop.
968bcb0991SDimitry Andric   if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))
978bcb0991SDimitry Andric     return false;
988bcb0991SDimitry Andric 
995ffd83dbSDimitry Andric   const SCEV *StepRec = AR->getStepRecurrence(SE);
1005ffd83dbSDimitry Andric   if (StepRec && SE.isKnownNegative(StepRec))
1015ffd83dbSDimitry Andric     StepRec = SE.getNegativeSCEV(StepRec);
1025ffd83dbSDimitry Andric 
1035ffd83dbSDimitry Andric   return StepRec == &ElemSize;
1048bcb0991SDimitry Andric }
1058bcb0991SDimitry Andric 
10681ad6265SDimitry Andric /// Compute the trip count for the given loop \p L or assume a default value if
10781ad6265SDimitry Andric /// it is not a compile time constant. Return the SCEV expression for the trip
10881ad6265SDimitry Andric /// count.
computeTripCount(const Loop & L,const SCEV & ElemSize,ScalarEvolution & SE)10981ad6265SDimitry Andric static const SCEV *computeTripCount(const Loop &L, const SCEV &ElemSize,
11081ad6265SDimitry Andric                                     ScalarEvolution &SE) {
1118bcb0991SDimitry Andric   const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(&L);
11281ad6265SDimitry Andric   const SCEV *TripCount = (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
11381ad6265SDimitry Andric                            isa<SCEVConstant>(BackedgeTakenCount))
11481ad6265SDimitry Andric                               ? SE.getTripCountFromExitCount(BackedgeTakenCount)
11581ad6265SDimitry Andric                               : nullptr;
11681ad6265SDimitry Andric 
11781ad6265SDimitry Andric   if (!TripCount) {
11881ad6265SDimitry Andric     LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName()
11981ad6265SDimitry Andric                << " could not be computed, using DefaultTripCount\n");
12081ad6265SDimitry Andric     TripCount = SE.getConstant(ElemSize.getType(), DefaultTripCount);
12181ad6265SDimitry Andric   }
12281ad6265SDimitry Andric 
12381ad6265SDimitry Andric   return TripCount;
1248bcb0991SDimitry Andric }
1258bcb0991SDimitry Andric 
1268bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
1278bcb0991SDimitry Andric // IndexedReference implementation
1288bcb0991SDimitry Andric //
operator <<(raw_ostream & OS,const IndexedReference & R)1298bcb0991SDimitry Andric raw_ostream &llvm::operator<<(raw_ostream &OS, const IndexedReference &R) {
1308bcb0991SDimitry Andric   if (!R.IsValid) {
1318bcb0991SDimitry Andric     OS << R.StoreOrLoadInst;
1328bcb0991SDimitry Andric     OS << ", IsValid=false.";
1338bcb0991SDimitry Andric     return OS;
1348bcb0991SDimitry Andric   }
1358bcb0991SDimitry Andric 
1368bcb0991SDimitry Andric   OS << *R.BasePointer;
1378bcb0991SDimitry Andric   for (const SCEV *Subscript : R.Subscripts)
1388bcb0991SDimitry Andric     OS << "[" << *Subscript << "]";
1398bcb0991SDimitry Andric 
1408bcb0991SDimitry Andric   OS << ", Sizes: ";
1418bcb0991SDimitry Andric   for (const SCEV *Size : R.Sizes)
1428bcb0991SDimitry Andric     OS << "[" << *Size << "]";
1438bcb0991SDimitry Andric 
1448bcb0991SDimitry Andric   return OS;
1458bcb0991SDimitry Andric }
1468bcb0991SDimitry Andric 
IndexedReference(Instruction & StoreOrLoadInst,const LoopInfo & LI,ScalarEvolution & SE)1478bcb0991SDimitry Andric IndexedReference::IndexedReference(Instruction &StoreOrLoadInst,
1488bcb0991SDimitry Andric                                    const LoopInfo &LI, ScalarEvolution &SE)
1498bcb0991SDimitry Andric     : StoreOrLoadInst(StoreOrLoadInst), SE(SE) {
1508bcb0991SDimitry Andric   assert((isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst>(StoreOrLoadInst)) &&
1518bcb0991SDimitry Andric          "Expecting a load or store instruction");
1528bcb0991SDimitry Andric 
1538bcb0991SDimitry Andric   IsValid = delinearize(LI);
1548bcb0991SDimitry Andric   if (IsValid)
1558bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(2) << "Succesfully delinearized: " << *this
1568bcb0991SDimitry Andric                                 << "\n");
1578bcb0991SDimitry Andric }
1588bcb0991SDimitry Andric 
159bdd1243dSDimitry Andric std::optional<bool>
hasSpacialReuse(const IndexedReference & Other,unsigned CLS,AAResults & AA) const160bdd1243dSDimitry Andric IndexedReference::hasSpacialReuse(const IndexedReference &Other, unsigned CLS,
161e8d8bef9SDimitry Andric                                   AAResults &AA) const {
1628bcb0991SDimitry Andric   assert(IsValid && "Expecting a valid reference");
1638bcb0991SDimitry Andric 
1648bcb0991SDimitry Andric   if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
1658bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(2)
1668bcb0991SDimitry Andric                << "No spacial reuse: different base pointers\n");
1678bcb0991SDimitry Andric     return false;
1688bcb0991SDimitry Andric   }
1698bcb0991SDimitry Andric 
1708bcb0991SDimitry Andric   unsigned NumSubscripts = getNumSubscripts();
1718bcb0991SDimitry Andric   if (NumSubscripts != Other.getNumSubscripts()) {
1728bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(2)
1738bcb0991SDimitry Andric                << "No spacial reuse: different number of subscripts\n");
1748bcb0991SDimitry Andric     return false;
1758bcb0991SDimitry Andric   }
1768bcb0991SDimitry Andric 
1778bcb0991SDimitry Andric   // all subscripts must be equal, except the leftmost one (the last one).
1788bcb0991SDimitry Andric   for (auto SubNum : seq<unsigned>(0, NumSubscripts - 1)) {
1798bcb0991SDimitry Andric     if (getSubscript(SubNum) != Other.getSubscript(SubNum)) {
1808bcb0991SDimitry Andric       LLVM_DEBUG(dbgs().indent(2) << "No spacial reuse, different subscripts: "
1818bcb0991SDimitry Andric                                   << "\n\t" << *getSubscript(SubNum) << "\n\t"
1828bcb0991SDimitry Andric                                   << *Other.getSubscript(SubNum) << "\n");
1838bcb0991SDimitry Andric       return false;
1848bcb0991SDimitry Andric     }
1858bcb0991SDimitry Andric   }
1868bcb0991SDimitry Andric 
1878bcb0991SDimitry Andric   // the difference between the last subscripts must be less than the cache line
1888bcb0991SDimitry Andric   // size.
1898bcb0991SDimitry Andric   const SCEV *LastSubscript = getLastSubscript();
1908bcb0991SDimitry Andric   const SCEV *OtherLastSubscript = Other.getLastSubscript();
1918bcb0991SDimitry Andric   const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
1928bcb0991SDimitry Andric       SE.getMinusSCEV(LastSubscript, OtherLastSubscript));
1938bcb0991SDimitry Andric 
1948bcb0991SDimitry Andric   if (Diff == nullptr) {
1958bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(2)
1968bcb0991SDimitry Andric                << "No spacial reuse, difference between subscript:\n\t"
1978bcb0991SDimitry Andric                << *LastSubscript << "\n\t" << OtherLastSubscript
1988bcb0991SDimitry Andric                << "\nis not constant.\n");
199bdd1243dSDimitry Andric     return std::nullopt;
2008bcb0991SDimitry Andric   }
2018bcb0991SDimitry Andric 
2028bcb0991SDimitry Andric   bool InSameCacheLine = (Diff->getValue()->getSExtValue() < CLS);
2038bcb0991SDimitry Andric 
2048bcb0991SDimitry Andric   LLVM_DEBUG({
2058bcb0991SDimitry Andric     if (InSameCacheLine)
2068bcb0991SDimitry Andric       dbgs().indent(2) << "Found spacial reuse.\n";
2078bcb0991SDimitry Andric     else
2088bcb0991SDimitry Andric       dbgs().indent(2) << "No spacial reuse.\n";
2098bcb0991SDimitry Andric   });
2108bcb0991SDimitry Andric 
2118bcb0991SDimitry Andric   return InSameCacheLine;
2128bcb0991SDimitry Andric }
2138bcb0991SDimitry Andric 
214bdd1243dSDimitry Andric std::optional<bool>
hasTemporalReuse(const IndexedReference & Other,unsigned MaxDistance,const Loop & L,DependenceInfo & DI,AAResults & AA) const215bdd1243dSDimitry Andric IndexedReference::hasTemporalReuse(const IndexedReference &Other,
216bdd1243dSDimitry Andric                                    unsigned MaxDistance, const Loop &L,
217bdd1243dSDimitry Andric                                    DependenceInfo &DI, AAResults &AA) const {
2188bcb0991SDimitry Andric   assert(IsValid && "Expecting a valid reference");
2198bcb0991SDimitry Andric 
2208bcb0991SDimitry Andric   if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
2218bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(2)
2228bcb0991SDimitry Andric                << "No temporal reuse: different base pointer\n");
2238bcb0991SDimitry Andric     return false;
2248bcb0991SDimitry Andric   }
2258bcb0991SDimitry Andric 
2268bcb0991SDimitry Andric   std::unique_ptr<Dependence> D =
2278bcb0991SDimitry Andric       DI.depends(&StoreOrLoadInst, &Other.StoreOrLoadInst, true);
2288bcb0991SDimitry Andric 
2298bcb0991SDimitry Andric   if (D == nullptr) {
2308bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: no dependence\n");
2318bcb0991SDimitry Andric     return false;
2328bcb0991SDimitry Andric   }
2338bcb0991SDimitry Andric 
2348bcb0991SDimitry Andric   if (D->isLoopIndependent()) {
2358bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
2368bcb0991SDimitry Andric     return true;
2378bcb0991SDimitry Andric   }
2388bcb0991SDimitry Andric 
2398bcb0991SDimitry Andric   // Check the dependence distance at every loop level. There is temporal reuse
2408bcb0991SDimitry Andric   // if the distance at the given loop's depth is small (|d| <= MaxDistance) and
2418bcb0991SDimitry Andric   // it is zero at every other loop level.
2428bcb0991SDimitry Andric   int LoopDepth = L.getLoopDepth();
2438bcb0991SDimitry Andric   int Levels = D->getLevels();
2448bcb0991SDimitry Andric   for (int Level = 1; Level <= Levels; ++Level) {
2458bcb0991SDimitry Andric     const SCEV *Distance = D->getDistance(Level);
2468bcb0991SDimitry Andric     const SCEVConstant *SCEVConst = dyn_cast_or_null<SCEVConstant>(Distance);
2478bcb0991SDimitry Andric 
2488bcb0991SDimitry Andric     if (SCEVConst == nullptr) {
2498bcb0991SDimitry Andric       LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: distance unknown\n");
250bdd1243dSDimitry Andric       return std::nullopt;
2518bcb0991SDimitry Andric     }
2528bcb0991SDimitry Andric 
2538bcb0991SDimitry Andric     const ConstantInt &CI = *SCEVConst->getValue();
2548bcb0991SDimitry Andric     if (Level != LoopDepth && !CI.isZero()) {
2558bcb0991SDimitry Andric       LLVM_DEBUG(dbgs().indent(2)
2568bcb0991SDimitry Andric                  << "No temporal reuse: distance is not zero at depth=" << Level
2578bcb0991SDimitry Andric                  << "\n");
2588bcb0991SDimitry Andric       return false;
2598bcb0991SDimitry Andric     } else if (Level == LoopDepth && CI.getSExtValue() > MaxDistance) {
2608bcb0991SDimitry Andric       LLVM_DEBUG(
2618bcb0991SDimitry Andric           dbgs().indent(2)
2628bcb0991SDimitry Andric           << "No temporal reuse: distance is greater than MaxDistance at depth="
2638bcb0991SDimitry Andric           << Level << "\n");
2648bcb0991SDimitry Andric       return false;
2658bcb0991SDimitry Andric     }
2668bcb0991SDimitry Andric   }
2678bcb0991SDimitry Andric 
2688bcb0991SDimitry Andric   LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
2698bcb0991SDimitry Andric   return true;
2708bcb0991SDimitry Andric }
2718bcb0991SDimitry Andric 
computeRefCost(const Loop & L,unsigned CLS) const2728bcb0991SDimitry Andric CacheCostTy IndexedReference::computeRefCost(const Loop &L,
2738bcb0991SDimitry Andric                                              unsigned CLS) const {
2748bcb0991SDimitry Andric   assert(IsValid && "Expecting a valid reference");
2758bcb0991SDimitry Andric   LLVM_DEBUG({
2768bcb0991SDimitry Andric     dbgs().indent(2) << "Computing cache cost for:\n";
2778bcb0991SDimitry Andric     dbgs().indent(4) << *this << "\n";
2788bcb0991SDimitry Andric   });
2798bcb0991SDimitry Andric 
2808bcb0991SDimitry Andric   // If the indexed reference is loop invariant the cost is one.
2818bcb0991SDimitry Andric   if (isLoopInvariant(L)) {
2828bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(4) << "Reference is loop invariant: RefCost=1\n");
2838bcb0991SDimitry Andric     return 1;
2848bcb0991SDimitry Andric   }
2858bcb0991SDimitry Andric 
28681ad6265SDimitry Andric   const SCEV *TripCount = computeTripCount(L, *Sizes.back(), SE);
28781ad6265SDimitry Andric   assert(TripCount && "Expecting valid TripCount");
2888bcb0991SDimitry Andric   LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n");
2898bcb0991SDimitry Andric 
29081ad6265SDimitry Andric   const SCEV *RefCost = nullptr;
291fcaf7f86SDimitry Andric   const SCEV *Stride = nullptr;
292fcaf7f86SDimitry Andric   if (isConsecutive(L, Stride, CLS)) {
29381ad6265SDimitry Andric     // If the indexed reference is 'consecutive' the cost is
29481ad6265SDimitry Andric     // (TripCount*Stride)/CLS.
295fcaf7f86SDimitry Andric     assert(Stride != nullptr &&
296fcaf7f86SDimitry Andric            "Stride should not be null for consecutive access!");
297480093f4SDimitry Andric     Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());
298349cc55cSDimitry Andric     const SCEV *CacheLineSize = SE.getConstant(WiderType, CLS);
2995ffd83dbSDimitry Andric     Stride = SE.getNoopOrAnyExtend(Stride, WiderType);
30006c3fb27SDimitry Andric     TripCount = SE.getNoopOrZeroExtend(TripCount, WiderType);
3018bcb0991SDimitry Andric     const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);
302*0fca6ea1SDimitry Andric     // Round the fractional cost up to the nearest integer number.
303*0fca6ea1SDimitry Andric     // The impact is the most significant when cost is calculated
304*0fca6ea1SDimitry Andric     // to be a number less than one, because it makes more sense
305*0fca6ea1SDimitry Andric     // to say one cache line is used rather than zero cache line
306*0fca6ea1SDimitry Andric     // is used.
307*0fca6ea1SDimitry Andric     RefCost = SE.getUDivCeilSCEV(Numerator, CacheLineSize);
3085ffd83dbSDimitry Andric 
3098bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(4)
3108bcb0991SDimitry Andric                << "Access is consecutive: RefCost=(TripCount*Stride)/CLS="
3118bcb0991SDimitry Andric                << *RefCost << "\n");
31281ad6265SDimitry Andric   } else {
31381ad6265SDimitry Andric     // If the indexed reference is not 'consecutive' the cost is proportional to
31481ad6265SDimitry Andric     // the trip count and the depth of the dimension which the subject loop
31581ad6265SDimitry Andric     // subscript is accessing. We try to estimate this by multiplying the cost
31681ad6265SDimitry Andric     // by the trip counts of loops corresponding to the inner dimensions. For
31781ad6265SDimitry Andric     // example, given the indexed reference 'A[i][j][k]', and assuming the
31881ad6265SDimitry Andric     // i-loop is in the innermost position, the cost would be equal to the
31981ad6265SDimitry Andric     // iterations of the i-loop multiplied by iterations of the j-loop.
32081ad6265SDimitry Andric     RefCost = TripCount;
32181ad6265SDimitry Andric 
32281ad6265SDimitry Andric     int Index = getSubscriptIndex(L);
323*0fca6ea1SDimitry Andric     assert(Index >= 0 && "Could not locate a valid Index");
32481ad6265SDimitry Andric 
32581ad6265SDimitry Andric     for (unsigned I = Index + 1; I < getNumSubscripts() - 1; ++I) {
32681ad6265SDimitry Andric       const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(I));
32781ad6265SDimitry Andric       assert(AR && AR->getLoop() && "Expecting valid loop");
32881ad6265SDimitry Andric       const SCEV *TripCount =
32981ad6265SDimitry Andric           computeTripCount(*AR->getLoop(), *Sizes.back(), SE);
33081ad6265SDimitry Andric       Type *WiderType = SE.getWiderType(RefCost->getType(), TripCount->getType());
33106c3fb27SDimitry Andric       RefCost = SE.getMulExpr(SE.getNoopOrZeroExtend(RefCost, WiderType),
33206c3fb27SDimitry Andric                               SE.getNoopOrZeroExtend(TripCount, WiderType));
33381ad6265SDimitry Andric     }
33481ad6265SDimitry Andric 
3358bcb0991SDimitry Andric     LLVM_DEBUG(dbgs().indent(4)
33681ad6265SDimitry Andric                << "Access is not consecutive: RefCost=" << *RefCost << "\n");
33781ad6265SDimitry Andric   }
33881ad6265SDimitry Andric   assert(RefCost && "Expecting a valid RefCost");
3398bcb0991SDimitry Andric 
3408bcb0991SDimitry Andric   // Attempt to fold RefCost into a constant.
3418bcb0991SDimitry Andric   if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost))
34206c3fb27SDimitry Andric     return ConstantCost->getValue()->getZExtValue();
3438bcb0991SDimitry Andric 
3448bcb0991SDimitry Andric   LLVM_DEBUG(dbgs().indent(4)
3458bcb0991SDimitry Andric              << "RefCost is not a constant! Setting to RefCost=InvalidCost "
3468bcb0991SDimitry Andric                 "(invalid value).\n");
3478bcb0991SDimitry Andric 
3488bcb0991SDimitry Andric   return CacheCost::InvalidCost;
3498bcb0991SDimitry Andric }
3508bcb0991SDimitry Andric 
tryDelinearizeFixedSize(const SCEV * AccessFn,SmallVectorImpl<const SCEV * > & Subscripts)35181ad6265SDimitry Andric bool IndexedReference::tryDelinearizeFixedSize(
35281ad6265SDimitry Andric     const SCEV *AccessFn, SmallVectorImpl<const SCEV *> &Subscripts) {
35381ad6265SDimitry Andric   SmallVector<int, 4> ArraySizes;
35481ad6265SDimitry Andric   if (!tryDelinearizeFixedSizeImpl(&SE, &StoreOrLoadInst, AccessFn, Subscripts,
35581ad6265SDimitry Andric                                    ArraySizes))
35681ad6265SDimitry Andric     return false;
35781ad6265SDimitry Andric 
35881ad6265SDimitry Andric   // Populate Sizes with scev expressions to be used in calculations later.
35981ad6265SDimitry Andric   for (auto Idx : seq<unsigned>(1, Subscripts.size()))
36081ad6265SDimitry Andric     Sizes.push_back(
36181ad6265SDimitry Andric         SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1]));
36281ad6265SDimitry Andric 
36381ad6265SDimitry Andric   LLVM_DEBUG({
36481ad6265SDimitry Andric     dbgs() << "Delinearized subscripts of fixed-size array\n"
36581ad6265SDimitry Andric            << "GEP:" << *getLoadStorePointerOperand(&StoreOrLoadInst)
36681ad6265SDimitry Andric            << "\n";
36781ad6265SDimitry Andric   });
36881ad6265SDimitry Andric   return true;
36981ad6265SDimitry Andric }
37081ad6265SDimitry Andric 
delinearize(const LoopInfo & LI)3718bcb0991SDimitry Andric bool IndexedReference::delinearize(const LoopInfo &LI) {
3728bcb0991SDimitry Andric   assert(Subscripts.empty() && "Subscripts should be empty");
3738bcb0991SDimitry Andric   assert(Sizes.empty() && "Sizes should be empty");
3748bcb0991SDimitry Andric   assert(!IsValid && "Should be called once from the constructor");
3758bcb0991SDimitry Andric   LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");
3768bcb0991SDimitry Andric 
3778bcb0991SDimitry Andric   const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);
3788bcb0991SDimitry Andric   const BasicBlock *BB = StoreOrLoadInst.getParent();
3798bcb0991SDimitry Andric 
380480093f4SDimitry Andric   if (Loop *L = LI.getLoopFor(BB)) {
3818bcb0991SDimitry Andric     const SCEV *AccessFn =
3828bcb0991SDimitry Andric         SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L);
3838bcb0991SDimitry Andric 
3848bcb0991SDimitry Andric     BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));
3858bcb0991SDimitry Andric     if (BasePointer == nullptr) {
3868bcb0991SDimitry Andric       LLVM_DEBUG(
3878bcb0991SDimitry Andric           dbgs().indent(2)
3888bcb0991SDimitry Andric           << "ERROR: failed to delinearize, can't identify base pointer\n");
3898bcb0991SDimitry Andric       return false;
3908bcb0991SDimitry Andric     }
3918bcb0991SDimitry Andric 
39281ad6265SDimitry Andric     bool IsFixedSize = false;
39381ad6265SDimitry Andric     // Try to delinearize fixed-size arrays.
39481ad6265SDimitry Andric     if (tryDelinearizeFixedSize(AccessFn, Subscripts)) {
39581ad6265SDimitry Andric       IsFixedSize = true;
39681ad6265SDimitry Andric       // The last element of Sizes is the element size.
39781ad6265SDimitry Andric       Sizes.push_back(ElemSize);
3988bcb0991SDimitry Andric       LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
3998bcb0991SDimitry Andric                                   << "', AccessFn: " << *AccessFn << "\n");
40081ad6265SDimitry Andric     }
4018bcb0991SDimitry Andric 
40281ad6265SDimitry Andric     AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
40381ad6265SDimitry Andric 
40481ad6265SDimitry Andric     // Try to delinearize parametric-size arrays.
40581ad6265SDimitry Andric     if (!IsFixedSize) {
40681ad6265SDimitry Andric       LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
40781ad6265SDimitry Andric                                   << "', AccessFn: " << *AccessFn << "\n");
408349cc55cSDimitry Andric       llvm::delinearize(SE, AccessFn, Subscripts, Sizes,
4098bcb0991SDimitry Andric                         SE.getElementSize(&StoreOrLoadInst));
41081ad6265SDimitry Andric     }
4118bcb0991SDimitry Andric 
4128bcb0991SDimitry Andric     if (Subscripts.empty() || Sizes.empty() ||
4138bcb0991SDimitry Andric         Subscripts.size() != Sizes.size()) {
4148bcb0991SDimitry Andric       // Attempt to determine whether we have a single dimensional array access.
4158bcb0991SDimitry Andric       // before giving up.
4168bcb0991SDimitry Andric       if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {
4178bcb0991SDimitry Andric         LLVM_DEBUG(dbgs().indent(2)
4188bcb0991SDimitry Andric                    << "ERROR: failed to delinearize reference\n");
4198bcb0991SDimitry Andric         Subscripts.clear();
4208bcb0991SDimitry Andric         Sizes.clear();
421480093f4SDimitry Andric         return false;
4228bcb0991SDimitry Andric       }
4238bcb0991SDimitry Andric 
4245ffd83dbSDimitry Andric       // The array may be accessed in reverse, for example:
4255ffd83dbSDimitry Andric       //   for (i = N; i > 0; i--)
4265ffd83dbSDimitry Andric       //     A[i] = 0;
4275ffd83dbSDimitry Andric       // In this case, reconstruct the access function using the absolute value
4285ffd83dbSDimitry Andric       // of the step recurrence.
4295ffd83dbSDimitry Andric       const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn);
4305ffd83dbSDimitry Andric       const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;
4315ffd83dbSDimitry Andric 
4325ffd83dbSDimitry Andric       if (StepRec && SE.isKnownNegative(StepRec))
4335ffd83dbSDimitry Andric         AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(),
4345ffd83dbSDimitry Andric                                     SE.getNegativeSCEV(StepRec),
4355ffd83dbSDimitry Andric                                     AccessFnAR->getLoop(),
4365ffd83dbSDimitry Andric                                     AccessFnAR->getNoWrapFlags());
4378bcb0991SDimitry Andric       const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);
4388bcb0991SDimitry Andric       Subscripts.push_back(Div);
4398bcb0991SDimitry Andric       Sizes.push_back(ElemSize);
4408bcb0991SDimitry Andric     }
4418bcb0991SDimitry Andric 
4428bcb0991SDimitry Andric     return all_of(Subscripts, [&](const SCEV *Subscript) {
4438bcb0991SDimitry Andric       return isSimpleAddRecurrence(*Subscript, *L);
4448bcb0991SDimitry Andric     });
4458bcb0991SDimitry Andric   }
4468bcb0991SDimitry Andric 
4478bcb0991SDimitry Andric   return false;
4488bcb0991SDimitry Andric }
4498bcb0991SDimitry Andric 
isLoopInvariant(const Loop & L) const4508bcb0991SDimitry Andric bool IndexedReference::isLoopInvariant(const Loop &L) const {
4518bcb0991SDimitry Andric   Value *Addr = getPointerOperand(&StoreOrLoadInst);
4528bcb0991SDimitry Andric   assert(Addr != nullptr && "Expecting either a load or a store instruction");
4538bcb0991SDimitry Andric   assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");
4548bcb0991SDimitry Andric 
4558bcb0991SDimitry Andric   if (SE.isLoopInvariant(SE.getSCEV(Addr), &L))
4568bcb0991SDimitry Andric     return true;
4578bcb0991SDimitry Andric 
4588bcb0991SDimitry Andric   // The indexed reference is loop invariant if none of the coefficients use
4598bcb0991SDimitry Andric   // the loop induction variable.
4608bcb0991SDimitry Andric   bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) {
4618bcb0991SDimitry Andric     return isCoeffForLoopZeroOrInvariant(*Subscript, L);
4628bcb0991SDimitry Andric   });
4638bcb0991SDimitry Andric 
4648bcb0991SDimitry Andric   return allCoeffForLoopAreZero;
4658bcb0991SDimitry Andric }
4668bcb0991SDimitry Andric 
isConsecutive(const Loop & L,const SCEV * & Stride,unsigned CLS) const467fcaf7f86SDimitry Andric bool IndexedReference::isConsecutive(const Loop &L, const SCEV *&Stride,
468fcaf7f86SDimitry Andric                                      unsigned CLS) const {
4698bcb0991SDimitry Andric   // The indexed reference is 'consecutive' if the only coefficient that uses
4708bcb0991SDimitry Andric   // the loop induction variable is the last one...
4718bcb0991SDimitry Andric   const SCEV *LastSubscript = Subscripts.back();
4728bcb0991SDimitry Andric   for (const SCEV *Subscript : Subscripts) {
4738bcb0991SDimitry Andric     if (Subscript == LastSubscript)
4748bcb0991SDimitry Andric       continue;
4758bcb0991SDimitry Andric     if (!isCoeffForLoopZeroOrInvariant(*Subscript, L))
4768bcb0991SDimitry Andric       return false;
4778bcb0991SDimitry Andric   }
4788bcb0991SDimitry Andric 
4798bcb0991SDimitry Andric   // ...and the access stride is less than the cache line size.
4808bcb0991SDimitry Andric   const SCEV *Coeff = getLastCoefficient();
4818bcb0991SDimitry Andric   const SCEV *ElemSize = Sizes.back();
482fcaf7f86SDimitry Andric   Type *WiderType = SE.getWiderType(Coeff->getType(), ElemSize->getType());
483fcaf7f86SDimitry Andric   // FIXME: This assumes that all values are signed integers which may
484fcaf7f86SDimitry Andric   // be incorrect in unusual codes and incorrectly use sext instead of zext.
485fcaf7f86SDimitry Andric   // for (uint32_t i = 0; i < 512; ++i) {
486fcaf7f86SDimitry Andric   //   uint8_t trunc = i;
487fcaf7f86SDimitry Andric   //   A[trunc] = 42;
488fcaf7f86SDimitry Andric   // }
489fcaf7f86SDimitry Andric   // This consecutively iterates twice over A. If `trunc` is sign-extended,
490fcaf7f86SDimitry Andric   // we would conclude that this may iterate backwards over the array.
491fcaf7f86SDimitry Andric   // However, LoopCacheAnalysis is heuristic anyway and transformations must
492fcaf7f86SDimitry Andric   // not result in wrong optimizations if the heuristic was incorrect.
493fcaf7f86SDimitry Andric   Stride = SE.getMulExpr(SE.getNoopOrSignExtend(Coeff, WiderType),
494fcaf7f86SDimitry Andric                          SE.getNoopOrSignExtend(ElemSize, WiderType));
4958bcb0991SDimitry Andric   const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
4968bcb0991SDimitry Andric 
4975ffd83dbSDimitry Andric   Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;
4988bcb0991SDimitry Andric   return SE.isKnownPredicate(ICmpInst::ICMP_ULT, Stride, CacheLineSize);
4998bcb0991SDimitry Andric }
5008bcb0991SDimitry Andric 
getSubscriptIndex(const Loop & L) const50181ad6265SDimitry Andric int IndexedReference::getSubscriptIndex(const Loop &L) const {
50281ad6265SDimitry Andric   for (auto Idx : seq<int>(0, getNumSubscripts())) {
50381ad6265SDimitry Andric     const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(Idx));
50481ad6265SDimitry Andric     if (AR && AR->getLoop() == &L) {
50581ad6265SDimitry Andric       return Idx;
50681ad6265SDimitry Andric     }
50781ad6265SDimitry Andric   }
50881ad6265SDimitry Andric   return -1;
50981ad6265SDimitry Andric }
51081ad6265SDimitry Andric 
getLastCoefficient() const5118bcb0991SDimitry Andric const SCEV *IndexedReference::getLastCoefficient() const {
5128bcb0991SDimitry Andric   const SCEV *LastSubscript = getLastSubscript();
513349cc55cSDimitry Andric   auto *AR = cast<SCEVAddRecExpr>(LastSubscript);
5148bcb0991SDimitry Andric   return AR->getStepRecurrence(SE);
5158bcb0991SDimitry Andric }
5168bcb0991SDimitry Andric 
isCoeffForLoopZeroOrInvariant(const SCEV & Subscript,const Loop & L) const5178bcb0991SDimitry Andric bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
5188bcb0991SDimitry Andric                                                      const Loop &L) const {
5198bcb0991SDimitry Andric   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript);
5208bcb0991SDimitry Andric   return (AR != nullptr) ? AR->getLoop() != &L
5218bcb0991SDimitry Andric                          : SE.isLoopInvariant(&Subscript, &L);
5228bcb0991SDimitry Andric }
5238bcb0991SDimitry Andric 
isSimpleAddRecurrence(const SCEV & Subscript,const Loop & L) const5248bcb0991SDimitry Andric bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,
5258bcb0991SDimitry Andric                                              const Loop &L) const {
5268bcb0991SDimitry Andric   if (!isa<SCEVAddRecExpr>(Subscript))
5278bcb0991SDimitry Andric     return false;
5288bcb0991SDimitry Andric 
5298bcb0991SDimitry Andric   const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript);
5308bcb0991SDimitry Andric   assert(AR->getLoop() && "AR should have a loop");
5318bcb0991SDimitry Andric 
5328bcb0991SDimitry Andric   if (!AR->isAffine())
5338bcb0991SDimitry Andric     return false;
5348bcb0991SDimitry Andric 
5358bcb0991SDimitry Andric   const SCEV *Start = AR->getStart();
5368bcb0991SDimitry Andric   const SCEV *Step = AR->getStepRecurrence(SE);
5378bcb0991SDimitry Andric 
5388bcb0991SDimitry Andric   if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))
5398bcb0991SDimitry Andric     return false;
5408bcb0991SDimitry Andric 
5418bcb0991SDimitry Andric   return true;
5428bcb0991SDimitry Andric }
5438bcb0991SDimitry Andric 
isAliased(const IndexedReference & Other,AAResults & AA) const5448bcb0991SDimitry Andric bool IndexedReference::isAliased(const IndexedReference &Other,
545e8d8bef9SDimitry Andric                                  AAResults &AA) const {
5468bcb0991SDimitry Andric   const auto &Loc1 = MemoryLocation::get(&StoreOrLoadInst);
5478bcb0991SDimitry Andric   const auto &Loc2 = MemoryLocation::get(&Other.StoreOrLoadInst);
5488bcb0991SDimitry Andric   return AA.isMustAlias(Loc1, Loc2);
5498bcb0991SDimitry Andric }
5508bcb0991SDimitry Andric 
5518bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
5528bcb0991SDimitry Andric // CacheCost implementation
5538bcb0991SDimitry Andric //
operator <<(raw_ostream & OS,const CacheCost & CC)5548bcb0991SDimitry Andric raw_ostream &llvm::operator<<(raw_ostream &OS, const CacheCost &CC) {
5558bcb0991SDimitry Andric   for (const auto &LC : CC.LoopCosts) {
5568bcb0991SDimitry Andric     const Loop *L = LC.first;
5578bcb0991SDimitry Andric     OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";
5588bcb0991SDimitry Andric   }
5598bcb0991SDimitry Andric   return OS;
5608bcb0991SDimitry Andric }
5618bcb0991SDimitry Andric 
CacheCost(const LoopVectorTy & Loops,const LoopInfo & LI,ScalarEvolution & SE,TargetTransformInfo & TTI,AAResults & AA,DependenceInfo & DI,std::optional<unsigned> TRT)5628bcb0991SDimitry Andric CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI,
5638bcb0991SDimitry Andric                      ScalarEvolution &SE, TargetTransformInfo &TTI,
564bdd1243dSDimitry Andric                      AAResults &AA, DependenceInfo &DI,
565bdd1243dSDimitry Andric                      std::optional<unsigned> TRT)
566bdd1243dSDimitry Andric     : Loops(Loops), TRT(TRT.value_or(TemporalReuseThreshold)), LI(LI), SE(SE),
567bdd1243dSDimitry Andric       TTI(TTI), AA(AA), DI(DI) {
5688bcb0991SDimitry Andric   assert(!Loops.empty() && "Expecting a non-empty loop vector.");
5698bcb0991SDimitry Andric 
5708bcb0991SDimitry Andric   for (const Loop *L : Loops) {
5718bcb0991SDimitry Andric     unsigned TripCount = SE.getSmallConstantTripCount(L);
5728bcb0991SDimitry Andric     TripCount = (TripCount == 0) ? DefaultTripCount : TripCount;
5738bcb0991SDimitry Andric     TripCounts.push_back({L, TripCount});
5748bcb0991SDimitry Andric   }
5758bcb0991SDimitry Andric 
5768bcb0991SDimitry Andric   calculateCacheFootprint();
5778bcb0991SDimitry Andric }
5788bcb0991SDimitry Andric 
5798bcb0991SDimitry Andric std::unique_ptr<CacheCost>
getCacheCost(Loop & Root,LoopStandardAnalysisResults & AR,DependenceInfo & DI,std::optional<unsigned> TRT)5808bcb0991SDimitry Andric CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR,
581bdd1243dSDimitry Andric                         DependenceInfo &DI, std::optional<unsigned> TRT) {
582e8d8bef9SDimitry Andric   if (!Root.isOutermost()) {
5838bcb0991SDimitry Andric     LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");
5848bcb0991SDimitry Andric     return nullptr;
5858bcb0991SDimitry Andric   }
5868bcb0991SDimitry Andric 
5878bcb0991SDimitry Andric   LoopVectorTy Loops;
588e8d8bef9SDimitry Andric   append_range(Loops, breadth_first(&Root));
5898bcb0991SDimitry Andric 
5908bcb0991SDimitry Andric   if (!getInnerMostLoop(Loops)) {
5918bcb0991SDimitry Andric     LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "
5928bcb0991SDimitry Andric                          "than one innermost loop\n");
5938bcb0991SDimitry Andric     return nullptr;
5948bcb0991SDimitry Andric   }
5958bcb0991SDimitry Andric 
5968bcb0991SDimitry Andric   return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);
5978bcb0991SDimitry Andric }
5988bcb0991SDimitry Andric 
calculateCacheFootprint()5998bcb0991SDimitry Andric void CacheCost::calculateCacheFootprint() {
6008bcb0991SDimitry Andric   LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n");
6018bcb0991SDimitry Andric   ReferenceGroupsTy RefGroups;
6028bcb0991SDimitry Andric   if (!populateReferenceGroups(RefGroups))
6038bcb0991SDimitry Andric     return;
6048bcb0991SDimitry Andric 
6058bcb0991SDimitry Andric   LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n");
6068bcb0991SDimitry Andric   for (const Loop *L : Loops) {
607349cc55cSDimitry Andric     assert(llvm::none_of(
608349cc55cSDimitry Andric                LoopCosts,
609349cc55cSDimitry Andric                [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) &&
6108bcb0991SDimitry Andric            "Should not add duplicate element");
6118bcb0991SDimitry Andric     CacheCostTy LoopCost = computeLoopCacheCost(*L, RefGroups);
6128bcb0991SDimitry Andric     LoopCosts.push_back(std::make_pair(L, LoopCost));
6138bcb0991SDimitry Andric   }
6148bcb0991SDimitry Andric 
6158bcb0991SDimitry Andric   sortLoopCosts();
6168bcb0991SDimitry Andric   RefGroups.clear();
6178bcb0991SDimitry Andric }
6188bcb0991SDimitry Andric 
populateReferenceGroups(ReferenceGroupsTy & RefGroups) const6198bcb0991SDimitry Andric bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const {
6208bcb0991SDimitry Andric   assert(RefGroups.empty() && "Reference groups should be empty");
6218bcb0991SDimitry Andric 
6228bcb0991SDimitry Andric   unsigned CLS = TTI.getCacheLineSize();
6238bcb0991SDimitry Andric   Loop *InnerMostLoop = getInnerMostLoop(Loops);
6248bcb0991SDimitry Andric   assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop");
6258bcb0991SDimitry Andric 
6268bcb0991SDimitry Andric   for (BasicBlock *BB : InnerMostLoop->getBlocks()) {
6278bcb0991SDimitry Andric     for (Instruction &I : *BB) {
6288bcb0991SDimitry Andric       if (!isa<StoreInst>(I) && !isa<LoadInst>(I))
6298bcb0991SDimitry Andric         continue;
6308bcb0991SDimitry Andric 
6318bcb0991SDimitry Andric       std::unique_ptr<IndexedReference> R(new IndexedReference(I, LI, SE));
6328bcb0991SDimitry Andric       if (!R->isValid())
6338bcb0991SDimitry Andric         continue;
6348bcb0991SDimitry Andric 
6358bcb0991SDimitry Andric       bool Added = false;
6368bcb0991SDimitry Andric       for (ReferenceGroupTy &RefGroup : RefGroups) {
63781ad6265SDimitry Andric         const IndexedReference &Representative = *RefGroup.front();
6388bcb0991SDimitry Andric         LLVM_DEBUG({
6398bcb0991SDimitry Andric           dbgs() << "References:\n";
6408bcb0991SDimitry Andric           dbgs().indent(2) << *R << "\n";
6418bcb0991SDimitry Andric           dbgs().indent(2) << Representative << "\n";
6428bcb0991SDimitry Andric         });
6438bcb0991SDimitry Andric 
6445ffd83dbSDimitry Andric 
6455ffd83dbSDimitry Andric        // FIXME: Both positive and negative access functions will be placed
6465ffd83dbSDimitry Andric        // into the same reference group, resulting in a bi-directional array
6475ffd83dbSDimitry Andric        // access such as:
6485ffd83dbSDimitry Andric        //   for (i = N; i > 0; i--)
6495ffd83dbSDimitry Andric        //     A[i] = A[N - i];
6505ffd83dbSDimitry Andric        // having the same cost calculation as a single dimention access pattern
6515ffd83dbSDimitry Andric        //   for (i = 0; i < N; i++)
6525ffd83dbSDimitry Andric        //     A[i] = A[i];
6535ffd83dbSDimitry Andric        // when in actuality, depending on the array size, the first example
6545ffd83dbSDimitry Andric        // should have a cost closer to 2x the second due to the two cache
6555ffd83dbSDimitry Andric        // access per iteration from opposite ends of the array
656bdd1243dSDimitry Andric         std::optional<bool> HasTemporalReuse =
6578bcb0991SDimitry Andric             R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);
658bdd1243dSDimitry Andric         std::optional<bool> HasSpacialReuse =
6598bcb0991SDimitry Andric             R->hasSpacialReuse(Representative, CLS, AA);
6608bcb0991SDimitry Andric 
66181ad6265SDimitry Andric         if ((HasTemporalReuse && *HasTemporalReuse) ||
66281ad6265SDimitry Andric             (HasSpacialReuse && *HasSpacialReuse)) {
6638bcb0991SDimitry Andric           RefGroup.push_back(std::move(R));
6648bcb0991SDimitry Andric           Added = true;
6658bcb0991SDimitry Andric           break;
6668bcb0991SDimitry Andric         }
6678bcb0991SDimitry Andric       }
6688bcb0991SDimitry Andric 
6698bcb0991SDimitry Andric       if (!Added) {
6708bcb0991SDimitry Andric         ReferenceGroupTy RG;
6718bcb0991SDimitry Andric         RG.push_back(std::move(R));
6728bcb0991SDimitry Andric         RefGroups.push_back(std::move(RG));
6738bcb0991SDimitry Andric       }
6748bcb0991SDimitry Andric     }
6758bcb0991SDimitry Andric   }
6768bcb0991SDimitry Andric 
6778bcb0991SDimitry Andric   if (RefGroups.empty())
6788bcb0991SDimitry Andric     return false;
6798bcb0991SDimitry Andric 
6808bcb0991SDimitry Andric   LLVM_DEBUG({
6818bcb0991SDimitry Andric     dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";
6828bcb0991SDimitry Andric     int n = 1;
6838bcb0991SDimitry Andric     for (const ReferenceGroupTy &RG : RefGroups) {
6848bcb0991SDimitry Andric       dbgs().indent(2) << "RefGroup " << n << ":\n";
6858bcb0991SDimitry Andric       for (const auto &IR : RG)
6868bcb0991SDimitry Andric         dbgs().indent(4) << *IR << "\n";
6878bcb0991SDimitry Andric       n++;
6888bcb0991SDimitry Andric     }
6898bcb0991SDimitry Andric     dbgs() << "\n";
6908bcb0991SDimitry Andric   });
6918bcb0991SDimitry Andric 
6928bcb0991SDimitry Andric   return true;
6938bcb0991SDimitry Andric }
6948bcb0991SDimitry Andric 
6958bcb0991SDimitry Andric CacheCostTy
computeLoopCacheCost(const Loop & L,const ReferenceGroupsTy & RefGroups) const6968bcb0991SDimitry Andric CacheCost::computeLoopCacheCost(const Loop &L,
6978bcb0991SDimitry Andric                                 const ReferenceGroupsTy &RefGroups) const {
6988bcb0991SDimitry Andric   if (!L.isLoopSimplifyForm())
6998bcb0991SDimitry Andric     return InvalidCost;
7008bcb0991SDimitry Andric 
7018bcb0991SDimitry Andric   LLVM_DEBUG(dbgs() << "Considering loop '" << L.getName()
7028bcb0991SDimitry Andric                     << "' as innermost loop.\n");
7038bcb0991SDimitry Andric 
7048bcb0991SDimitry Andric   // Compute the product of the trip counts of each other loop in the nest.
7058bcb0991SDimitry Andric   CacheCostTy TripCountsProduct = 1;
7068bcb0991SDimitry Andric   for (const auto &TC : TripCounts) {
7078bcb0991SDimitry Andric     if (TC.first == &L)
7088bcb0991SDimitry Andric       continue;
7098bcb0991SDimitry Andric     TripCountsProduct *= TC.second;
7108bcb0991SDimitry Andric   }
7118bcb0991SDimitry Andric 
7128bcb0991SDimitry Andric   CacheCostTy LoopCost = 0;
7138bcb0991SDimitry Andric   for (const ReferenceGroupTy &RG : RefGroups) {
7148bcb0991SDimitry Andric     CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);
7158bcb0991SDimitry Andric     LoopCost += RefGroupCost * TripCountsProduct;
7168bcb0991SDimitry Andric   }
7178bcb0991SDimitry Andric 
7188bcb0991SDimitry Andric   LLVM_DEBUG(dbgs().indent(2) << "Loop '" << L.getName()
7198bcb0991SDimitry Andric                               << "' has cost=" << LoopCost << "\n");
7208bcb0991SDimitry Andric 
7218bcb0991SDimitry Andric   return LoopCost;
7228bcb0991SDimitry Andric }
7238bcb0991SDimitry Andric 
computeRefGroupCacheCost(const ReferenceGroupTy & RG,const Loop & L) const7248bcb0991SDimitry Andric CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG,
7258bcb0991SDimitry Andric                                                 const Loop &L) const {
7268bcb0991SDimitry Andric   assert(!RG.empty() && "Reference group should have at least one member.");
7278bcb0991SDimitry Andric 
7288bcb0991SDimitry Andric   const IndexedReference *Representative = RG.front().get();
7298bcb0991SDimitry Andric   return Representative->computeRefCost(L, TTI.getCacheLineSize());
7308bcb0991SDimitry Andric }
7318bcb0991SDimitry Andric 
7328bcb0991SDimitry Andric //===----------------------------------------------------------------------===//
7338bcb0991SDimitry Andric // LoopCachePrinterPass implementation
7348bcb0991SDimitry Andric //
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & U)7358bcb0991SDimitry Andric PreservedAnalyses LoopCachePrinterPass::run(Loop &L, LoopAnalysisManager &AM,
7368bcb0991SDimitry Andric                                             LoopStandardAnalysisResults &AR,
7378bcb0991SDimitry Andric                                             LPMUpdater &U) {
7388bcb0991SDimitry Andric   Function *F = L.getHeader()->getParent();
7398bcb0991SDimitry Andric   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
7408bcb0991SDimitry Andric 
7418bcb0991SDimitry Andric   if (auto CC = CacheCost::getCacheCost(L, AR, DI))
7428bcb0991SDimitry Andric     OS << *CC;
7438bcb0991SDimitry Andric 
7448bcb0991SDimitry Andric   return PreservedAnalyses::all();
7458bcb0991SDimitry Andric }
746