1 //===- LoopCacheAnalysis.cpp - Loop Cache Analysis -------------------------==//
7 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
9 //===----------------------------------------------------------------------===//
16 ///       By: Steve Carr, Katherine S. McKinley, Chau-Wen Tseng
17 ///       http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf
21 ///    1. Partition memory references that exhibit temporal or spacial reuse
26 //===----------------------------------------------------------------------===//
43 #define DEBUG_TYPE "loop-cache-cost"
46     "default-trip-count", cl::init(100), cl::Hidden,
49 // In this analysis two array references are considered to exhibit temporal
53     "temporal-reuse-threshold", cl::init(2), cl::Hidden,
56              "temporal reuse"));
60 /// The loop vector is expected to contain loops collected in breadth-first
63   assert(!Loops.empty() && "Expecting a non-empy loop vector");  in getInnerMostLoop()
66   Loop *ParentLoop = LastLoop->getParentLoop();  in getInnerMostLoop()
75                             return L1->getLoopDepth() < L2->getLoopDepth();  in getInnerMostLoop()
84   if (!AR || !AR->isAffine())  in isOneDimensionalArray()
87   assert(AR->getLoop() && "AR should have a loop");  in isOneDimensionalArray()
90   const SCEV *Start = AR->getStart();  in isOneDimensionalArray()
91   const SCEV *Step = AR->getStepRecurrence(SE);  in isOneDimensionalArray()
99   const SCEV *StepRec = AR->getStepRecurrence(SE);  in isOneDimensionalArray()
126 //===----------------------------------------------------------------------===//
178   for (auto SubNum : seq<unsigned>(0, NumSubscripts - 1)) {  in hasSpacialReuse()
202   bool InSameCacheLine = (Diff->getValue()->getSExtValue() < CLS);  in hasSpacialReuse()
222                << "No temporal reuse: different base pointer\n");  in hasTemporalReuse()
230     LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: no dependence\n");  in hasTemporalReuse()
234   if (D->isLoopIndependent()) {  in hasTemporalReuse()
235     LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");  in hasTemporalReuse()
239   // Check the dependence distance at every loop level. There is temporal reuse  in hasTemporalReuse()
243   int Levels = D->getLevels();  in hasTemporalReuse()
245     const SCEV *Distance = D->getDistance(Level);  in hasTemporalReuse()
249       LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: distance unknown\n");  in hasTemporalReuse()
253     const ConstantInt &CI = *SCEVConst->getValue();  in hasTemporalReuse()
256                  << "No temporal reuse: distance is not zero at depth=" << Level  in hasTemporalReuse()
262           << "No temporal reuse: distance is greater than MaxDistance at depth="  in hasTemporalReuse()
268   LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");  in hasTemporalReuse()
297     Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());  in computeRefCost()
318     // i-loop is in the innermost position, the cost would be equal to the  in computeRefCost()
319     // iterations of the i-loop multiplied by iterations of the j-loop.  in computeRefCost()
325     for (unsigned I = Index + 1; I < getNumSubscripts() - 1; ++I) {  in computeRefCost()
327       assert(AR && AR->getLoop() && "Expecting valid loop");  in computeRefCost()
329           computeTripCount(*AR->getLoop(), *Sizes.back(), SE);  in computeRefCost()
330       Type *WiderType = SE.getWiderType(RefCost->getType(), TripCount->getType());  in computeRefCost()
342     return ConstantCost->getValue()->getZExtValue();  in computeRefCost()
361         SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1]));  in tryDelinearizeFixedSize()
364     dbgs() << "Delinearized subscripts of fixed-size array\n"  in tryDelinearizeFixedSize()
393     // Try to delinearize fixed-size arrays.  in delinearize()
398       LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()  in delinearize()
404     // Try to delinearize parametric-size arrays.  in delinearize()
406       LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()  in delinearize()
425       //   for (i = N; i > 0; i--)  in delinearize()
430       const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;  in delinearize()
433         AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(),  in delinearize()
435                                     AccessFnAR->getLoop(),  in delinearize()
436                                     AccessFnAR->getNoWrapFlags());  in delinearize()
453   assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");  in isLoopInvariant()
482   Type *WiderType = SE.getWiderType(Coeff->getType(), ElemSize->getType());  in isConsecutive()
489   // This consecutively iterates twice over A. If `trunc` is sign-extended,  in isConsecutive()
495   const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);  in isConsecutive()
504     if (AR && AR->getLoop() == &L) {  in getSubscriptIndex()
508   return -1;  in getSubscriptIndex()
514   return AR->getStepRecurrence(SE);  in getLastCoefficient()
520   return (AR != nullptr) ? AR->getLoop() != &L  in isCoeffForLoopZeroOrInvariant()
530   assert(AR->getLoop() && "AR should have a loop");  in isSimpleAddRecurrence()
532   if (!AR->isAffine())  in isSimpleAddRecurrence()
535   const SCEV *Start = AR->getStart();  in isSimpleAddRecurrence()
536   const SCEV *Step = AR->getStepRecurrence(SE);  in isSimpleAddRecurrence()
551 //===----------------------------------------------------------------------===//
557     OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";  in operator <<()
568   assert(!Loops.empty() && "Expecting a non-empty loop vector.");  in CacheCost()
626   for (BasicBlock *BB : InnerMostLoop->getBlocks()) {  in populateReferenceGroups()
632       if (!R->isValid())  in populateReferenceGroups()
646        // into the same reference group, resulting in a bi-directional array  in populateReferenceGroups()
648        //   for (i = N; i > 0; i--)  in populateReferenceGroups()
649        //     A[i] = A[N - i];  in populateReferenceGroups()
657             R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);  in populateReferenceGroups()
659             R->hasSpacialReuse(Representative, CLS, AA);  in populateReferenceGroups()
729   return Representative->computeRefCost(L, TTI.getCacheLineSize());  in computeRefGroupCacheCost()
732 //===----------------------------------------------------------------------===//
738   Function *F = L.getHeader()->getParent();  in run()