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.
getInnerMostLoop(const LoopVectorTy & Loops)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
isOneDimensionalArray(const SCEV & AccessFn,const SCEV & ElemSize,const Loop & L,ScalarEvolution & SE)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.
computeTripCount(const Loop & L,ScalarEvolution & SE)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 //
operator <<(raw_ostream & OS,const IndexedReference & R)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
IndexedReference(Instruction & StoreOrLoadInst,const LoopInfo & LI,ScalarEvolution & SE)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
hasSpacialReuse(const IndexedReference & Other,unsigned CLS,AAResults & AA) const150 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
hasTemporalReuse(const IndexedReference & Other,unsigned MaxDistance,const Loop & L,DependenceInfo & DI,AAResults & AA) const205 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
computeRefCost(const Loop & L,unsigned CLS) const264 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
delinearize(const LoopInfo & LI)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
isLoopInvariant(const Loop & L) const390 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
isConsecutive(const Loop & L,unsigned CLS) const407 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
getLastCoefficient() const428 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
isCoeffForLoopZeroOrInvariant(const SCEV & Subscript,const Loop & L) const436 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
isSimpleAddRecurrence(const SCEV & Subscript,const Loop & L) const443 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
isAliased(const IndexedReference & Other,AAResults & AA) const463 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 //
operator <<(raw_ostream & OS,const CacheCost & CC)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
CacheCost(const LoopVectorTy & Loops,const LoopInfo & LI,ScalarEvolution & SE,TargetTransformInfo & TTI,AAResults & AA,DependenceInfo & DI,Optional<unsigned> TRT)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>
getCacheCost(Loop & Root,LoopStandardAnalysisResults & AR,DependenceInfo & DI,Optional<unsigned> TRT)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
calculateCacheFootprint()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
populateReferenceGroups(ReferenceGroupsTy & RefGroups) const540 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
computeLoopCacheCost(const Loop & L,const ReferenceGroupsTy & RefGroups) const617 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
computeRefGroupCacheCost(const ReferenceGroupTy & RG,const Loop & L) const645 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 //
run(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater & U)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