1 //===- llvm/Analysis/LoopCacheAnalysis.h ------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file defines the interface for the loop cache analysis. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ANALYSIS_LOOPCACHEANALYSIS_H 15 #define LLVM_ANALYSIS_LOOPCACHEANALYSIS_H 16 17 #include "llvm/Analysis/LoopAnalysisManager.h" 18 #include "llvm/IR/PassManager.h" 19 #include <optional> 20 21 namespace llvm { 22 23 class AAResults; 24 class DependenceInfo; 25 class Instruction; 26 class LPMUpdater; 27 class raw_ostream; 28 class LoopInfo; 29 class Loop; 30 class ScalarEvolution; 31 class SCEV; 32 class TargetTransformInfo; 33 34 using CacheCostTy = int64_t; 35 using LoopVectorTy = SmallVector<Loop *, 8>; 36 37 /// Represents a memory reference as a base pointer and a set of indexing 38 /// operations. For example given the array reference A[i][2j+1][3k+2] in a 39 /// 3-dim loop nest: 40 /// for(i=0;i<n;++i) 41 /// for(j=0;j<m;++j) 42 /// for(k=0;k<o;++k) 43 /// ... A[i][2j+1][3k+2] ... 44 /// We expect: 45 /// BasePointer -> A 46 /// Subscripts -> [{0,+,1}<%for.i>][{1,+,2}<%for.j>][{2,+,3}<%for.k>] 47 /// Sizes -> [m][o][4] 48 class IndexedReference { 49 friend raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R); 50 51 public: 52 /// Construct an indexed reference given a \p StoreOrLoadInst instruction. 53 IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI, 54 ScalarEvolution &SE); 55 56 bool isValid() const { return IsValid; } 57 const SCEV *getBasePointer() const { return BasePointer; } 58 size_t getNumSubscripts() const { return Subscripts.size(); } 59 const SCEV *getSubscript(unsigned SubNum) const { 60 assert(SubNum < getNumSubscripts() && "Invalid subscript number"); 61 return Subscripts[SubNum]; 62 } 63 const SCEV *getFirstSubscript() const { 64 assert(!Subscripts.empty() && "Expecting non-empty container"); 65 return Subscripts.front(); 66 } 67 const SCEV *getLastSubscript() const { 68 assert(!Subscripts.empty() && "Expecting non-empty container"); 69 return Subscripts.back(); 70 } 71 72 /// Return true/false if the current object and the indexed reference \p Other 73 /// are/aren't in the same cache line of size \p CLS. Two references are in 74 /// the same chace line iff the distance between them in the innermost 75 /// dimension is less than the cache line size. Return std::nullopt if unsure. 76 std::optional<bool> hasSpacialReuse(const IndexedReference &Other, 77 unsigned CLS, AAResults &AA) const; 78 79 /// Return true if the current object and the indexed reference \p Other 80 /// have distance smaller than \p MaxDistance in the dimension associated with 81 /// the given loop \p L. Return false if the distance is not smaller than \p 82 /// MaxDistance and std::nullopt if unsure. 83 std::optional<bool> hasTemporalReuse(const IndexedReference &Other, 84 unsigned MaxDistance, const Loop &L, 85 DependenceInfo &DI, AAResults &AA) const; 86 87 /// Compute the cost of the reference w.r.t. the given loop \p L when it is 88 /// considered in the innermost position in the loop nest. 89 /// The cost is defined as: 90 /// - equal to one if the reference is loop invariant, or 91 /// - equal to '(TripCount * stride) / cache_line_size' if: 92 /// + the reference stride is less than the cache line size, and 93 /// + the coefficient of this loop's index variable used in all other 94 /// subscripts is zero 95 /// - or otherwise equal to 'TripCount'. 96 CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const; 97 98 private: 99 /// Attempt to delinearize the indexed reference. 100 bool delinearize(const LoopInfo &LI); 101 102 /// Attempt to delinearize \p AccessFn for fixed-size arrays. 103 bool tryDelinearizeFixedSize(const SCEV *AccessFn, 104 SmallVectorImpl<const SCEV *> &Subscripts); 105 106 /// Return true if the index reference is invariant with respect to loop \p L. 107 bool isLoopInvariant(const Loop &L) const; 108 109 /// Return true if the indexed reference is 'consecutive' in loop \p L. 110 /// An indexed reference is 'consecutive' if the only coefficient that uses 111 /// the loop induction variable is the rightmost one, and the access stride is 112 /// smaller than the cache line size \p CLS. Provide a valid \p Stride value 113 /// if the indexed reference is 'consecutive'. 114 bool isConsecutive(const Loop &L, const SCEV *&Stride, unsigned CLS) const; 115 116 /// Retrieve the index of the subscript corresponding to the given loop \p 117 /// L. Return a zero-based positive index if the subscript index is 118 /// succesfully located and a negative value otherwise. For example given the 119 /// indexed reference 'A[i][2j+1][3k+2]', the call 120 /// 'getSubscriptIndex(loop-k)' would return value 2. 121 int getSubscriptIndex(const Loop &L) const; 122 123 /// Return the coefficient used in the rightmost dimension. 124 const SCEV *getLastCoefficient() const; 125 126 /// Return true if the coefficient corresponding to induction variable of 127 /// loop \p L in the given \p Subscript is zero or is loop invariant in \p L. 128 bool isCoeffForLoopZeroOrInvariant(const SCEV &Subscript, 129 const Loop &L) const; 130 131 /// Verify that the given \p Subscript is 'well formed' (must be a simple add 132 /// recurrence). 133 bool isSimpleAddRecurrence(const SCEV &Subscript, const Loop &L) const; 134 135 /// Return true if the given reference \p Other is definetely aliased with 136 /// the indexed reference represented by this class. 137 bool isAliased(const IndexedReference &Other, AAResults &AA) const; 138 139 private: 140 /// True if the reference can be delinearized, false otherwise. 141 bool IsValid = false; 142 143 /// Represent the memory reference instruction. 144 Instruction &StoreOrLoadInst; 145 146 /// The base pointer of the memory reference. 147 const SCEV *BasePointer = nullptr; 148 149 /// The subscript (indexes) of the memory reference. 150 SmallVector<const SCEV *, 3> Subscripts; 151 152 /// The dimensions of the memory reference. 153 SmallVector<const SCEV *, 3> Sizes; 154 155 ScalarEvolution &SE; 156 }; 157 158 /// A reference group represents a set of memory references that exhibit 159 /// temporal or spacial reuse. Two references belong to the same 160 /// reference group with respect to a inner loop L iff: 161 /// 1. they have a loop independent dependency, or 162 /// 2. they have a loop carried dependence with a small dependence distance 163 /// (e.g. less than 2) carried by the inner loop, or 164 /// 3. they refer to the same array, and the subscript in their innermost 165 /// dimension is less than or equal to 'd' (where 'd' is less than the cache 166 /// line size) 167 /// 168 /// Intuitively a reference group represents memory references that access 169 /// the same cache line. Conditions 1,2 above account for temporal reuse, while 170 /// contition 3 accounts for spacial reuse. 171 using ReferenceGroupTy = SmallVector<std::unique_ptr<IndexedReference>, 8>; 172 using ReferenceGroupsTy = SmallVector<ReferenceGroupTy, 8>; 173 174 /// \c CacheCost represents the estimated cost of a inner loop as the number of 175 /// cache lines used by the memory references it contains. 176 /// The 'cache cost' of a loop 'L' in a loop nest 'LN' is computed as the sum of 177 /// the cache costs of all of its reference groups when the loop is considered 178 /// to be in the innermost position in the nest. 179 /// A reference group represents memory references that fall into the same cache 180 /// line. Each reference group is analysed with respect to the innermost loop in 181 /// a loop nest. The cost of a reference is defined as follow: 182 /// - one if it is loop invariant w.r.t the innermost loop, 183 /// - equal to the loop trip count divided by the cache line times the 184 /// reference stride if the reference stride is less than the cache line 185 /// size (CLS), and the coefficient of this loop's index variable used in all 186 /// other subscripts is zero (e.g. RefCost = TripCount/(CLS/RefStride)) 187 /// - equal to the innermost loop trip count if the reference stride is greater 188 /// or equal to the cache line size CLS. 189 class CacheCost { 190 friend raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC); 191 using LoopTripCountTy = std::pair<const Loop *, unsigned>; 192 using LoopCacheCostTy = std::pair<const Loop *, CacheCostTy>; 193 194 public: 195 static CacheCostTy constexpr InvalidCost = -1; 196 197 /// Construct a CacheCost object for the loop nest described by \p Loops. 198 /// The optional parameter \p TRT can be used to specify the max. distance 199 /// between array elements accessed in a loop so that the elements are 200 /// classified to have temporal reuse. 201 CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE, 202 TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI, 203 std::optional<unsigned> TRT = std::nullopt); 204 205 /// Create a CacheCost for the loop nest rooted by \p Root. 206 /// The optional parameter \p TRT can be used to specify the max. distance 207 /// between array elements accessed in a loop so that the elements are 208 /// classified to have temporal reuse. 209 static std::unique_ptr<CacheCost> 210 getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI, 211 std::optional<unsigned> TRT = std::nullopt); 212 213 /// Return the estimated cost of loop \p L if the given loop is part of the 214 /// loop nest associated with this object. Return -1 otherwise. 215 CacheCostTy getLoopCost(const Loop &L) const { 216 auto IT = llvm::find_if(LoopCosts, [&L](const LoopCacheCostTy &LCC) { 217 return LCC.first == &L; 218 }); 219 return (IT != LoopCosts.end()) ? (*IT).second : -1; 220 } 221 222 /// Return the estimated ordered loop costs. 223 ArrayRef<LoopCacheCostTy> getLoopCosts() const { return LoopCosts; } 224 225 private: 226 /// Calculate the cache footprint of each loop in the nest (when it is 227 /// considered to be in the innermost position). 228 void calculateCacheFootprint(); 229 230 /// Partition store/load instructions in the loop nest into reference groups. 231 /// Two or more memory accesses belong in the same reference group if they 232 /// share the same cache line. 233 bool populateReferenceGroups(ReferenceGroupsTy &RefGroups) const; 234 235 /// Calculate the cost of the given loop \p L assuming it is the innermost 236 /// loop in nest. 237 CacheCostTy computeLoopCacheCost(const Loop &L, 238 const ReferenceGroupsTy &RefGroups) const; 239 240 /// Compute the cost of a representative reference in reference group \p RG 241 /// when the given loop \p L is considered as the innermost loop in the nest. 242 /// The computed cost is an estimate for the number of cache lines used by the 243 /// reference group. The representative reference cost is defined as: 244 /// - equal to one if the reference is loop invariant, or 245 /// - equal to '(TripCount * stride) / cache_line_size' if (a) loop \p L's 246 /// induction variable is used only in the reference subscript associated 247 /// with loop \p L, and (b) the reference stride is less than the cache 248 /// line size, or 249 /// - TripCount otherwise 250 CacheCostTy computeRefGroupCacheCost(const ReferenceGroupTy &RG, 251 const Loop &L) const; 252 253 /// Sort the LoopCosts vector by decreasing cache cost. 254 void sortLoopCosts() { 255 stable_sort(LoopCosts, 256 [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) { 257 return A.second > B.second; 258 }); 259 } 260 261 private: 262 /// Loops in the loop nest associated with this object. 263 LoopVectorTy Loops; 264 265 /// Trip counts for the loops in the loop nest associated with this object. 266 SmallVector<LoopTripCountTy, 3> TripCounts; 267 268 /// Cache costs for the loops in the loop nest associated with this object. 269 SmallVector<LoopCacheCostTy, 3> LoopCosts; 270 271 /// The max. distance between array elements accessed in a loop so that the 272 /// elements are classified to have temporal reuse. 273 std::optional<unsigned> TRT; 274 275 const LoopInfo &LI; 276 ScalarEvolution &SE; 277 TargetTransformInfo &TTI; 278 AAResults &AA; 279 DependenceInfo &DI; 280 }; 281 282 raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R); 283 raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC); 284 285 /// Printer pass for the \c CacheCost results. 286 class LoopCachePrinterPass : public PassInfoMixin<LoopCachePrinterPass> { 287 raw_ostream &OS; 288 289 public: 290 explicit LoopCachePrinterPass(raw_ostream &OS) : OS(OS) {} 291 292 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 293 LoopStandardAnalysisResults &AR, LPMUpdater &U); 294 295 static bool isRequired() { return true; } 296 }; 297 298 } // namespace llvm 299 300 #endif // LLVM_ANALYSIS_LOOPCACHEANALYSIS_H 301