File: | llvm/lib/Analysis/LoopCacheAnalysis.cpp |
Warning: | line 429, column 10 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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/ScalarEvolutionExpressions.h" | |||
33 | #include "llvm/Support/CommandLine.h" | |||
34 | #include "llvm/Support/Debug.h" | |||
35 | ||||
36 | using namespace llvm; | |||
37 | ||||
38 | #define DEBUG_TYPE"loop-cache-cost" "loop-cache-cost" | |||
39 | ||||
40 | static cl::opt<unsigned> DefaultTripCount( | |||
41 | "default-trip-count", cl::init(100), cl::Hidden, | |||
42 | cl::desc("Use this to specify the default trip count of a loop")); | |||
43 | ||||
44 | // In this analysis two array references are considered to exhibit temporal | |||
45 | // reuse if they access either the same memory location, or a memory location | |||
46 | // with distance smaller than a configurable threshold. | |||
47 | static cl::opt<unsigned> TemporalReuseThreshold( | |||
48 | "temporal-reuse-threshold", cl::init(2), cl::Hidden, | |||
49 | cl::desc("Use this to specify the max. distance between array elements " | |||
50 | "accessed in a loop so that the elements are classified to have " | |||
51 | "temporal reuse")); | |||
52 | ||||
53 | /// Retrieve the innermost loop in the given loop nest \p Loops. It returns a | |||
54 | /// nullptr if any loops in the loop vector supplied has more than one sibling. | |||
55 | /// The loop vector is expected to contain loops collected in breadth-first | |||
56 | /// order. | |||
57 | static Loop *getInnerMostLoop(const LoopVectorTy &Loops) { | |||
58 | assert(!Loops.empty() && "Expecting a non-empy loop vector")((!Loops.empty() && "Expecting a non-empy loop vector" ) ? static_cast<void> (0) : __assert_fail ("!Loops.empty() && \"Expecting a non-empy loop vector\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 58, __PRETTY_FUNCTION__)); | |||
59 | ||||
60 | Loop *LastLoop = Loops.back(); | |||
61 | Loop *ParentLoop = LastLoop->getParentLoop(); | |||
62 | ||||
63 | if (ParentLoop == nullptr) { | |||
64 | assert(Loops.size() == 1 && "Expecting a single loop")((Loops.size() == 1 && "Expecting a single loop") ? static_cast <void> (0) : __assert_fail ("Loops.size() == 1 && \"Expecting a single loop\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 64, __PRETTY_FUNCTION__)); | |||
65 | return LastLoop; | |||
66 | } | |||
67 | ||||
68 | return (llvm::is_sorted(Loops, | |||
69 | [](const Loop *L1, const Loop *L2) { | |||
70 | return L1->getLoopDepth() < L2->getLoopDepth(); | |||
71 | })) | |||
72 | ? LastLoop | |||
73 | : nullptr; | |||
74 | } | |||
75 | ||||
76 | static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize, | |||
77 | const Loop &L, ScalarEvolution &SE) { | |||
78 | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&AccessFn); | |||
79 | if (!AR || !AR->isAffine()) | |||
80 | return false; | |||
81 | ||||
82 | assert(AR->getLoop() && "AR should have a loop")((AR->getLoop() && "AR should have a loop") ? static_cast <void> (0) : __assert_fail ("AR->getLoop() && \"AR should have a loop\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 82, __PRETTY_FUNCTION__)); | |||
83 | ||||
84 | // Check that start and increment are not add recurrences. | |||
85 | const SCEV *Start = AR->getStart(); | |||
86 | const SCEV *Step = AR->getStepRecurrence(SE); | |||
87 | if (isa<SCEVAddRecExpr>(Start) || isa<SCEVAddRecExpr>(Step)) | |||
88 | return false; | |||
89 | ||||
90 | // Check that start and increment are both invariant in the loop. | |||
91 | if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L)) | |||
92 | return false; | |||
93 | ||||
94 | const SCEV *StepRec = AR->getStepRecurrence(SE); | |||
95 | if (StepRec && SE.isKnownNegative(StepRec)) | |||
96 | StepRec = SE.getNegativeSCEV(StepRec); | |||
97 | ||||
98 | return StepRec == &ElemSize; | |||
99 | } | |||
100 | ||||
101 | /// Compute the trip count for the given loop \p L. Return the SCEV expression | |||
102 | /// for the trip count or nullptr if it cannot be computed. | |||
103 | static const SCEV *computeTripCount(const Loop &L, ScalarEvolution &SE) { | |||
104 | const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(&L); | |||
105 | if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) || | |||
106 | !isa<SCEVConstant>(BackedgeTakenCount)) | |||
107 | return nullptr; | |||
108 | ||||
109 | return SE.getAddExpr(BackedgeTakenCount, | |||
110 | SE.getOne(BackedgeTakenCount->getType())); | |||
111 | } | |||
112 | ||||
113 | //===----------------------------------------------------------------------===// | |||
114 | // IndexedReference implementation | |||
115 | // | |||
116 | raw_ostream &llvm::operator<<(raw_ostream &OS, const IndexedReference &R) { | |||
117 | if (!R.IsValid) { | |||
118 | OS << R.StoreOrLoadInst; | |||
119 | OS << ", IsValid=false."; | |||
120 | return OS; | |||
121 | } | |||
122 | ||||
123 | OS << *R.BasePointer; | |||
124 | for (const SCEV *Subscript : R.Subscripts) | |||
125 | OS << "[" << *Subscript << "]"; | |||
126 | ||||
127 | OS << ", Sizes: "; | |||
128 | for (const SCEV *Size : R.Sizes) | |||
129 | OS << "[" << *Size << "]"; | |||
130 | ||||
131 | return OS; | |||
132 | } | |||
133 | ||||
134 | IndexedReference::IndexedReference(Instruction &StoreOrLoadInst, | |||
135 | const LoopInfo &LI, ScalarEvolution &SE) | |||
136 | : StoreOrLoadInst(StoreOrLoadInst), SE(SE) { | |||
137 | assert((isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst>(StoreOrLoadInst)) &&(((isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst> (StoreOrLoadInst)) && "Expecting a load or store instruction" ) ? static_cast<void> (0) : __assert_fail ("(isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst>(StoreOrLoadInst)) && \"Expecting a load or store instruction\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 138, __PRETTY_FUNCTION__)) | |||
138 | "Expecting a load or store instruction")(((isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst> (StoreOrLoadInst)) && "Expecting a load or store instruction" ) ? static_cast<void> (0) : __assert_fail ("(isa<StoreInst>(StoreOrLoadInst) || isa<LoadInst>(StoreOrLoadInst)) && \"Expecting a load or store instruction\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 138, __PRETTY_FUNCTION__)); | |||
139 | ||||
140 | IsValid = delinearize(LI); | |||
141 | if (IsValid) | |||
142 | LLVM_DEBUG(dbgs().indent(2) << "Succesfully delinearized: " << *thisdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "Succesfully delinearized: " << *this << "\n"; } } while (false) | |||
143 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "Succesfully delinearized: " << *this << "\n"; } } while (false); | |||
144 | } | |||
145 | ||||
146 | Optional<bool> IndexedReference::hasSpacialReuse(const IndexedReference &Other, | |||
147 | unsigned CLS, | |||
148 | AliasAnalysis &AA) const { | |||
149 | assert(IsValid && "Expecting a valid reference")((IsValid && "Expecting a valid reference") ? static_cast <void> (0) : __assert_fail ("IsValid && \"Expecting a valid reference\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 149, __PRETTY_FUNCTION__)); | |||
150 | ||||
151 | if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) { | |||
152 | LLVM_DEBUG(dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse: different base pointers\n" ; } } while (false) | |||
153 | << "No spacial reuse: different base pointers\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse: different base pointers\n" ; } } while (false); | |||
154 | return false; | |||
155 | } | |||
156 | ||||
157 | unsigned NumSubscripts = getNumSubscripts(); | |||
158 | if (NumSubscripts != Other.getNumSubscripts()) { | |||
159 | LLVM_DEBUG(dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse: different number of subscripts\n" ; } } while (false) | |||
160 | << "No spacial reuse: different number of subscripts\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse: different number of subscripts\n" ; } } while (false); | |||
161 | return false; | |||
162 | } | |||
163 | ||||
164 | // all subscripts must be equal, except the leftmost one (the last one). | |||
165 | for (auto SubNum : seq<unsigned>(0, NumSubscripts - 1)) { | |||
166 | if (getSubscript(SubNum) != Other.getSubscript(SubNum)) { | |||
167 | LLVM_DEBUG(dbgs().indent(2) << "No spacial reuse, different subscripts: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse, different subscripts: " << "\n\t" << *getSubscript(SubNum) << "\n\t" << *Other.getSubscript(SubNum) << "\n"; } } while (false) | |||
168 | << "\n\t" << *getSubscript(SubNum) << "\n\t"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse, different subscripts: " << "\n\t" << *getSubscript(SubNum) << "\n\t" << *Other.getSubscript(SubNum) << "\n"; } } while (false) | |||
169 | << *Other.getSubscript(SubNum) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse, different subscripts: " << "\n\t" << *getSubscript(SubNum) << "\n\t" << *Other.getSubscript(SubNum) << "\n"; } } while (false); | |||
170 | return false; | |||
171 | } | |||
172 | } | |||
173 | ||||
174 | // the difference between the last subscripts must be less than the cache line | |||
175 | // size. | |||
176 | const SCEV *LastSubscript = getLastSubscript(); | |||
177 | const SCEV *OtherLastSubscript = Other.getLastSubscript(); | |||
178 | const SCEVConstant *Diff = dyn_cast<SCEVConstant>( | |||
179 | SE.getMinusSCEV(LastSubscript, OtherLastSubscript)); | |||
180 | ||||
181 | if (Diff == nullptr) { | |||
182 | LLVM_DEBUG(dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse, difference between subscript:\n\t" << *LastSubscript << "\n\t" << OtherLastSubscript << "\nis not constant.\n"; } } while (false) | |||
183 | << "No spacial reuse, difference between subscript:\n\t"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse, difference between subscript:\n\t" << *LastSubscript << "\n\t" << OtherLastSubscript << "\nis not constant.\n"; } } while (false) | |||
184 | << *LastSubscript << "\n\t" << OtherLastSubscriptdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse, difference between subscript:\n\t" << *LastSubscript << "\n\t" << OtherLastSubscript << "\nis not constant.\n"; } } while (false) | |||
185 | << "\nis not constant.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No spacial reuse, difference between subscript:\n\t" << *LastSubscript << "\n\t" << OtherLastSubscript << "\nis not constant.\n"; } } while (false); | |||
186 | return None; | |||
187 | } | |||
188 | ||||
189 | bool InSameCacheLine = (Diff->getValue()->getSExtValue() < CLS); | |||
190 | ||||
191 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { if (InSameCacheLine) dbgs().indent(2 ) << "Found spacial reuse.\n"; else dbgs().indent(2) << "No spacial reuse.\n"; }; } } while (false) | |||
192 | if (InSameCacheLine)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { if (InSameCacheLine) dbgs().indent(2 ) << "Found spacial reuse.\n"; else dbgs().indent(2) << "No spacial reuse.\n"; }; } } while (false) | |||
193 | dbgs().indent(2) << "Found spacial reuse.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { if (InSameCacheLine) dbgs().indent(2 ) << "Found spacial reuse.\n"; else dbgs().indent(2) << "No spacial reuse.\n"; }; } } while (false) | |||
194 | elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { if (InSameCacheLine) dbgs().indent(2 ) << "Found spacial reuse.\n"; else dbgs().indent(2) << "No spacial reuse.\n"; }; } } while (false) | |||
195 | dbgs().indent(2) << "No spacial reuse.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { if (InSameCacheLine) dbgs().indent(2 ) << "Found spacial reuse.\n"; else dbgs().indent(2) << "No spacial reuse.\n"; }; } } while (false) | |||
196 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { if (InSameCacheLine) dbgs().indent(2 ) << "Found spacial reuse.\n"; else dbgs().indent(2) << "No spacial reuse.\n"; }; } } while (false); | |||
197 | ||||
198 | return InSameCacheLine; | |||
199 | } | |||
200 | ||||
201 | Optional<bool> IndexedReference::hasTemporalReuse(const IndexedReference &Other, | |||
202 | unsigned MaxDistance, | |||
203 | const Loop &L, | |||
204 | DependenceInfo &DI, | |||
205 | AliasAnalysis &AA) const { | |||
206 | assert(IsValid && "Expecting a valid reference")((IsValid && "Expecting a valid reference") ? static_cast <void> (0) : __assert_fail ("IsValid && \"Expecting a valid reference\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 206, __PRETTY_FUNCTION__)); | |||
207 | ||||
208 | if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) { | |||
209 | LLVM_DEBUG(dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: different base pointer\n" ; } } while (false) | |||
210 | << "No temporal reuse: different base pointer\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: different base pointer\n" ; } } while (false); | |||
211 | return false; | |||
212 | } | |||
213 | ||||
214 | std::unique_ptr<Dependence> D = | |||
215 | DI.depends(&StoreOrLoadInst, &Other.StoreOrLoadInst, true); | |||
216 | ||||
217 | if (D == nullptr) { | |||
218 | LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: no dependence\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: no dependence\n" ; } } while (false); | |||
219 | return false; | |||
220 | } | |||
221 | ||||
222 | if (D->isLoopIndependent()) { | |||
223 | LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "Found temporal reuse\n" ; } } while (false); | |||
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>(Distance); | |||
235 | ||||
236 | if (SCEVConst == nullptr) { | |||
237 | LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: distance unknown\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance unknown\n" ; } } while (false); | |||
238 | return None; | |||
239 | } | |||
240 | ||||
241 | const ConstantInt &CI = *SCEVConst->getValue(); | |||
242 | if (Level != LoopDepth && !CI.isZero()) { | |||
243 | LLVM_DEBUG(dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance is not zero at depth=" << Level << "\n"; } } while (false) | |||
244 | << "No temporal reuse: distance is not zero at depth=" << Leveldo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance is not zero at depth=" << Level << "\n"; } } while (false) | |||
245 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance is not zero at depth=" << Level << "\n"; } } while (false); | |||
246 | return false; | |||
247 | } else if (Level == LoopDepth && CI.getSExtValue() > MaxDistance) { | |||
248 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance is greater than MaxDistance at depth=" << Level << "\n"; } } while (false) | |||
249 | dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance is greater than MaxDistance at depth=" << Level << "\n"; } } while (false) | |||
250 | << "No temporal reuse: distance is greater than MaxDistance at depth="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance is greater than MaxDistance at depth=" << Level << "\n"; } } while (false) | |||
251 | << Level << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "No temporal reuse: distance is greater than MaxDistance at depth=" << Level << "\n"; } } while (false); | |||
252 | return false; | |||
253 | } | |||
254 | } | |||
255 | ||||
256 | LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "Found temporal reuse\n" ; } } while (false); | |||
257 | return true; | |||
258 | } | |||
259 | ||||
260 | CacheCostTy IndexedReference::computeRefCost(const Loop &L, | |||
261 | unsigned CLS) const { | |||
262 | assert(IsValid && "Expecting a valid reference")((IsValid && "Expecting a valid reference") ? static_cast <void> (0) : __assert_fail ("IsValid && \"Expecting a valid reference\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 262, __PRETTY_FUNCTION__)); | |||
263 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs().indent(2) << "Computing cache cost for:\n" ; dbgs().indent(4) << *this << "\n"; }; } } while (false) | |||
264 | dbgs().indent(2) << "Computing cache cost for:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs().indent(2) << "Computing cache cost for:\n" ; dbgs().indent(4) << *this << "\n"; }; } } while (false) | |||
265 | dbgs().indent(4) << *this << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs().indent(2) << "Computing cache cost for:\n" ; dbgs().indent(4) << *this << "\n"; }; } } while (false) | |||
266 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs().indent(2) << "Computing cache cost for:\n" ; dbgs().indent(4) << *this << "\n"; }; } } while (false); | |||
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")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "Reference is loop invariant: RefCost=1\n" ; } } while (false); | |||
271 | return 1; | |||
272 | } | |||
273 | ||||
274 | const SCEV *TripCount = computeTripCount(L, SE); | |||
275 | if (!TripCount) { | |||
276 | LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Trip count of loop " << L.getName() << " could not be computed, using DefaultTripCount\n" ; } } while (false) | |||
277 | << " could not be computed, using DefaultTripCount\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Trip count of loop " << L.getName() << " could not be computed, using DefaultTripCount\n" ; } } while (false); | |||
278 | const SCEV *ElemSize = Sizes.back(); | |||
279 | TripCount = SE.getConstant(ElemSize->getType(), DefaultTripCount); | |||
280 | } | |||
281 | LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "TripCount=" << * TripCount << "\n"; } } while (false); | |||
282 | ||||
283 | // If the indexed reference is 'consecutive' the cost is | |||
284 | // (TripCount*Stride)/CLS, otherwise the cost is TripCount. | |||
285 | const SCEV *RefCost = TripCount; | |||
286 | ||||
287 | if (isConsecutive(L, CLS)) { | |||
288 | const SCEV *Coeff = getLastCoefficient(); | |||
289 | const SCEV *ElemSize = Sizes.back(); | |||
290 | const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize); | |||
291 | const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS); | |||
292 | Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType()); | |||
293 | if (SE.isKnownNegative(Stride)) | |||
294 | Stride = SE.getNegativeSCEV(Stride); | |||
295 | Stride = SE.getNoopOrAnyExtend(Stride, WiderType); | |||
296 | TripCount = SE.getNoopOrAnyExtend(TripCount, WiderType); | |||
297 | const SCEV *Numerator = SE.getMulExpr(Stride, TripCount); | |||
298 | RefCost = SE.getUDivExpr(Numerator, CacheLineSize); | |||
299 | ||||
300 | LLVM_DEBUG(dbgs().indent(4)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "Access is consecutive: RefCost=(TripCount*Stride)/CLS=" << *RefCost << "\n"; } } while (false) | |||
301 | << "Access is consecutive: RefCost=(TripCount*Stride)/CLS="do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "Access is consecutive: RefCost=(TripCount*Stride)/CLS=" << *RefCost << "\n"; } } while (false) | |||
302 | << *RefCost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "Access is consecutive: RefCost=(TripCount*Stride)/CLS=" << *RefCost << "\n"; } } while (false); | |||
303 | } else | |||
304 | LLVM_DEBUG(dbgs().indent(4)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "Access is not consecutive: RefCost=TripCount=" << *RefCost << "\n"; } } while (false) | |||
305 | << "Access is not consecutive: RefCost=TripCount=" << *RefCostdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "Access is not consecutive: RefCost=TripCount=" << *RefCost << "\n"; } } while (false) | |||
306 | << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "Access is not consecutive: RefCost=TripCount=" << *RefCost << "\n"; } } while (false); | |||
307 | ||||
308 | // Attempt to fold RefCost into a constant. | |||
309 | if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost)) | |||
310 | return ConstantCost->getValue()->getSExtValue(); | |||
311 | ||||
312 | LLVM_DEBUG(dbgs().indent(4)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "RefCost is not a constant! Setting to RefCost=InvalidCost " "(invalid value).\n"; } } while (false) | |||
313 | << "RefCost is not a constant! Setting to RefCost=InvalidCost "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "RefCost is not a constant! Setting to RefCost=InvalidCost " "(invalid value).\n"; } } while (false) | |||
314 | "(invalid value).\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(4) << "RefCost is not a constant! Setting to RefCost=InvalidCost " "(invalid value).\n"; } } while (false); | |||
315 | ||||
316 | return CacheCost::InvalidCost; | |||
317 | } | |||
318 | ||||
319 | bool IndexedReference::delinearize(const LoopInfo &LI) { | |||
320 | assert(Subscripts.empty() && "Subscripts should be empty")((Subscripts.empty() && "Subscripts should be empty") ? static_cast<void> (0) : __assert_fail ("Subscripts.empty() && \"Subscripts should be empty\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 320, __PRETTY_FUNCTION__)); | |||
321 | assert(Sizes.empty() && "Sizes should be empty")((Sizes.empty() && "Sizes should be empty") ? static_cast <void> (0) : __assert_fail ("Sizes.empty() && \"Sizes should be empty\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 321, __PRETTY_FUNCTION__)); | |||
322 | assert(!IsValid && "Should be called once from the constructor")((!IsValid && "Should be called once from the constructor" ) ? static_cast<void> (0) : __assert_fail ("!IsValid && \"Should be called once from the constructor\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 322, __PRETTY_FUNCTION__)); | |||
323 | LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n"; } } while (false); | |||
324 | ||||
325 | const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst); | |||
326 | const BasicBlock *BB = StoreOrLoadInst.getParent(); | |||
327 | ||||
328 | if (Loop *L = LI.getLoopFor(BB)) { | |||
329 | const SCEV *AccessFn = | |||
330 | SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L); | |||
331 | ||||
332 | BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn)); | |||
333 | if (BasePointer == nullptr) { | |||
334 | LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "ERROR: failed to delinearize, can't identify base pointer\n" ; } } while (false) | |||
335 | dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "ERROR: failed to delinearize, can't identify base pointer\n" ; } } while (false) | |||
336 | << "ERROR: failed to delinearize, can't identify base pointer\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "ERROR: failed to delinearize, can't identify base pointer\n" ; } } while (false); | |||
337 | return false; | |||
338 | } | |||
339 | ||||
340 | AccessFn = SE.getMinusSCEV(AccessFn, BasePointer); | |||
341 | ||||
342 | LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "In Loop '" << L->getName() << "', AccessFn: " << *AccessFn << "\n"; } } while (false) | |||
343 | << "', AccessFn: " << *AccessFn << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "In Loop '" << L->getName() << "', AccessFn: " << *AccessFn << "\n"; } } while (false); | |||
344 | ||||
345 | SE.delinearize(AccessFn, Subscripts, Sizes, | |||
346 | SE.getElementSize(&StoreOrLoadInst)); | |||
347 | ||||
348 | if (Subscripts.empty() || Sizes.empty() || | |||
349 | Subscripts.size() != Sizes.size()) { | |||
350 | // Attempt to determine whether we have a single dimensional array access. | |||
351 | // before giving up. | |||
352 | if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) { | |||
353 | LLVM_DEBUG(dbgs().indent(2)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "ERROR: failed to delinearize reference\n" ; } } while (false) | |||
354 | << "ERROR: failed to delinearize reference\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "ERROR: failed to delinearize reference\n" ; } } while (false); | |||
355 | Subscripts.clear(); | |||
356 | Sizes.clear(); | |||
357 | return false; | |||
358 | } | |||
359 | ||||
360 | // The array may be accessed in reverse, for example: | |||
361 | // for (i = N; i > 0; i--) | |||
362 | // A[i] = 0; | |||
363 | // In this case, reconstruct the access function using the absolute value | |||
364 | // of the step recurrence. | |||
365 | const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn); | |||
366 | const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr; | |||
367 | ||||
368 | if (StepRec && SE.isKnownNegative(StepRec)) | |||
369 | AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(), | |||
370 | SE.getNegativeSCEV(StepRec), | |||
371 | AccessFnAR->getLoop(), | |||
372 | AccessFnAR->getNoWrapFlags()); | |||
373 | const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize); | |||
374 | Subscripts.push_back(Div); | |||
375 | Sizes.push_back(ElemSize); | |||
376 | } | |||
377 | ||||
378 | return all_of(Subscripts, [&](const SCEV *Subscript) { | |||
379 | return isSimpleAddRecurrence(*Subscript, *L); | |||
380 | }); | |||
381 | } | |||
382 | ||||
383 | return false; | |||
384 | } | |||
385 | ||||
386 | bool IndexedReference::isLoopInvariant(const Loop &L) const { | |||
387 | Value *Addr = getPointerOperand(&StoreOrLoadInst); | |||
388 | assert(Addr != nullptr && "Expecting either a load or a store instruction")((Addr != nullptr && "Expecting either a load or a store instruction" ) ? static_cast<void> (0) : __assert_fail ("Addr != nullptr && \"Expecting either a load or a store instruction\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 388, __PRETTY_FUNCTION__)); | |||
389 | assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable")((SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable" ) ? static_cast<void> (0) : __assert_fail ("SE.isSCEVable(Addr->getType()) && \"Addr should be SCEVable\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 389, __PRETTY_FUNCTION__)); | |||
390 | ||||
391 | if (SE.isLoopInvariant(SE.getSCEV(Addr), &L)) | |||
392 | return true; | |||
393 | ||||
394 | // The indexed reference is loop invariant if none of the coefficients use | |||
395 | // the loop induction variable. | |||
396 | bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) { | |||
397 | return isCoeffForLoopZeroOrInvariant(*Subscript, L); | |||
398 | }); | |||
399 | ||||
400 | return allCoeffForLoopAreZero; | |||
401 | } | |||
402 | ||||
403 | bool IndexedReference::isConsecutive(const Loop &L, unsigned CLS) const { | |||
404 | // The indexed reference is 'consecutive' if the only coefficient that uses | |||
405 | // the loop induction variable is the last one... | |||
406 | const SCEV *LastSubscript = Subscripts.back(); | |||
407 | for (const SCEV *Subscript : Subscripts) { | |||
408 | if (Subscript == LastSubscript) | |||
409 | continue; | |||
410 | if (!isCoeffForLoopZeroOrInvariant(*Subscript, L)) | |||
411 | return false; | |||
412 | } | |||
413 | ||||
414 | // ...and the access stride is less than the cache line size. | |||
415 | const SCEV *Coeff = getLastCoefficient(); | |||
416 | const SCEV *ElemSize = Sizes.back(); | |||
417 | const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize); | |||
418 | const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS); | |||
419 | ||||
420 | Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride; | |||
421 | return SE.isKnownPredicate(ICmpInst::ICMP_ULT, Stride, CacheLineSize); | |||
422 | } | |||
423 | ||||
424 | const SCEV *IndexedReference::getLastCoefficient() const { | |||
425 | const SCEV *LastSubscript = getLastSubscript(); | |||
426 | assert(isa<SCEVAddRecExpr>(LastSubscript) &&((isa<SCEVAddRecExpr>(LastSubscript) && "Expecting a SCEV add recurrence expression" ) ? static_cast<void> (0) : __assert_fail ("isa<SCEVAddRecExpr>(LastSubscript) && \"Expecting a SCEV add recurrence expression\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 427, __PRETTY_FUNCTION__)) | |||
427 | "Expecting a SCEV add recurrence expression")((isa<SCEVAddRecExpr>(LastSubscript) && "Expecting a SCEV add recurrence expression" ) ? static_cast<void> (0) : __assert_fail ("isa<SCEVAddRecExpr>(LastSubscript) && \"Expecting a SCEV add recurrence expression\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 427, __PRETTY_FUNCTION__)); | |||
428 | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LastSubscript); | |||
429 | return AR->getStepRecurrence(SE); | |||
| ||||
430 | } | |||
431 | ||||
432 | bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript, | |||
433 | const Loop &L) const { | |||
434 | const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript); | |||
435 | return (AR != nullptr) ? AR->getLoop() != &L | |||
436 | : SE.isLoopInvariant(&Subscript, &L); | |||
437 | } | |||
438 | ||||
439 | bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript, | |||
440 | const Loop &L) const { | |||
441 | if (!isa<SCEVAddRecExpr>(Subscript)) | |||
442 | return false; | |||
443 | ||||
444 | const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript); | |||
445 | assert(AR->getLoop() && "AR should have a loop")((AR->getLoop() && "AR should have a loop") ? static_cast <void> (0) : __assert_fail ("AR->getLoop() && \"AR should have a loop\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 445, __PRETTY_FUNCTION__)); | |||
446 | ||||
447 | if (!AR->isAffine()) | |||
448 | return false; | |||
449 | ||||
450 | const SCEV *Start = AR->getStart(); | |||
451 | const SCEV *Step = AR->getStepRecurrence(SE); | |||
452 | ||||
453 | if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L)) | |||
454 | return false; | |||
455 | ||||
456 | return true; | |||
457 | } | |||
458 | ||||
459 | bool IndexedReference::isAliased(const IndexedReference &Other, | |||
460 | AliasAnalysis &AA) const { | |||
461 | const auto &Loc1 = MemoryLocation::get(&StoreOrLoadInst); | |||
462 | const auto &Loc2 = MemoryLocation::get(&Other.StoreOrLoadInst); | |||
463 | return AA.isMustAlias(Loc1, Loc2); | |||
464 | } | |||
465 | ||||
466 | //===----------------------------------------------------------------------===// | |||
467 | // CacheCost implementation | |||
468 | // | |||
469 | raw_ostream &llvm::operator<<(raw_ostream &OS, const CacheCost &CC) { | |||
470 | for (const auto &LC : CC.LoopCosts) { | |||
471 | const Loop *L = LC.first; | |||
472 | OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n"; | |||
473 | } | |||
474 | return OS; | |||
475 | } | |||
476 | ||||
477 | CacheCost::CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, | |||
478 | ScalarEvolution &SE, TargetTransformInfo &TTI, | |||
479 | AliasAnalysis &AA, DependenceInfo &DI, | |||
480 | Optional<unsigned> TRT) | |||
481 | : Loops(Loops), TripCounts(), LoopCosts(), | |||
482 | TRT((TRT == None) ? Optional<unsigned>(TemporalReuseThreshold) : TRT), | |||
483 | LI(LI), SE(SE), TTI(TTI), AA(AA), DI(DI) { | |||
484 | assert(!Loops.empty() && "Expecting a non-empty loop vector.")((!Loops.empty() && "Expecting a non-empty loop vector." ) ? static_cast<void> (0) : __assert_fail ("!Loops.empty() && \"Expecting a non-empty loop vector.\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 484, __PRETTY_FUNCTION__)); | |||
485 | ||||
486 | for (const Loop *L : Loops) { | |||
487 | unsigned TripCount = SE.getSmallConstantTripCount(L); | |||
488 | TripCount = (TripCount == 0) ? DefaultTripCount : TripCount; | |||
489 | TripCounts.push_back({L, TripCount}); | |||
490 | } | |||
491 | ||||
492 | calculateCacheFootprint(); | |||
493 | } | |||
494 | ||||
495 | std::unique_ptr<CacheCost> | |||
496 | CacheCost::getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, | |||
497 | DependenceInfo &DI, Optional<unsigned> TRT) { | |||
498 | if (Root.getParentLoop()) { | |||
499 | LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Expecting the outermost loop in a loop nest\n" ; } } while (false); | |||
500 | return nullptr; | |||
501 | } | |||
502 | ||||
503 | LoopVectorTy Loops; | |||
504 | for (Loop *L : breadth_first(&Root)) | |||
505 | Loops.push_back(L); | |||
506 | ||||
507 | if (!getInnerMostLoop(Loops)) { | |||
508 | LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Cannot compute cache cost of loop nest with more " "than one innermost loop\n"; } } while (false) | |||
509 | "than one innermost loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Cannot compute cache cost of loop nest with more " "than one innermost loop\n"; } } while (false); | |||
510 | return nullptr; | |||
511 | } | |||
512 | ||||
513 | return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT); | |||
514 | } | |||
515 | ||||
516 | void CacheCost::calculateCacheFootprint() { | |||
517 | LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "POPULATING REFERENCE GROUPS\n" ; } } while (false); | |||
518 | ReferenceGroupsTy RefGroups; | |||
519 | if (!populateReferenceGroups(RefGroups)) | |||
520 | return; | |||
521 | ||||
522 | LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "COMPUTING LOOP CACHE COSTS\n" ; } } while (false); | |||
523 | for (const Loop *L : Loops) { | |||
524 | assert((std::find_if(LoopCosts.begin(), LoopCosts.end(),(((std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts .end()) && "Should not add duplicate element") ? static_cast <void> (0) : __assert_fail ("(std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts.end()) && \"Should not add duplicate element\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 528, __PRETTY_FUNCTION__)) | |||
525 | [L](const LoopCacheCostTy &LCC) {(((std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts .end()) && "Should not add duplicate element") ? static_cast <void> (0) : __assert_fail ("(std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts.end()) && \"Should not add duplicate element\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 528, __PRETTY_FUNCTION__)) | |||
526 | return LCC.first == L;(((std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts .end()) && "Should not add duplicate element") ? static_cast <void> (0) : __assert_fail ("(std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts.end()) && \"Should not add duplicate element\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 528, __PRETTY_FUNCTION__)) | |||
527 | }) == LoopCosts.end()) &&(((std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts .end()) && "Should not add duplicate element") ? static_cast <void> (0) : __assert_fail ("(std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts.end()) && \"Should not add duplicate element\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 528, __PRETTY_FUNCTION__)) | |||
528 | "Should not add duplicate element")(((std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts .end()) && "Should not add duplicate element") ? static_cast <void> (0) : __assert_fail ("(std::find_if(LoopCosts.begin(), LoopCosts.end(), [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) == LoopCosts.end()) && \"Should not add duplicate element\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 528, __PRETTY_FUNCTION__)); | |||
529 | CacheCostTy LoopCost = computeLoopCacheCost(*L, RefGroups); | |||
530 | LoopCosts.push_back(std::make_pair(L, LoopCost)); | |||
531 | } | |||
532 | ||||
533 | sortLoopCosts(); | |||
534 | RefGroups.clear(); | |||
535 | } | |||
536 | ||||
537 | bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const { | |||
538 | assert(RefGroups.empty() && "Reference groups should be empty")((RefGroups.empty() && "Reference groups should be empty" ) ? static_cast<void> (0) : __assert_fail ("RefGroups.empty() && \"Reference groups should be empty\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 538, __PRETTY_FUNCTION__)); | |||
539 | ||||
540 | unsigned CLS = TTI.getCacheLineSize(); | |||
541 | Loop *InnerMostLoop = getInnerMostLoop(Loops); | |||
542 | assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop")((InnerMostLoop != nullptr && "Expecting a valid innermost loop" ) ? static_cast<void> (0) : __assert_fail ("InnerMostLoop != nullptr && \"Expecting a valid innermost loop\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 542, __PRETTY_FUNCTION__)); | |||
543 | ||||
544 | for (BasicBlock *BB : InnerMostLoop->getBlocks()) { | |||
545 | for (Instruction &I : *BB) { | |||
546 | if (!isa<StoreInst>(I) && !isa<LoadInst>(I)) | |||
547 | continue; | |||
548 | ||||
549 | std::unique_ptr<IndexedReference> R(new IndexedReference(I, LI, SE)); | |||
550 | if (!R->isValid()) | |||
551 | continue; | |||
552 | ||||
553 | bool Added = false; | |||
554 | for (ReferenceGroupTy &RefGroup : RefGroups) { | |||
555 | const IndexedReference &Representative = *RefGroup.front().get(); | |||
556 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "References:\n"; dbgs ().indent(2) << *R << "\n"; dbgs().indent(2) << Representative << "\n"; }; } } while (false) | |||
557 | dbgs() << "References:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "References:\n"; dbgs ().indent(2) << *R << "\n"; dbgs().indent(2) << Representative << "\n"; }; } } while (false) | |||
558 | dbgs().indent(2) << *R << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "References:\n"; dbgs ().indent(2) << *R << "\n"; dbgs().indent(2) << Representative << "\n"; }; } } while (false) | |||
559 | dbgs().indent(2) << Representative << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "References:\n"; dbgs ().indent(2) << *R << "\n"; dbgs().indent(2) << Representative << "\n"; }; } } while (false) | |||
560 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "References:\n"; dbgs ().indent(2) << *R << "\n"; dbgs().indent(2) << Representative << "\n"; }; } } while (false); | |||
561 | ||||
562 | ||||
563 | // FIXME: Both positive and negative access functions will be placed | |||
564 | // into the same reference group, resulting in a bi-directional array | |||
565 | // access such as: | |||
566 | // for (i = N; i > 0; i--) | |||
567 | // A[i] = A[N - i]; | |||
568 | // having the same cost calculation as a single dimention access pattern | |||
569 | // for (i = 0; i < N; i++) | |||
570 | // A[i] = A[i]; | |||
571 | // when in actuality, depending on the array size, the first example | |||
572 | // should have a cost closer to 2x the second due to the two cache | |||
573 | // access per iteration from opposite ends of the array | |||
574 | Optional<bool> HasTemporalReuse = | |||
575 | R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA); | |||
576 | Optional<bool> HasSpacialReuse = | |||
577 | R->hasSpacialReuse(Representative, CLS, AA); | |||
578 | ||||
579 | if ((HasTemporalReuse.hasValue() && *HasTemporalReuse) || | |||
580 | (HasSpacialReuse.hasValue() && *HasSpacialReuse)) { | |||
581 | RefGroup.push_back(std::move(R)); | |||
582 | Added = true; | |||
583 | break; | |||
584 | } | |||
585 | } | |||
586 | ||||
587 | if (!Added) { | |||
588 | ReferenceGroupTy RG; | |||
589 | RG.push_back(std::move(R)); | |||
590 | RefGroups.push_back(std::move(RG)); | |||
591 | } | |||
592 | } | |||
593 | } | |||
594 | ||||
595 | if (RefGroups.empty()) | |||
596 | return false; | |||
597 | ||||
598 | LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
599 | dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
600 | int n = 1;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
601 | for (const ReferenceGroupTy &RG : RefGroups) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
602 | dbgs().indent(2) << "RefGroup " << n << ":\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
603 | for (const auto &IR : RG)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
604 | dbgs().indent(4) << *IR << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
605 | n++;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
606 | }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
607 | dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ) | |||
608 | })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { { dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n" ; int n = 1; for (const ReferenceGroupTy &RG : RefGroups) { dbgs().indent(2) << "RefGroup " << n << ":\n" ; for (const auto &IR : RG) dbgs().indent(4) << *IR << "\n"; n++; } dbgs() << "\n"; }; } } while (false ); | |||
609 | ||||
610 | return true; | |||
611 | } | |||
612 | ||||
613 | CacheCostTy | |||
614 | CacheCost::computeLoopCacheCost(const Loop &L, | |||
615 | const ReferenceGroupsTy &RefGroups) const { | |||
616 | if (!L.isLoopSimplifyForm()) | |||
617 | return InvalidCost; | |||
618 | ||||
619 | LLVM_DEBUG(dbgs() << "Considering loop '" << L.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Considering loop '" << L.getName() << "' as innermost loop.\n"; } } while (false ) | |||
620 | << "' as innermost loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs() << "Considering loop '" << L.getName() << "' as innermost loop.\n"; } } while (false ); | |||
621 | ||||
622 | // Compute the product of the trip counts of each other loop in the nest. | |||
623 | CacheCostTy TripCountsProduct = 1; | |||
624 | for (const auto &TC : TripCounts) { | |||
625 | if (TC.first == &L) | |||
626 | continue; | |||
627 | TripCountsProduct *= TC.second; | |||
628 | } | |||
629 | ||||
630 | CacheCostTy LoopCost = 0; | |||
631 | for (const ReferenceGroupTy &RG : RefGroups) { | |||
632 | CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L); | |||
633 | LoopCost += RefGroupCost * TripCountsProduct; | |||
634 | } | |||
635 | ||||
636 | LLVM_DEBUG(dbgs().indent(2) << "Loop '" << L.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "Loop '" << L.getName() << "' has cost=" << LoopCost << "\n"; } } while (false) | |||
637 | << "' has cost=" << LoopCost << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-cache-cost")) { dbgs().indent(2) << "Loop '" << L.getName() << "' has cost=" << LoopCost << "\n"; } } while (false); | |||
638 | ||||
639 | return LoopCost; | |||
640 | } | |||
641 | ||||
642 | CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG, | |||
643 | const Loop &L) const { | |||
644 | assert(!RG.empty() && "Reference group should have at least one member.")((!RG.empty() && "Reference group should have at least one member." ) ? static_cast<void> (0) : __assert_fail ("!RG.empty() && \"Reference group should have at least one member.\"" , "/build/llvm-toolchain-snapshot-12~++20200828100629+cfde93e5d6b/llvm/lib/Analysis/LoopCacheAnalysis.cpp" , 644, __PRETTY_FUNCTION__)); | |||
| ||||
645 | ||||
646 | const IndexedReference *Representative = RG.front().get(); | |||
647 | return Representative->computeRefCost(L, TTI.getCacheLineSize()); | |||
648 | } | |||
649 | ||||
650 | //===----------------------------------------------------------------------===// | |||
651 | // LoopCachePrinterPass implementation | |||
652 | // | |||
653 | PreservedAnalyses LoopCachePrinterPass::run(Loop &L, LoopAnalysisManager &AM, | |||
654 | LoopStandardAnalysisResults &AR, | |||
655 | LPMUpdater &U) { | |||
656 | Function *F = L.getHeader()->getParent(); | |||
657 | DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI); | |||
658 | ||||
659 | if (auto CC = CacheCost::getCacheCost(L, AR, DI)) | |||
660 | OS << *CC; | |||
661 | ||||
662 | return PreservedAnalyses::all(); | |||
663 | } |