759 lines · cpp
1//===- LoopCacheAnalysis.cpp - Loop Cache Analysis -------------------------==//2//3// The LLVM Compiler Infrastructure4//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-exception8//9//===----------------------------------------------------------------------===//10///11/// \file12/// 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 Locality16/// By: Steve Carr, Katherine S. McKinley, Chau-Wen Tseng17/// http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf18///19/// The general approach taken to estimate the number of cache lines used by the20/// memory references in an inner loop is:21/// 1. Partition memory references that exhibit temporal or spacial reuse22/// into reference groups.23/// 2. For each loop L in the a loop nest LN:24/// a. Compute the cost of the reference group25/// b. Compute the loop cost by summing up the reference groups costs26//===----------------------------------------------------------------------===//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(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 temporal50// reuse if they access either the same memory location, or a memory location51// with distance smaller than a configurable threshold.52static cl::opt<unsigned> TemporalReuseThreshold(53 "temporal-reuse-threshold", cl::init(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 a59/// 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-first61/// 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(Loops,74 [](const Loop *L1, const Loop *L2) {75 return L1->getLoopDepth() < L2->getLoopDepth();76 }))77 ? LastLoop78 : 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>(&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>(Start) || isa<SCEVAddRecExpr>(Step))93 return false;94 95 // Check that start and increment are both invariant in the loop.96 if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))97 return false;98 99 const SCEV *StepRec = AR->getStepRecurrence(SE);100 if (StepRec && SE.isKnownNegative(StepRec))101 StepRec = SE.getNegativeSCEV(StepRec);102 103 return StepRec == &ElemSize;104}105 106/// Compute the trip count for the given loop \p L or assume a default value if107/// it is not a compile time constant. Return the SCEV expression for the trip108/// count.109static const SCEV *computeTripCount(const Loop &L, const SCEV &ElemSize,110 ScalarEvolution &SE) {111 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(&L);112 const SCEV *TripCount = (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&113 isa<SCEVConstant>(BackedgeTakenCount))114 ? SE.getTripCountFromExitCount(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(ElemSize.getType(), DefaultTripCount);121 }122 123 return TripCount;124}125 126//===----------------------------------------------------------------------===//127// IndexedReference implementation128//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: " << *this156 << "\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>(0, 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 line188 // size.189 const SCEV *LastSubscript = getLastSubscript();190 const SCEV *OtherLastSubscript = Other.getLastSubscript();191 const SCEVConstant *Diff = dyn_cast<SCEVConstant>(192 SE.getMinusSCEV(LastSubscript, 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" << OtherLastSubscript198 << "\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 else208 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(&StoreOrLoadInst, &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 reuse240 // if the distance at the given loop's depth is small (|d| <= MaxDistance) and241 // 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>(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=" << Level257 << "\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, *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 is294 // (TripCount*Stride)/CLS.295 assert(Stride != nullptr &&296 "Stride should not be null for consecutive access!");297 Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());298 const SCEV *CacheLineSize = SE.getConstant(WiderType, CLS);299 Stride = SE.getNoopOrAnyExtend(Stride, WiderType);300 TripCount = SE.getNoopOrZeroExtend(TripCount, WiderType);301 const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);302 // Round the fractional cost up to the nearest integer number.303 // The impact is the most significant when cost is calculated304 // to be a number less than one, because it makes more sense305 // to say one cache line is used rather than zero cache line306 // is used.307 RefCost = SE.getUDivCeilSCEV(Numerator, 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 to314 // the trip count and the depth of the dimension which the subject loop315 // subscript is accessing. We try to estimate this by multiplying the cost316 // by the trip counts of loops corresponding to the inner dimensions. For317 // example, given the indexed reference 'A[i][j][k]', and assuming the318 // i-loop is in the innermost position, the cost would be equal to the319 // 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>(getSubscript(I));327 assert(AR && AR->getLoop() && "Expecting valid loop");328 const SCEV *TripCount =329 computeTripCount(*AR->getLoop(), *Sizes.back(), SE);330 Type *WiderType = SE.getWiderType(RefCost->getType(), TripCount->getType());331 // For the multiplication result to fit, request a type twice as wide.332 WiderType = WiderType->getExtendedType();333 RefCost = SE.getMulExpr(SE.getNoopOrZeroExtend(RefCost, WiderType),334 SE.getNoopOrZeroExtend(TripCount, WiderType));335 }336 337 LLVM_DEBUG(dbgs().indent(4)338 << "Access is not consecutive: RefCost=" << *RefCost << "\n");339 }340 assert(RefCost && "Expecting a valid RefCost");341 342 // Attempt to fold RefCost into a constant.343 // CacheCostTy is a signed integer, but the tripcount value can be large344 // and may not fit, so saturate/limit the value to the maximum signed345 // integer value.346 if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost))347 return ConstantCost->getValue()->getLimitedValue(348 std::numeric_limits<int64_t>::max());349 350 LLVM_DEBUG(dbgs().indent(4)351 << "RefCost is not a constant! Setting to RefCost=InvalidCost "352 "(invalid value).\n");353 354 return CacheCostTy::getInvalid();355}356 357bool IndexedReference::tryDelinearizeFixedSize(358 const SCEV *AccessFn, SmallVectorImpl<const SCEV *> &Subscripts,359 const SCEV *ElementSize) {360 const SCEV *Offset = SE.removePointerBase(AccessFn);361 if (!delinearizeFixedSizeArray(SE, Offset, Subscripts, Sizes, ElementSize)) {362 Sizes.clear();363 return false;364 }365 366 // We expect Sizes and Subscipts have the same number of elements, and the367 // last element of Sizes is ElementSize. It is for ensuring consistency with368 // the load/store instruction being analyzed. It is not needed for further369 // analysis.370 // TODO: Maybe this property should be enforced in delinearizeFixedSizeArray.371#ifndef NDEBUG372 assert(!Sizes.empty() && Subscripts.size() == Sizes.size() &&373 "Inconsistent length of Sizes and Subscripts");374 Type *WideTy =375 SE.getWiderType(ElementSize->getType(), Sizes.back()->getType());376 const SCEV *ElemSizeExt = SE.getNoopOrZeroExtend(ElementSize, WideTy);377 const SCEV *LastSizeExt = SE.getNoopOrZeroExtend(Sizes.back(), WideTy);378 assert(ElemSizeExt == LastSizeExt && "Unexpected last element of Sizes");379#endif380 381 Sizes.pop_back();382 return true;383}384 385bool IndexedReference::delinearize(const LoopInfo &LI) {386 assert(Subscripts.empty() && "Subscripts should be empty");387 assert(Sizes.empty() && "Sizes should be empty");388 assert(!IsValid && "Should be called once from the constructor");389 LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");390 391 const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);392 const BasicBlock *BB = StoreOrLoadInst.getParent();393 394 if (Loop *L = LI.getLoopFor(BB)) {395 const SCEV *AccessFn =396 SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L);397 398 BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));399 if (BasePointer == nullptr) {400 LLVM_DEBUG(401 dbgs().indent(2)402 << "ERROR: failed to delinearize, can't identify base pointer\n");403 return false;404 }405 406 bool IsFixedSize = false;407 // Try to delinearize fixed-size arrays.408 if (tryDelinearizeFixedSize(AccessFn, Subscripts, ElemSize)) {409 IsFixedSize = true;410 // The last element of Sizes is the element size.411 Sizes.push_back(ElemSize);412 LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()413 << "', AccessFn: " << *AccessFn << "\n");414 }415 416 AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);417 418 // Try to delinearize parametric-size arrays.419 if (!IsFixedSize) {420 LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()421 << "', AccessFn: " << *AccessFn << "\n");422 llvm::delinearize(SE, AccessFn, Subscripts, Sizes,423 SE.getElementSize(&StoreOrLoadInst));424 }425 426 if (Subscripts.empty() || Sizes.empty() ||427 Subscripts.size() != Sizes.size()) {428 // Attempt to determine whether we have a single dimensional array access.429 // before giving up.430 if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {431 LLVM_DEBUG(dbgs().indent(2)432 << "ERROR: failed to delinearize reference\n");433 Subscripts.clear();434 Sizes.clear();435 return false;436 }437 438 // The array may be accessed in reverse, for example:439 // for (i = N; i > 0; i--)440 // A[i] = 0;441 // In this case, reconstruct the access function using the absolute value442 // of the step recurrence.443 const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn);444 const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;445 446 if (StepRec && SE.isKnownNegative(StepRec))447 AccessFn = SE.getAddRecExpr(448 AccessFnAR->getStart(), SE.getNegativeSCEV(StepRec),449 AccessFnAR->getLoop(), SCEV::NoWrapFlags::FlagAnyWrap);450 const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);451 Subscripts.push_back(Div);452 Sizes.push_back(ElemSize);453 }454 455 return all_of(Subscripts, [&](const SCEV *Subscript) {456 return isSimpleAddRecurrence(*Subscript, *L);457 });458 }459 460 return false;461}462 463bool IndexedReference::isLoopInvariant(const Loop &L) const {464 Value *Addr = getPointerOperand(&StoreOrLoadInst);465 assert(Addr != nullptr && "Expecting either a load or a store instruction");466 assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");467 468 if (SE.isLoopInvariant(SE.getSCEV(Addr), &L))469 return true;470 471 // The indexed reference is loop invariant if none of the coefficients use472 // the loop induction variable.473 bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) {474 return isCoeffForLoopZeroOrInvariant(*Subscript, L);475 });476 477 return allCoeffForLoopAreZero;478}479 480bool IndexedReference::isConsecutive(const Loop &L, const SCEV *&Stride,481 unsigned CLS) const {482 // The indexed reference is 'consecutive' if the only coefficient that uses483 // the loop induction variable is the last one...484 const SCEV *LastSubscript = Subscripts.back();485 for (const SCEV *Subscript : Subscripts) {486 if (Subscript == LastSubscript)487 continue;488 if (!isCoeffForLoopZeroOrInvariant(*Subscript, L))489 return false;490 }491 492 // ...and the access stride is less than the cache line size.493 const SCEV *Coeff = getLastCoefficient();494 const SCEV *ElemSize = Sizes.back();495 Type *WiderType = SE.getWiderType(Coeff->getType(), ElemSize->getType());496 // FIXME: This assumes that all values are signed integers which may497 // be incorrect in unusual codes and incorrectly use sext instead of zext.498 // for (uint32_t i = 0; i < 512; ++i) {499 // uint8_t trunc = i;500 // A[trunc] = 42;501 // }502 // This consecutively iterates twice over A. If `trunc` is sign-extended,503 // we would conclude that this may iterate backwards over the array.504 // However, LoopCacheAnalysis is heuristic anyway and transformations must505 // not result in wrong optimizations if the heuristic was incorrect.506 Stride = SE.getMulExpr(SE.getNoopOrSignExtend(Coeff, WiderType),507 SE.getNoopOrSignExtend(ElemSize, WiderType));508 const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);509 510 Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;511 return SE.isKnownPredicate(ICmpInst::ICMP_ULT, Stride, CacheLineSize);512}513 514int IndexedReference::getSubscriptIndex(const Loop &L) const {515 for (auto Idx : seq<int>(0, getNumSubscripts())) {516 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(Idx));517 if (AR && AR->getLoop() == &L) {518 return Idx;519 }520 }521 return -1;522}523 524const SCEV *IndexedReference::getLastCoefficient() const {525 const SCEV *LastSubscript = getLastSubscript();526 auto *AR = cast<SCEVAddRecExpr>(LastSubscript);527 return AR->getStepRecurrence(SE);528}529 530bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,531 const Loop &L) const {532 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript);533 return (AR != nullptr) ? AR->getLoop() != &L534 : SE.isLoopInvariant(&Subscript, &L);535}536 537bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,538 const Loop &L) const {539 if (!isa<SCEVAddRecExpr>(Subscript))540 return false;541 542 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript);543 assert(AR->getLoop() && "AR should have a loop");544 545 if (!AR->isAffine())546 return false;547 548 const SCEV *Start = AR->getStart();549 const SCEV *Step = AR->getStepRecurrence(SE);550 551 if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))552 return false;553 554 return true;555}556 557bool IndexedReference::isAliased(const IndexedReference &Other,558 AAResults &AA) const {559 const auto &Loc1 = MemoryLocation::get(&StoreOrLoadInst);560 const auto &Loc2 = MemoryLocation::get(&Other.StoreOrLoadInst);561 return AA.isMustAlias(Loc1, Loc2);562}563 564//===----------------------------------------------------------------------===//565// CacheCost implementation566//567raw_ostream &llvm::operator<<(raw_ostream &OS, const CacheCost &CC) {568 for (const auto &LC : CC.LoopCosts) {569 const Loop *L = LC.first;570 OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";571 }572 return OS;573}574 575CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI,576 ScalarEvolution &SE, TargetTransformInfo &TTI,577 AAResults &AA, DependenceInfo &DI,578 std::optional<unsigned> TRT)579 : Loops(Loops), TRT(TRT.value_or(TemporalReuseThreshold)), LI(LI), SE(SE),580 TTI(TTI), AA(AA), DI(DI) {581 assert(!Loops.empty() && "Expecting a non-empty loop vector.");582 583 for (const Loop *L : Loops) {584 unsigned TripCount = SE.getSmallConstantTripCount(L);585 TripCount = (TripCount == 0) ? DefaultTripCount : TripCount;586 TripCounts.push_back({L, TripCount});587 }588 589 calculateCacheFootprint();590}591 592std::unique_ptr<CacheCost>593CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR,594 DependenceInfo &DI, std::optional<unsigned> TRT) {595 if (!Root.isOutermost()) {596 LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");597 return nullptr;598 }599 600 LoopVectorTy Loops;601 append_range(Loops, breadth_first(&Root));602 603 if (!getInnerMostLoop(Loops)) {604 LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "605 "than one innermost loop\n");606 return nullptr;607 }608 609 return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);610}611 612void CacheCost::calculateCacheFootprint() {613 LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n");614 ReferenceGroupsTy RefGroups;615 if (!populateReferenceGroups(RefGroups))616 return;617 618 LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n");619 for (const Loop *L : Loops) {620 assert(llvm::none_of(621 LoopCosts,622 [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) &&623 "Should not add duplicate element");624 CacheCostTy LoopCost = computeLoopCacheCost(*L, RefGroups);625 LoopCosts.push_back(std::make_pair(L, LoopCost));626 }627 628 sortLoopCosts();629 RefGroups.clear();630}631 632bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const {633 assert(RefGroups.empty() && "Reference groups should be empty");634 635 unsigned CLS = TTI.getCacheLineSize();636 Loop *InnerMostLoop = getInnerMostLoop(Loops);637 assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop");638 639 for (BasicBlock *BB : InnerMostLoop->getBlocks()) {640 for (Instruction &I : *BB) {641 if (!isa<StoreInst>(I) && !isa<LoadInst>(I))642 continue;643 644 std::unique_ptr<IndexedReference> R(new IndexedReference(I, LI, SE));645 if (!R->isValid())646 continue;647 648 bool Added = false;649 for (ReferenceGroupTy &RefGroup : RefGroups) {650 const IndexedReference &Representative = *RefGroup.front();651 LLVM_DEBUG({652 dbgs() << "References:\n";653 dbgs().indent(2) << *R << "\n";654 dbgs().indent(2) << Representative << "\n";655 });656 657 658 // FIXME: Both positive and negative access functions will be placed659 // into the same reference group, resulting in a bi-directional array660 // access such as:661 // for (i = N; i > 0; i--)662 // A[i] = A[N - i];663 // having the same cost calculation as a single dimention access pattern664 // for (i = 0; i < N; i++)665 // A[i] = A[i];666 // when in actuality, depending on the array size, the first example667 // should have a cost closer to 2x the second due to the two cache668 // access per iteration from opposite ends of the array669 std::optional<bool> HasTemporalReuse =670 R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);671 std::optional<bool> HasSpacialReuse =672 R->hasSpacialReuse(Representative, CLS, AA);673 674 if ((HasTemporalReuse && *HasTemporalReuse) ||675 (HasSpacialReuse && *HasSpacialReuse)) {676 RefGroup.push_back(std::move(R));677 Added = true;678 break;679 }680 }681 682 if (!Added) {683 ReferenceGroupTy RG;684 RG.push_back(std::move(R));685 RefGroups.push_back(std::move(RG));686 }687 }688 }689 690 if (RefGroups.empty())691 return false;692 693 LLVM_DEBUG({694 dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";695 int n = 1;696 for (const ReferenceGroupTy &RG : RefGroups) {697 dbgs().indent(2) << "RefGroup " << n << ":\n";698 for (const auto &IR : RG)699 dbgs().indent(4) << *IR << "\n";700 n++;701 }702 dbgs() << "\n";703 });704 705 return true;706}707 708CacheCostTy709CacheCost::computeLoopCacheCost(const Loop &L,710 const ReferenceGroupsTy &RefGroups) const {711 if (!L.isLoopSimplifyForm())712 return CacheCostTy::getInvalid();713 714 LLVM_DEBUG(dbgs() << "Considering loop '" << L.getName()715 << "' as innermost loop.\n");716 717 // Compute the product of the trip counts of each other loop in the nest.718 CacheCostTy TripCountsProduct = 1;719 for (const auto &TC : TripCounts) {720 if (TC.first == &L)721 continue;722 TripCountsProduct *= TC.second;723 }724 725 CacheCostTy LoopCost = 0;726 for (const ReferenceGroupTy &RG : RefGroups) {727 CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);728 LoopCost += RefGroupCost * TripCountsProduct;729 }730 731 LLVM_DEBUG(dbgs().indent(2) << "Loop '" << L.getName()732 << "' has cost=" << LoopCost << "\n");733 734 return LoopCost;735}736 737CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG,738 const Loop &L) const {739 assert(!RG.empty() && "Reference group should have at least one member.");740 741 const IndexedReference *Representative = RG.front().get();742 return Representative->computeRefCost(L, TTI.getCacheLineSize());743}744 745//===----------------------------------------------------------------------===//746// LoopCachePrinterPass implementation747//748PreservedAnalyses LoopCachePrinterPass::run(Loop &L, LoopAnalysisManager &AM,749 LoopStandardAnalysisResults &AR,750 LPMUpdater &U) {751 Function *F = L.getHeader()->getParent();752 DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);753 754 if (auto CC = CacheCost::getCacheCost(L, AR, DI))755 OS << *CC;756 757 return PreservedAnalyses::all();758}759