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