xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp (revision 0d8fe2373503aeac48492f28073049a8bfa4feb5)
1 //===- LoopCacheAnalysis.cpp - Loop Cache Analysis -------------------------==//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
6 // See https://llvm.org/LICENSE.txt for license information.
7 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
8 //
9 //===----------------------------------------------------------------------===//
10 ///
11 /// \file
12 /// This file defines the implementation for the loop cache analysis.
13 /// The implementation is largely based on the following paper:
14 ///
15 ///       Compiler Optimizations for Improving Data Locality
16 ///       By: Steve Carr, Katherine S. McKinley, Chau-Wen Tseng
17 ///       http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf
18 ///
19 /// The general approach taken to estimate the number of cache lines used by the
20 /// memory references in an inner loop is:
21 ///    1. Partition memory references that exhibit temporal or spacial reuse
22 ///       into reference groups.
23 ///    2. For each loop L in the a loop nest LN:
24 ///       a. Compute the cost of the reference group
25 ///       b. Compute the loop cost by summing up the reference groups costs
26 //===----------------------------------------------------------------------===//
27 
28 #include "llvm/Analysis/LoopCacheAnalysis.h"
29 #include "llvm/ADT/BreadthFirstIterator.h"
30 #include "llvm/ADT/Sequence.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Analysis/AliasAnalysis.h"
33 #include "llvm/Analysis/DependenceAnalysis.h"
34 #include "llvm/Analysis/LoopInfo.h"
35 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
36 #include "llvm/Analysis/TargetTransformInfo.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "loop-cache-cost"
43 
44 static cl::opt<unsigned> DefaultTripCount(
45     "default-trip-count", cl::init(100), cl::Hidden,
46     cl::desc("Use this to specify the default trip count of a loop"));
47 
48 // In this analysis two array references are considered to exhibit temporal
49 // reuse if they access either the same memory location, or a memory location
50 // with distance smaller than a configurable threshold.
51 static cl::opt<unsigned> TemporalReuseThreshold(
52     "temporal-reuse-threshold", cl::init(2), cl::Hidden,
53     cl::desc("Use this to specify the max. distance between array elements "
54              "accessed in a loop so that the elements are classified to have "
55              "temporal reuse"));
56 
57 /// Retrieve the innermost loop in the given loop nest \p Loops. It returns a
58 /// nullptr if any loops in the loop vector supplied has more than one sibling.
59 /// The loop vector is expected to contain loops collected in breadth-first
60 /// order.
61 static Loop *getInnerMostLoop(const LoopVectorTy &Loops) {
62   assert(!Loops.empty() && "Expecting a non-empy loop vector");
63 
64   Loop *LastLoop = Loops.back();
65   Loop *ParentLoop = LastLoop->getParentLoop();
66 
67   if (ParentLoop == nullptr) {
68     assert(Loops.size() == 1 && "Expecting a single loop");
69     return LastLoop;
70   }
71 
72   return (llvm::is_sorted(Loops,
73                           [](const Loop *L1, const Loop *L2) {
74                             return L1->getLoopDepth() < L2->getLoopDepth();
75                           }))
76              ? LastLoop
77              : nullptr;
78 }
79 
80 static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize,
81                                   const Loop &L, ScalarEvolution &SE) {
82   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&AccessFn);
83   if (!AR || !AR->isAffine())
84     return false;
85 
86   assert(AR->getLoop() && "AR should have a loop");
87 
88   // Check that start and increment are not add recurrences.
89   const SCEV *Start = AR->getStart();
90   const SCEV *Step = AR->getStepRecurrence(SE);
91   if (isa<SCEVAddRecExpr>(Start) || isa<SCEVAddRecExpr>(Step))
92     return false;
93 
94   // Check that start and increment are both invariant in the loop.
95   if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))
96     return false;
97 
98   const SCEV *StepRec = AR->getStepRecurrence(SE);
99   if (StepRec && SE.isKnownNegative(StepRec))
100     StepRec = SE.getNegativeSCEV(StepRec);
101 
102   return StepRec == &ElemSize;
103 }
104 
105 /// Compute the trip count for the given loop \p L. Return the SCEV expression
106 /// for the trip count or nullptr if it cannot be computed.
107 static const SCEV *computeTripCount(const Loop &L, ScalarEvolution &SE) {
108   const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(&L);
109   if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) ||
110       !isa<SCEVConstant>(BackedgeTakenCount))
111     return nullptr;
112 
113   return SE.getAddExpr(BackedgeTakenCount,
114                        SE.getOne(BackedgeTakenCount->getType()));
115 }
116 
117 //===----------------------------------------------------------------------===//
118 // IndexedReference implementation
119 //
120 raw_ostream &llvm::operator<<(raw_ostream &OS, const IndexedReference &R) {
121   if (!R.IsValid) {
122     OS << R.StoreOrLoadInst;
123     OS << ", IsValid=false.";
124     return OS;
125   }
126 
127   OS << *R.BasePointer;
128   for (const SCEV *Subscript : R.Subscripts)
129     OS << "[" << *Subscript << "]";
130 
131   OS << ", Sizes: ";
132   for (const SCEV *Size : R.Sizes)
133     OS << "[" << *Size << "]";
134 
135   return OS;
136 }
137 
138 IndexedReference::IndexedReference(Instruction &StoreOrLoadInst,
139                                    const LoopInfo &LI, ScalarEvolution &SE)
140     : StoreOrLoadInst(StoreOrLoadInst), SE(SE) {
141   assert((isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst>(StoreOrLoadInst)) &&
142          "Expecting a load or store instruction");
143 
144   IsValid = delinearize(LI);
145   if (IsValid)
146     LLVM_DEBUG(dbgs().indent(2) << "Succesfully delinearized: " << *this
147                                 << "\n");
148 }
149 
150 Optional<bool> IndexedReference::hasSpacialReuse(const IndexedReference &Other,
151                                                  unsigned CLS,
152                                                  AAResults &AA) const {
153   assert(IsValid && "Expecting a valid reference");
154 
155   if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
156     LLVM_DEBUG(dbgs().indent(2)
157                << "No spacial reuse: different base pointers\n");
158     return false;
159   }
160 
161   unsigned NumSubscripts = getNumSubscripts();
162   if (NumSubscripts != Other.getNumSubscripts()) {
163     LLVM_DEBUG(dbgs().indent(2)
164                << "No spacial reuse: different number of subscripts\n");
165     return false;
166   }
167 
168   // all subscripts must be equal, except the leftmost one (the last one).
169   for (auto SubNum : seq<unsigned>(0, NumSubscripts - 1)) {
170     if (getSubscript(SubNum) != Other.getSubscript(SubNum)) {
171       LLVM_DEBUG(dbgs().indent(2) << "No spacial reuse, different subscripts: "
172                                   << "\n\t" << *getSubscript(SubNum) << "\n\t"
173                                   << *Other.getSubscript(SubNum) << "\n");
174       return false;
175     }
176   }
177 
178   // the difference between the last subscripts must be less than the cache line
179   // size.
180   const SCEV *LastSubscript = getLastSubscript();
181   const SCEV *OtherLastSubscript = Other.getLastSubscript();
182   const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
183       SE.getMinusSCEV(LastSubscript, OtherLastSubscript));
184 
185   if (Diff == nullptr) {
186     LLVM_DEBUG(dbgs().indent(2)
187                << "No spacial reuse, difference between subscript:\n\t"
188                << *LastSubscript << "\n\t" << OtherLastSubscript
189                << "\nis not constant.\n");
190     return None;
191   }
192 
193   bool InSameCacheLine = (Diff->getValue()->getSExtValue() < CLS);
194 
195   LLVM_DEBUG({
196     if (InSameCacheLine)
197       dbgs().indent(2) << "Found spacial reuse.\n";
198     else
199       dbgs().indent(2) << "No spacial reuse.\n";
200   });
201 
202   return InSameCacheLine;
203 }
204 
205 Optional<bool> IndexedReference::hasTemporalReuse(const IndexedReference &Other,
206                                                   unsigned MaxDistance,
207                                                   const Loop &L,
208                                                   DependenceInfo &DI,
209                                                   AAResults &AA) const {
210   assert(IsValid && "Expecting a valid reference");
211 
212   if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
213     LLVM_DEBUG(dbgs().indent(2)
214                << "No temporal reuse: different base pointer\n");
215     return false;
216   }
217 
218   std::unique_ptr<Dependence> D =
219       DI.depends(&StoreOrLoadInst, &Other.StoreOrLoadInst, true);
220 
221   if (D == nullptr) {
222     LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: no dependence\n");
223     return false;
224   }
225 
226   if (D->isLoopIndependent()) {
227     LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
228     return true;
229   }
230 
231   // Check the dependence distance at every loop level. There is temporal reuse
232   // if the distance at the given loop's depth is small (|d| <= MaxDistance) and
233   // it is zero at every other loop level.
234   int LoopDepth = L.getLoopDepth();
235   int Levels = D->getLevels();
236   for (int Level = 1; Level <= Levels; ++Level) {
237     const SCEV *Distance = D->getDistance(Level);
238     const SCEVConstant *SCEVConst = dyn_cast_or_null<SCEVConstant>(Distance);
239 
240     if (SCEVConst == nullptr) {
241       LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: distance unknown\n");
242       return None;
243     }
244 
245     const ConstantInt &CI = *SCEVConst->getValue();
246     if (Level != LoopDepth && !CI.isZero()) {
247       LLVM_DEBUG(dbgs().indent(2)
248                  << "No temporal reuse: distance is not zero at depth=" << Level
249                  << "\n");
250       return false;
251     } else if (Level == LoopDepth && CI.getSExtValue() > MaxDistance) {
252       LLVM_DEBUG(
253           dbgs().indent(2)
254           << "No temporal reuse: distance is greater than MaxDistance at depth="
255           << Level << "\n");
256       return false;
257     }
258   }
259 
260   LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
261   return true;
262 }
263 
264 CacheCostTy IndexedReference::computeRefCost(const Loop &L,
265                                              unsigned CLS) const {
266   assert(IsValid && "Expecting a valid reference");
267   LLVM_DEBUG({
268     dbgs().indent(2) << "Computing cache cost for:\n";
269     dbgs().indent(4) << *this << "\n";
270   });
271 
272   // If the indexed reference is loop invariant the cost is one.
273   if (isLoopInvariant(L)) {
274     LLVM_DEBUG(dbgs().indent(4) << "Reference is loop invariant: RefCost=1\n");
275     return 1;
276   }
277 
278   const SCEV *TripCount = computeTripCount(L, SE);
279   if (!TripCount) {
280     LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName()
281                       << " could not be computed, using DefaultTripCount\n");
282     const SCEV *ElemSize = Sizes.back();
283     TripCount = SE.getConstant(ElemSize->getType(), DefaultTripCount);
284   }
285   LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n");
286 
287   // If the indexed reference is 'consecutive' the cost is
288   // (TripCount*Stride)/CLS, otherwise the cost is TripCount.
289   const SCEV *RefCost = TripCount;
290 
291   if (isConsecutive(L, CLS)) {
292     const SCEV *Coeff = getLastCoefficient();
293     const SCEV *ElemSize = Sizes.back();
294     const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize);
295     const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
296     Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());
297     if (SE.isKnownNegative(Stride))
298       Stride = SE.getNegativeSCEV(Stride);
299     Stride = SE.getNoopOrAnyExtend(Stride, WiderType);
300     TripCount = SE.getNoopOrAnyExtend(TripCount, WiderType);
301     const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);
302     RefCost = SE.getUDivExpr(Numerator, CacheLineSize);
303 
304     LLVM_DEBUG(dbgs().indent(4)
305                << "Access is consecutive: RefCost=(TripCount*Stride)/CLS="
306                << *RefCost << "\n");
307   } else
308     LLVM_DEBUG(dbgs().indent(4)
309                << "Access is not consecutive: RefCost=TripCount=" << *RefCost
310                << "\n");
311 
312   // Attempt to fold RefCost into a constant.
313   if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost))
314     return ConstantCost->getValue()->getSExtValue();
315 
316   LLVM_DEBUG(dbgs().indent(4)
317              << "RefCost is not a constant! Setting to RefCost=InvalidCost "
318                 "(invalid value).\n");
319 
320   return CacheCost::InvalidCost;
321 }
322 
323 bool IndexedReference::delinearize(const LoopInfo &LI) {
324   assert(Subscripts.empty() && "Subscripts should be empty");
325   assert(Sizes.empty() && "Sizes should be empty");
326   assert(!IsValid && "Should be called once from the constructor");
327   LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");
328 
329   const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);
330   const BasicBlock *BB = StoreOrLoadInst.getParent();
331 
332   if (Loop *L = LI.getLoopFor(BB)) {
333     const SCEV *AccessFn =
334         SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L);
335 
336     BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));
337     if (BasePointer == nullptr) {
338       LLVM_DEBUG(
339           dbgs().indent(2)
340           << "ERROR: failed to delinearize, can't identify base pointer\n");
341       return false;
342     }
343 
344     AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
345 
346     LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
347                                 << "', AccessFn: " << *AccessFn << "\n");
348 
349     SE.delinearize(AccessFn, Subscripts, Sizes,
350                    SE.getElementSize(&StoreOrLoadInst));
351 
352     if (Subscripts.empty() || Sizes.empty() ||
353         Subscripts.size() != Sizes.size()) {
354       // Attempt to determine whether we have a single dimensional array access.
355       // before giving up.
356       if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {
357         LLVM_DEBUG(dbgs().indent(2)
358                    << "ERROR: failed to delinearize reference\n");
359         Subscripts.clear();
360         Sizes.clear();
361         return false;
362       }
363 
364       // The array may be accessed in reverse, for example:
365       //   for (i = N; i > 0; i--)
366       //     A[i] = 0;
367       // In this case, reconstruct the access function using the absolute value
368       // of the step recurrence.
369       const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn);
370       const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;
371 
372       if (StepRec && SE.isKnownNegative(StepRec))
373         AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(),
374                                     SE.getNegativeSCEV(StepRec),
375                                     AccessFnAR->getLoop(),
376                                     AccessFnAR->getNoWrapFlags());
377       const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);
378       Subscripts.push_back(Div);
379       Sizes.push_back(ElemSize);
380     }
381 
382     return all_of(Subscripts, [&](const SCEV *Subscript) {
383       return isSimpleAddRecurrence(*Subscript, *L);
384     });
385   }
386 
387   return false;
388 }
389 
390 bool IndexedReference::isLoopInvariant(const Loop &L) const {
391   Value *Addr = getPointerOperand(&StoreOrLoadInst);
392   assert(Addr != nullptr && "Expecting either a load or a store instruction");
393   assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");
394 
395   if (SE.isLoopInvariant(SE.getSCEV(Addr), &L))
396     return true;
397 
398   // The indexed reference is loop invariant if none of the coefficients use
399   // the loop induction variable.
400   bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) {
401     return isCoeffForLoopZeroOrInvariant(*Subscript, L);
402   });
403 
404   return allCoeffForLoopAreZero;
405 }
406 
407 bool IndexedReference::isConsecutive(const Loop &L, unsigned CLS) const {
408   // The indexed reference is 'consecutive' if the only coefficient that uses
409   // the loop induction variable is the last one...
410   const SCEV *LastSubscript = Subscripts.back();
411   for (const SCEV *Subscript : Subscripts) {
412     if (Subscript == LastSubscript)
413       continue;
414     if (!isCoeffForLoopZeroOrInvariant(*Subscript, L))
415       return false;
416   }
417 
418   // ...and the access stride is less than the cache line size.
419   const SCEV *Coeff = getLastCoefficient();
420   const SCEV *ElemSize = Sizes.back();
421   const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize);
422   const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
423 
424   Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;
425   return SE.isKnownPredicate(ICmpInst::ICMP_ULT, Stride, CacheLineSize);
426 }
427 
428 const SCEV *IndexedReference::getLastCoefficient() const {
429   const SCEV *LastSubscript = getLastSubscript();
430   assert(isa<SCEVAddRecExpr>(LastSubscript) &&
431          "Expecting a SCEV add recurrence expression");
432   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LastSubscript);
433   return AR->getStepRecurrence(SE);
434 }
435 
436 bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
437                                                      const Loop &L) const {
438   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript);
439   return (AR != nullptr) ? AR->getLoop() != &L
440                          : SE.isLoopInvariant(&Subscript, &L);
441 }
442 
443 bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,
444                                              const Loop &L) const {
445   if (!isa<SCEVAddRecExpr>(Subscript))
446     return false;
447 
448   const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript);
449   assert(AR->getLoop() && "AR should have a loop");
450 
451   if (!AR->isAffine())
452     return false;
453 
454   const SCEV *Start = AR->getStart();
455   const SCEV *Step = AR->getStepRecurrence(SE);
456 
457   if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))
458     return false;
459 
460   return true;
461 }
462 
463 bool IndexedReference::isAliased(const IndexedReference &Other,
464                                  AAResults &AA) const {
465   const auto &Loc1 = MemoryLocation::get(&StoreOrLoadInst);
466   const auto &Loc2 = MemoryLocation::get(&Other.StoreOrLoadInst);
467   return AA.isMustAlias(Loc1, Loc2);
468 }
469 
470 //===----------------------------------------------------------------------===//
471 // CacheCost implementation
472 //
473 raw_ostream &llvm::operator<<(raw_ostream &OS, const CacheCost &CC) {
474   for (const auto &LC : CC.LoopCosts) {
475     const Loop *L = LC.first;
476     OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";
477   }
478   return OS;
479 }
480 
481 CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI,
482                      ScalarEvolution &SE, TargetTransformInfo &TTI,
483                      AAResults &AA, DependenceInfo &DI,
484                      Optional<unsigned> TRT)
485     : Loops(Loops), TripCounts(), LoopCosts(),
486       TRT((TRT == None) ? Optional<unsigned>(TemporalReuseThreshold) : TRT),
487       LI(LI), SE(SE), TTI(TTI), AA(AA), DI(DI) {
488   assert(!Loops.empty() && "Expecting a non-empty loop vector.");
489 
490   for (const Loop *L : Loops) {
491     unsigned TripCount = SE.getSmallConstantTripCount(L);
492     TripCount = (TripCount == 0) ? DefaultTripCount : TripCount;
493     TripCounts.push_back({L, TripCount});
494   }
495 
496   calculateCacheFootprint();
497 }
498 
499 std::unique_ptr<CacheCost>
500 CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR,
501                         DependenceInfo &DI, Optional<unsigned> TRT) {
502   if (!Root.isOutermost()) {
503     LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");
504     return nullptr;
505   }
506 
507   LoopVectorTy Loops;
508   append_range(Loops, breadth_first(&Root));
509 
510   if (!getInnerMostLoop(Loops)) {
511     LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "
512                          "than one innermost loop\n");
513     return nullptr;
514   }
515 
516   return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);
517 }
518 
519 void CacheCost::calculateCacheFootprint() {
520   LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n");
521   ReferenceGroupsTy RefGroups;
522   if (!populateReferenceGroups(RefGroups))
523     return;
524 
525   LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n");
526   for (const Loop *L : Loops) {
527     assert((std::find_if(LoopCosts.begin(), LoopCosts.end(),
528                          [L](const LoopCacheCostTy &LCC) {
529                            return LCC.first == L;
530                          }) == LoopCosts.end()) &&
531            "Should not add duplicate element");
532     CacheCostTy LoopCost = computeLoopCacheCost(*L, RefGroups);
533     LoopCosts.push_back(std::make_pair(L, LoopCost));
534   }
535 
536   sortLoopCosts();
537   RefGroups.clear();
538 }
539 
540 bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const {
541   assert(RefGroups.empty() && "Reference groups should be empty");
542 
543   unsigned CLS = TTI.getCacheLineSize();
544   Loop *InnerMostLoop = getInnerMostLoop(Loops);
545   assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop");
546 
547   for (BasicBlock *BB : InnerMostLoop->getBlocks()) {
548     for (Instruction &I : *BB) {
549       if (!isa<StoreInst>(I) && !isa<LoadInst>(I))
550         continue;
551 
552       std::unique_ptr<IndexedReference> R(new IndexedReference(I, LI, SE));
553       if (!R->isValid())
554         continue;
555 
556       bool Added = false;
557       for (ReferenceGroupTy &RefGroup : RefGroups) {
558         const IndexedReference &Representative = *RefGroup.front().get();
559         LLVM_DEBUG({
560           dbgs() << "References:\n";
561           dbgs().indent(2) << *R << "\n";
562           dbgs().indent(2) << Representative << "\n";
563         });
564 
565 
566        // FIXME: Both positive and negative access functions will be placed
567        // into the same reference group, resulting in a bi-directional array
568        // access such as:
569        //   for (i = N; i > 0; i--)
570        //     A[i] = A[N - i];
571        // having the same cost calculation as a single dimention access pattern
572        //   for (i = 0; i < N; i++)
573        //     A[i] = A[i];
574        // when in actuality, depending on the array size, the first example
575        // should have a cost closer to 2x the second due to the two cache
576        // access per iteration from opposite ends of the array
577         Optional<bool> HasTemporalReuse =
578             R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);
579         Optional<bool> HasSpacialReuse =
580             R->hasSpacialReuse(Representative, CLS, AA);
581 
582         if ((HasTemporalReuse.hasValue() && *HasTemporalReuse) ||
583             (HasSpacialReuse.hasValue() && *HasSpacialReuse)) {
584           RefGroup.push_back(std::move(R));
585           Added = true;
586           break;
587         }
588       }
589 
590       if (!Added) {
591         ReferenceGroupTy RG;
592         RG.push_back(std::move(R));
593         RefGroups.push_back(std::move(RG));
594       }
595     }
596   }
597 
598   if (RefGroups.empty())
599     return false;
600 
601   LLVM_DEBUG({
602     dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";
603     int n = 1;
604     for (const ReferenceGroupTy &RG : RefGroups) {
605       dbgs().indent(2) << "RefGroup " << n << ":\n";
606       for (const auto &IR : RG)
607         dbgs().indent(4) << *IR << "\n";
608       n++;
609     }
610     dbgs() << "\n";
611   });
612 
613   return true;
614 }
615 
616 CacheCostTy
617 CacheCost::computeLoopCacheCost(const Loop &L,
618                                 const ReferenceGroupsTy &RefGroups) const {
619   if (!L.isLoopSimplifyForm())
620     return InvalidCost;
621 
622   LLVM_DEBUG(dbgs() << "Considering loop '" << L.getName()
623                     << "' as innermost loop.\n");
624 
625   // Compute the product of the trip counts of each other loop in the nest.
626   CacheCostTy TripCountsProduct = 1;
627   for (const auto &TC : TripCounts) {
628     if (TC.first == &L)
629       continue;
630     TripCountsProduct *= TC.second;
631   }
632 
633   CacheCostTy LoopCost = 0;
634   for (const ReferenceGroupTy &RG : RefGroups) {
635     CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);
636     LoopCost += RefGroupCost * TripCountsProduct;
637   }
638 
639   LLVM_DEBUG(dbgs().indent(2) << "Loop '" << L.getName()
640                               << "' has cost=" << LoopCost << "\n");
641 
642   return LoopCost;
643 }
644 
645 CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG,
646                                                 const Loop &L) const {
647   assert(!RG.empty() && "Reference group should have at least one member.");
648 
649   const IndexedReference *Representative = RG.front().get();
650   return Representative->computeRefCost(L, TTI.getCacheLineSize());
651 }
652 
653 //===----------------------------------------------------------------------===//
654 // LoopCachePrinterPass implementation
655 //
656 PreservedAnalyses LoopCachePrinterPass::run(Loop &L, LoopAnalysisManager &AM,
657                                             LoopStandardAnalysisResults &AR,
658                                             LPMUpdater &U) {
659   Function *F = L.getHeader()->getParent();
660   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
661 
662   if (auto CC = CacheCost::getCacheCost(L, AR, DI))
663     OS << *CC;
664 
665   return PreservedAnalyses::all();
666 }
667