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/Delinearization.h"
34#include "llvm/Analysis/DependenceAnalysis.h"
35#include "llvm/Analysis/LoopInfo.h"
36#include "llvm/Analysis/ScalarEvolutionExpressions.h"
37#include "llvm/Analysis/TargetTransformInfo.h"
38#include "llvm/Support/CommandLine.h"
39#include "llvm/Support/Debug.h"
40
41using namespace llvm;
42
43#define DEBUG_TYPE "loop-cache-cost"
44
45static cl::opt<unsigned> DefaultTripCount(
46 "default-trip-count", cl::init(Val: 100), cl::Hidden,
47 cl::desc("Use this to specify the default trip count of a loop"));
48
49// In this analysis two array references are considered to exhibit temporal
50// reuse if they access either the same memory location, or a memory location
51// with distance smaller than a configurable threshold.
52static cl::opt<unsigned> TemporalReuseThreshold(
53 "temporal-reuse-threshold", cl::init(Val: 2), cl::Hidden,
54 cl::desc("Use this to specify the max. distance between array elements "
55 "accessed in a loop so that the elements are classified to have "
56 "temporal reuse"));
57
58/// Retrieve the innermost loop in the given loop nest \p Loops. It returns a
59/// nullptr if any loops in the loop vector supplied has more than one sibling.
60/// The loop vector is expected to contain loops collected in breadth-first
61/// order.
62static Loop *getInnerMostLoop(const LoopVectorTy &Loops) {
63 assert(!Loops.empty() && "Expecting a non-empy loop vector");
64
65 Loop *LastLoop = Loops.back();
66 Loop *ParentLoop = LastLoop->getParentLoop();
67
68 if (ParentLoop == nullptr) {
69 assert(Loops.size() == 1 && "Expecting a single loop");
70 return LastLoop;
71 }
72
73 return (llvm::is_sorted(Range: Loops,
74 C: [](const Loop *L1, const Loop *L2) {
75 return L1->getLoopDepth() < L2->getLoopDepth();
76 }))
77 ? LastLoop
78 : nullptr;
79}
80
81static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize,
82 const Loop &L, ScalarEvolution &SE) {
83 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: &AccessFn);
84 if (!AR || !AR->isAffine())
85 return false;
86
87 assert(AR->getLoop() && "AR should have a loop");
88
89 // Check that start and increment are not add recurrences.
90 const SCEV *Start = AR->getStart();
91 const SCEV *Step = AR->getStepRecurrence(SE);
92 if (isa<SCEVAddRecExpr>(Val: Start) || isa<SCEVAddRecExpr>(Val: Step))
93 return false;
94
95 // Check that start and increment are both invariant in the loop.
96 if (!SE.isLoopInvariant(S: Start, L: &L) || !SE.isLoopInvariant(S: Step, L: &L))
97 return false;
98
99 const SCEV *StepRec = AR->getStepRecurrence(SE);
100 if (StepRec && SE.isKnownNegative(S: StepRec))
101 StepRec = SE.getNegativeSCEV(V: StepRec);
102
103 return StepRec == &ElemSize;
104}
105
106/// Compute the trip count for the given loop \p L or assume a default value if
107/// it is not a compile time constant. Return the SCEV expression for the trip
108/// count.
109static const SCEV *computeTripCount(const Loop &L, const SCEV &ElemSize,
110 ScalarEvolution &SE) {
111 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L: &L);
112 const SCEV *TripCount = (!isa<SCEVCouldNotCompute>(Val: BackedgeTakenCount) &&
113 isa<SCEVConstant>(Val: BackedgeTakenCount))
114 ? SE.getTripCountFromExitCount(ExitCount: BackedgeTakenCount)
115 : nullptr;
116
117 if (!TripCount) {
118 LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName()
119 << " could not be computed, using DefaultTripCount\n");
120 TripCount = SE.getConstant(Ty: ElemSize.getType(), V: DefaultTripCount);
121 }
122
123 return TripCount;
124}
125
126//===----------------------------------------------------------------------===//
127// IndexedReference implementation
128//
129raw_ostream &llvm::operator<<(raw_ostream &OS, const IndexedReference &R) {
130 if (!R.IsValid) {
131 OS << R.StoreOrLoadInst;
132 OS << ", IsValid=false.";
133 return OS;
134 }
135
136 OS << *R.BasePointer;
137 for (const SCEV *Subscript : R.Subscripts)
138 OS << "[" << *Subscript << "]";
139
140 OS << ", Sizes: ";
141 for (const SCEV *Size : R.Sizes)
142 OS << "[" << *Size << "]";
143
144 return OS;
145}
146
147IndexedReference::IndexedReference(Instruction &StoreOrLoadInst,
148 const LoopInfo &LI, ScalarEvolution &SE)
149 : StoreOrLoadInst(StoreOrLoadInst), SE(SE) {
150 assert((isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst>(StoreOrLoadInst)) &&
151 "Expecting a load or store instruction");
152
153 IsValid = delinearize(LI);
154 if (IsValid)
155 LLVM_DEBUG(dbgs().indent(2) << "Succesfully delinearized: " << *this
156 << "\n");
157}
158
159std::optional<bool>
160IndexedReference::hasSpacialReuse(const IndexedReference &Other, unsigned CLS,
161 AAResults &AA) const {
162 assert(IsValid && "Expecting a valid reference");
163
164 if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
165 LLVM_DEBUG(dbgs().indent(2)
166 << "No spacial reuse: different base pointers\n");
167 return false;
168 }
169
170 unsigned NumSubscripts = getNumSubscripts();
171 if (NumSubscripts != Other.getNumSubscripts()) {
172 LLVM_DEBUG(dbgs().indent(2)
173 << "No spacial reuse: different number of subscripts\n");
174 return false;
175 }
176
177 // all subscripts must be equal, except the leftmost one (the last one).
178 for (auto SubNum : seq<unsigned>(Begin: 0, End: NumSubscripts - 1)) {
179 if (getSubscript(SubNum) != Other.getSubscript(SubNum)) {
180 LLVM_DEBUG(dbgs().indent(2) << "No spacial reuse, different subscripts: "
181 << "\n\t" << *getSubscript(SubNum) << "\n\t"
182 << *Other.getSubscript(SubNum) << "\n");
183 return false;
184 }
185 }
186
187 // the difference between the last subscripts must be less than the cache line
188 // size.
189 const SCEV *LastSubscript = getLastSubscript();
190 const SCEV *OtherLastSubscript = Other.getLastSubscript();
191 const SCEVConstant *Diff = dyn_cast<SCEVConstant>(
192 Val: SE.getMinusSCEV(LHS: LastSubscript, RHS: OtherLastSubscript));
193
194 if (Diff == nullptr) {
195 LLVM_DEBUG(dbgs().indent(2)
196 << "No spacial reuse, difference between subscript:\n\t"
197 << *LastSubscript << "\n\t" << OtherLastSubscript
198 << "\nis not constant.\n");
199 return std::nullopt;
200 }
201
202 bool InSameCacheLine = (Diff->getValue()->getSExtValue() < CLS);
203
204 LLVM_DEBUG({
205 if (InSameCacheLine)
206 dbgs().indent(2) << "Found spacial reuse.\n";
207 else
208 dbgs().indent(2) << "No spacial reuse.\n";
209 });
210
211 return InSameCacheLine;
212}
213
214std::optional<bool>
215IndexedReference::hasTemporalReuse(const IndexedReference &Other,
216 unsigned MaxDistance, const Loop &L,
217 DependenceInfo &DI, AAResults &AA) const {
218 assert(IsValid && "Expecting a valid reference");
219
220 if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
221 LLVM_DEBUG(dbgs().indent(2)
222 << "No temporal reuse: different base pointer\n");
223 return false;
224 }
225
226 std::unique_ptr<Dependence> D =
227 DI.depends(Src: &StoreOrLoadInst, Dst: &Other.StoreOrLoadInst);
228
229 if (D == nullptr) {
230 LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: no dependence\n");
231 return false;
232 }
233
234 if (D->isLoopIndependent()) {
235 LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
236 return true;
237 }
238
239 // Check the dependence distance at every loop level. There is temporal reuse
240 // if the distance at the given loop's depth is small (|d| <= MaxDistance) and
241 // it is zero at every other loop level.
242 int LoopDepth = L.getLoopDepth();
243 int Levels = D->getLevels();
244 for (int Level = 1; Level <= Levels; ++Level) {
245 const SCEV *Distance = D->getDistance(Level);
246 const SCEVConstant *SCEVConst = dyn_cast_or_null<SCEVConstant>(Val: Distance);
247
248 if (SCEVConst == nullptr) {
249 LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: distance unknown\n");
250 return std::nullopt;
251 }
252
253 const ConstantInt &CI = *SCEVConst->getValue();
254 if (Level != LoopDepth && !CI.isZero()) {
255 LLVM_DEBUG(dbgs().indent(2)
256 << "No temporal reuse: distance is not zero at depth=" << Level
257 << "\n");
258 return false;
259 } else if (Level == LoopDepth && CI.getSExtValue() > MaxDistance) {
260 LLVM_DEBUG(
261 dbgs().indent(2)
262 << "No temporal reuse: distance is greater than MaxDistance at depth="
263 << Level << "\n");
264 return false;
265 }
266 }
267
268 LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
269 return true;
270}
271
272CacheCostTy IndexedReference::computeRefCost(const Loop &L,
273 unsigned CLS) const {
274 assert(IsValid && "Expecting a valid reference");
275 LLVM_DEBUG({
276 dbgs().indent(2) << "Computing cache cost for:\n";
277 dbgs().indent(4) << *this << "\n";
278 });
279
280 // If the indexed reference is loop invariant the cost is one.
281 if (isLoopInvariant(L)) {
282 LLVM_DEBUG(dbgs().indent(4) << "Reference is loop invariant: RefCost=1\n");
283 return 1;
284 }
285
286 const SCEV *TripCount = computeTripCount(L, ElemSize: *Sizes.back(), SE);
287 assert(TripCount && "Expecting valid TripCount");
288 LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n");
289
290 const SCEV *RefCost = nullptr;
291 const SCEV *Stride = nullptr;
292 if (isConsecutive(L, Stride, CLS)) {
293 // If the indexed reference is 'consecutive' the cost is
294 // (TripCount*Stride)/CLS.
295 assert(Stride != nullptr &&
296 "Stride should not be null for consecutive access!");
297 Type *WiderType = SE.getWiderType(Ty1: Stride->getType(), Ty2: TripCount->getType());
298 const SCEV *CacheLineSize = SE.getConstant(Ty: WiderType, V: CLS);
299 Stride = SE.getNoopOrAnyExtend(V: Stride, Ty: WiderType);
300 TripCount = SE.getNoopOrZeroExtend(V: TripCount, Ty: WiderType);
301 const SCEV *Numerator = SE.getMulExpr(LHS: Stride, RHS: TripCount);
302 // Round the fractional cost up to the nearest integer number.
303 // The impact is the most significant when cost is calculated
304 // to be a number less than one, because it makes more sense
305 // to say one cache line is used rather than zero cache line
306 // is used.
307 RefCost = SE.getUDivCeilSCEV(N: Numerator, D: CacheLineSize);
308
309 LLVM_DEBUG(dbgs().indent(4)
310 << "Access is consecutive: RefCost=(TripCount*Stride)/CLS="
311 << *RefCost << "\n");
312 } else {
313 // If the indexed reference is not 'consecutive' the cost is proportional to
314 // the trip count and the depth of the dimension which the subject loop
315 // subscript is accessing. We try to estimate this by multiplying the cost
316 // by the trip counts of loops corresponding to the inner dimensions. For
317 // example, given the indexed reference 'A[i][j][k]', and assuming the
318 // i-loop is in the innermost position, the cost would be equal to the
319 // iterations of the i-loop multiplied by iterations of the j-loop.
320 RefCost = TripCount;
321
322 int Index = getSubscriptIndex(L);
323 assert(Index >= 0 && "Could not locate a valid Index");
324
325 for (unsigned I = Index + 1; I < getNumSubscripts() - 1; ++I) {
326 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: getSubscript(SubNum: I));
327 assert(AR && AR->getLoop() && "Expecting valid loop");
328 const SCEV *TripCount =
329 computeTripCount(L: *AR->getLoop(), ElemSize: *Sizes.back(), SE);
330 Type *WiderType = SE.getWiderType(Ty1: RefCost->getType(), Ty2: TripCount->getType());
331 // For the multiplication result to fit, request a type twice as wide.
332 // Bail out if doubling would exceed MAX_INT_BITS.
333 auto *WiderIntTy = cast<IntegerType>(Val: WiderType);
334 if (WiderIntTy->getBitWidth() > IntegerType::MAX_INT_BITS / 2)
335 return CacheCostTy::getInvalid();
336 WiderType = WiderIntTy->getExtendedType();
337 RefCost = SE.getMulExpr(LHS: SE.getNoopOrZeroExtend(V: RefCost, Ty: WiderType),
338 RHS: SE.getNoopOrZeroExtend(V: TripCount, Ty: WiderType));
339 }
340
341 LLVM_DEBUG(dbgs().indent(4)
342 << "Access is not consecutive: RefCost=" << *RefCost << "\n");
343 }
344 assert(RefCost && "Expecting a valid RefCost");
345
346 // Attempt to fold RefCost into a constant.
347 // CacheCostTy is a signed integer, but the tripcount value can be large
348 // and may not fit, so saturate/limit the value to the maximum signed
349 // integer value.
350 if (auto ConstantCost = dyn_cast<SCEVConstant>(Val: RefCost))
351 return ConstantCost->getValue()->getLimitedValue(
352 Limit: std::numeric_limits<int64_t>::max());
353
354 LLVM_DEBUG(dbgs().indent(4)
355 << "RefCost is not a constant! Setting to RefCost=InvalidCost "
356 "(invalid value).\n");
357
358 return CacheCostTy::getInvalid();
359}
360
361bool IndexedReference::delinearize(const LoopInfo &LI) {
362 assert(Subscripts.empty() && "Subscripts should be empty");
363 assert(Sizes.empty() && "Sizes should be empty");
364 assert(!IsValid && "Should be called once from the constructor");
365 LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");
366
367 const SCEV *ElemSize = SE.getElementSize(Inst: &StoreOrLoadInst);
368 const BasicBlock *BB = StoreOrLoadInst.getParent();
369
370 if (Loop *L = LI.getLoopFor(BB)) {
371 const SCEV *AccessFn =
372 SE.getSCEVAtScope(V: getPointerOperand(V: &StoreOrLoadInst), L);
373
374 BasePointer = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: AccessFn));
375 if (BasePointer == nullptr) {
376 LLVM_DEBUG(
377 dbgs().indent(2)
378 << "ERROR: failed to delinearize, can't identify base pointer\n");
379 return false;
380 }
381
382 bool IsFixedSize = false;
383 AccessFn = SE.getMinusSCEV(LHS: AccessFn, RHS: BasePointer);
384
385 // Try to delinearize fixed-size arrays.
386 if (delinearizeFixedSizeArray(SE, Expr: AccessFn, Subscripts, Sizes, ElementSize: ElemSize)) {
387 IsFixedSize = true;
388 LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
389 << "', AccessFn: " << *AccessFn << "\n");
390 }
391
392 // Try to delinearize parametric-size arrays.
393 if (!IsFixedSize) {
394 LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
395 << "', AccessFn: " << *AccessFn << "\n");
396 Sizes.clear();
397 llvm::delinearize(SE, Expr: AccessFn, Subscripts, Sizes,
398 ElementSize: SE.getElementSize(Inst: &StoreOrLoadInst));
399 }
400
401 if (Subscripts.empty() || Sizes.empty() ||
402 Subscripts.size() != Sizes.size()) {
403 // Attempt to determine whether we have a single dimensional array access.
404 // before giving up.
405 if (!isOneDimensionalArray(AccessFn: *AccessFn, ElemSize: *ElemSize, L: *L, SE)) {
406 LLVM_DEBUG(dbgs().indent(2)
407 << "ERROR: failed to delinearize reference\n");
408 Subscripts.clear();
409 Sizes.clear();
410 return false;
411 }
412
413 // The array may be accessed in reverse, for example:
414 // for (i = N; i > 0; i--)
415 // A[i] = 0;
416 // In this case, reconstruct the access function using the absolute value
417 // of the step recurrence.
418 const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(Val: AccessFn);
419 const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;
420
421 if (StepRec && SE.isKnownNegative(S: StepRec))
422 AccessFn = SE.getAddRecExpr(Start: AccessFnAR->getStart(),
423 Step: SE.getNegativeSCEV(V: StepRec),
424 L: AccessFnAR->getLoop(), Flags: SCEVFlags::FlagNone);
425 const SCEV *Div = SE.getUDivExactExpr(LHS: AccessFn, RHS: ElemSize);
426 Subscripts.push_back(Elt: Div);
427 Sizes.push_back(Elt: ElemSize);
428 }
429
430 return all_of(Range&: Subscripts, P: [&](const SCEV *Subscript) {
431 return isSimpleAddRecurrence(Subscript: *Subscript, L: *L);
432 });
433 }
434
435 return false;
436}
437
438bool IndexedReference::isLoopInvariant(const Loop &L) const {
439 Value *Addr = getPointerOperand(V: &StoreOrLoadInst);
440 assert(Addr != nullptr && "Expecting either a load or a store instruction");
441 assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");
442
443 if (SE.isLoopInvariant(S: SE.getSCEV(V: Addr), L: &L))
444 return true;
445
446 // The indexed reference is loop invariant if none of the coefficients use
447 // the loop induction variable.
448 bool allCoeffForLoopAreZero = all_of(Range: Subscripts, P: [&](const SCEV *Subscript) {
449 return isCoeffForLoopZeroOrInvariant(Subscript: *Subscript, L);
450 });
451
452 return allCoeffForLoopAreZero;
453}
454
455bool IndexedReference::isConsecutive(const Loop &L, const SCEV *&Stride,
456 unsigned CLS) const {
457 // The indexed reference is 'consecutive' if the only coefficient that uses
458 // the loop induction variable is the last one...
459 const SCEV *LastSubscript = Subscripts.back();
460 for (const SCEV *Subscript : Subscripts) {
461 if (Subscript == LastSubscript)
462 continue;
463 if (!isCoeffForLoopZeroOrInvariant(Subscript: *Subscript, L))
464 return false;
465 }
466
467 // ...and the access stride is less than the cache line size.
468 const SCEV *Coeff = getLastCoefficient();
469 const SCEV *ElemSize = Sizes.back();
470 Type *WiderType = SE.getWiderType(Ty1: Coeff->getType(), Ty2: ElemSize->getType());
471 // FIXME: This assumes that all values are signed integers which may
472 // be incorrect in unusual codes and incorrectly use sext instead of zext.
473 // for (uint32_t i = 0; i < 512; ++i) {
474 // uint8_t trunc = i;
475 // A[trunc] = 42;
476 // }
477 // This consecutively iterates twice over A. If `trunc` is sign-extended,
478 // we would conclude that this may iterate backwards over the array.
479 // However, LoopCacheAnalysis is heuristic anyway and transformations must
480 // not result in wrong optimizations if the heuristic was incorrect.
481 Stride = SE.getMulExpr(LHS: SE.getNoopOrSignExtend(V: Coeff, Ty: WiderType),
482 RHS: SE.getNoopOrSignExtend(V: ElemSize, Ty: WiderType));
483 const SCEV *CacheLineSize = SE.getConstant(Ty: Stride->getType(), V: CLS);
484
485 Stride = SE.isKnownNegative(S: Stride) ? SE.getNegativeSCEV(V: Stride) : Stride;
486 return SE.isKnownPredicate(Pred: ICmpInst::ICMP_ULT, LHS: Stride, RHS: CacheLineSize);
487}
488
489int IndexedReference::getSubscriptIndex(const Loop &L) const {
490 for (auto Idx : seq<int>(Begin: 0, End: getNumSubscripts())) {
491 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: getSubscript(SubNum: Idx));
492 if (AR && AR->getLoop() == &L) {
493 return Idx;
494 }
495 }
496 return -1;
497}
498
499const SCEV *IndexedReference::getLastCoefficient() const {
500 const SCEV *LastSubscript = getLastSubscript();
501 auto *AR = cast<SCEVAddRecExpr>(Val: LastSubscript);
502 return AR->getStepRecurrence(SE);
503}
504
505bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
506 const Loop &L) const {
507 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Val: &Subscript);
508 return (AR != nullptr) ? AR->getLoop() != &L
509 : SE.isLoopInvariant(S: &Subscript, L: &L);
510}
511
512bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,
513 const Loop &L) const {
514 if (!isa<SCEVAddRecExpr>(Val: Subscript))
515 return false;
516
517 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(Val: &Subscript);
518 assert(AR->getLoop() && "AR should have a loop");
519
520 if (!AR->isAffine())
521 return false;
522
523 const SCEV *Start = AR->getStart();
524 const SCEV *Step = AR->getStepRecurrence(SE);
525
526 if (!SE.isLoopInvariant(S: Start, L: &L) || !SE.isLoopInvariant(S: Step, L: &L))
527 return false;
528
529 return true;
530}
531
532bool IndexedReference::isAliased(const IndexedReference &Other,
533 AAResults &AA) const {
534 const auto &Loc1 = MemoryLocation::get(Inst: &StoreOrLoadInst);
535 const auto &Loc2 = MemoryLocation::get(Inst: &Other.StoreOrLoadInst);
536 return AA.isMustAlias(LocA: Loc1, LocB: Loc2);
537}
538
539//===----------------------------------------------------------------------===//
540// CacheCost implementation
541//
542raw_ostream &llvm::operator<<(raw_ostream &OS, const CacheCost &CC) {
543 for (const auto &LC : CC.LoopCosts) {
544 const Loop *L = LC.first;
545 OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";
546 }
547 return OS;
548}
549
550CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI,
551 ScalarEvolution &SE, TargetTransformInfo &TTI,
552 AAResults &AA, DependenceInfo &DI,
553 std::optional<unsigned> TRT)
554 : Loops(Loops), TRT(TRT.value_or(u&: TemporalReuseThreshold)), LI(LI), SE(SE),
555 TTI(TTI), AA(AA), DI(DI) {
556 assert(!Loops.empty() && "Expecting a non-empty loop vector.");
557
558 for (const Loop *L : Loops) {
559 unsigned TripCount = SE.getSmallConstantTripCount(L);
560 TripCount = (TripCount == 0) ? DefaultTripCount : TripCount;
561 TripCounts.push_back(Elt: {L, TripCount});
562 }
563
564 calculateCacheFootprint();
565}
566
567static std::unique_ptr<CacheCost>
568getCacheCostImpl(Loop &Root, LoopInfo &LI, ScalarEvolution &SE,
569 TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI,
570 std::optional<unsigned> TRT) {
571 if (!Root.isOutermost()) {
572 LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");
573 return nullptr;
574 }
575
576 LoopVectorTy Loops;
577 append_range(C&: Loops, R: breadth_first(G: &Root));
578
579 if (!getInnerMostLoop(Loops)) {
580 LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "
581 "than one innermost loop\n");
582 return nullptr;
583 }
584
585 return std::make_unique<CacheCost>(args&: Loops, args&: LI, args&: SE, args&: TTI, args&: AA, args&: DI, args&: TRT);
586}
587
588std::unique_ptr<CacheCost>
589CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR,
590 DependenceInfo &DI, std::optional<unsigned> TRT) {
591 return getCacheCostImpl(Root, LI&: AR.LI, SE&: AR.SE, TTI&: AR.TTI, AA&: AR.AA, DI, TRT);
592}
593
594void CacheCost::calculateCacheFootprint() {
595 LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n");
596 ReferenceGroupsTy RefGroups;
597 if (!populateReferenceGroups(RefGroups))
598 return;
599
600 LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n");
601 for (const Loop *L : Loops) {
602 assert(llvm::none_of(
603 LoopCosts,
604 [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) &&
605 "Should not add duplicate element");
606 CacheCostTy LoopCost = computeLoopCacheCost(L: *L, RefGroups);
607 LoopCosts.push_back(Elt: std::make_pair(x&: L, y&: LoopCost));
608 }
609
610 sortLoopCosts();
611 RefGroups.clear();
612}
613
614bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const {
615 assert(RefGroups.empty() && "Reference groups should be empty");
616
617 unsigned CLS = TTI.getCacheLineSize();
618 Loop *InnerMostLoop = getInnerMostLoop(Loops);
619 assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop");
620
621 for (BasicBlock *BB : InnerMostLoop->getBlocks()) {
622 for (Instruction &I : *BB) {
623 if (!isa<StoreInst>(Val: I) && !isa<LoadInst>(Val: I))
624 continue;
625
626 std::unique_ptr<IndexedReference> R(new IndexedReference(I, LI, SE));
627 if (!R->isValid())
628 continue;
629
630 bool Added = false;
631 for (ReferenceGroupTy &RefGroup : RefGroups) {
632 const IndexedReference &Representative = *RefGroup.front();
633 LLVM_DEBUG({
634 dbgs() << "References:\n";
635 dbgs().indent(2) << *R << "\n";
636 dbgs().indent(2) << Representative << "\n";
637 });
638
639
640 // FIXME: Both positive and negative access functions will be placed
641 // into the same reference group, resulting in a bi-directional array
642 // access such as:
643 // for (i = N; i > 0; i--)
644 // A[i] = A[N - i];
645 // having the same cost calculation as a single dimention access pattern
646 // for (i = 0; i < N; i++)
647 // A[i] = A[i];
648 // when in actuality, depending on the array size, the first example
649 // should have a cost closer to 2x the second due to the two cache
650 // access per iteration from opposite ends of the array
651 std::optional<bool> HasTemporalReuse =
652 R->hasTemporalReuse(Other: Representative, MaxDistance: *TRT, L: *InnerMostLoop, DI, AA);
653 std::optional<bool> HasSpacialReuse =
654 R->hasSpacialReuse(Other: Representative, CLS, AA);
655
656 if ((HasTemporalReuse && *HasTemporalReuse) ||
657 (HasSpacialReuse && *HasSpacialReuse)) {
658 RefGroup.push_back(Elt: std::move(R));
659 Added = true;
660 break;
661 }
662 }
663
664 if (!Added) {
665 ReferenceGroupTy RG;
666 RG.push_back(Elt: std::move(R));
667 RefGroups.push_back(Elt: std::move(RG));
668 }
669 }
670 }
671
672 if (RefGroups.empty())
673 return false;
674
675 LLVM_DEBUG({
676 dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";
677 int n = 1;
678 for (const ReferenceGroupTy &RG : RefGroups) {
679 dbgs().indent(2) << "RefGroup " << n << ":\n";
680 for (const auto &IR : RG)
681 dbgs().indent(4) << *IR << "\n";
682 n++;
683 }
684 dbgs() << "\n";
685 });
686
687 return true;
688}
689
690CacheCostTy
691CacheCost::computeLoopCacheCost(const Loop &L,
692 const ReferenceGroupsTy &RefGroups) const {
693 LLVM_DEBUG(dbgs() << "Considering loop '" << L.getName()
694 << "' as innermost loop.\n");
695
696 // Compute the product of the trip counts of each other loop in the nest.
697 CacheCostTy TripCountsProduct = 1;
698 for (const auto &TC : TripCounts) {
699 if (TC.first == &L)
700 continue;
701 TripCountsProduct *= TC.second;
702 }
703
704 CacheCostTy LoopCost = 0;
705 for (const ReferenceGroupTy &RG : RefGroups) {
706 CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);
707 LoopCost += RefGroupCost * TripCountsProduct;
708 }
709
710 LLVM_DEBUG(dbgs().indent(2) << "Loop '" << L.getName()
711 << "' has cost=" << LoopCost << "\n");
712
713 return LoopCost;
714}
715
716CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG,
717 const Loop &L) const {
718 assert(!RG.empty() && "Reference group should have at least one member.");
719
720 const IndexedReference *Representative = RG.front().get();
721 return Representative->computeRefCost(L, CLS: TTI.getCacheLineSize());
722}
723
724//===----------------------------------------------------------------------===//
725// LoopCachePrinterPass implementation
726//
727PreservedAnalyses LoopCachePrinterPass::run(Function &F,
728 FunctionAnalysisManager &FAM) {
729 OS << "Printing analysis 'Loop Cache Analysis' for function '" << F.getName()
730 << "':\n";
731
732 auto &LI = FAM.getResult<LoopAnalysis>(IR&: F);
733 auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(IR&: F);
734 auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
735 auto &AA = FAM.getResult<AAManager>(IR&: F);
736 auto &DI = FAM.getResult<DependenceAnalysis>(IR&: F);
737 for (Loop *L : LI.getTopLevelLoops())
738 if (std::unique_ptr<CacheCost> CC =
739 getCacheCostImpl(Root&: *L, LI, SE, TTI, AA, DI, /*TRT=*/std::nullopt))
740 OS << *CC;
741
742 return PreservedAnalyses::all();
743}
744