LLVM  10.0.0svn
LoopCacheAnalysis.h
Go to the documentation of this file.
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 
20 #include "llvm/Analysis/LoopInfo.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/Pass.h"
26 
27 namespace llvm {
28 
29 class LPMUpdater;
30 using CacheCostTy = int64_t;
32 
33 /// Represents a memory reference as a base pointer and a set of indexing
34 /// operations. For example given the array reference A[i][2j+1][3k+2] in a
35 /// 3-dim loop nest:
36 /// for(i=0;i<n;++i)
37 /// for(j=0;j<m;++j)
38 /// for(k=0;k<o;++k)
39 /// ... A[i][2j+1][3k+2] ...
40 /// We expect:
41 /// BasePointer -> A
42 /// Subscripts -> [{0,+,1}<%for.i>][{1,+,2}<%for.j>][{2,+,3}<%for.k>]
43 /// Sizes -> [m][o][4]
45  friend raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R);
46 
47 public:
48  /// Construct an indexed reference given a \p StoreOrLoadInst instruction.
49  IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI,
50  ScalarEvolution &SE);
51 
52  bool isValid() const { return IsValid; }
53  const SCEV *getBasePointer() const { return BasePointer; }
54  size_t getNumSubscripts() const { return Subscripts.size(); }
55  const SCEV *getSubscript(unsigned SubNum) const {
56  assert(SubNum < getNumSubscripts() && "Invalid subscript number");
57  return Subscripts[SubNum];
58  }
59  const SCEV *getFirstSubscript() const {
60  assert(!Subscripts.empty() && "Expecting non-empty container");
61  return Subscripts.front();
62  }
63  const SCEV *getLastSubscript() const {
64  assert(!Subscripts.empty() && "Expecting non-empty container");
65  return Subscripts.back();
66  }
67 
68  /// Return true/false if the current object and the indexed reference \p Other
69  /// are/aren't in the same cache line of size \p CLS. Two references are in
70  /// the same chace line iff the distance between them in the innermost
71  /// dimension is less than the cache line size. Return None if unsure.
73  AliasAnalysis &AA) const;
74 
75  /// Return true if the current object and the indexed reference \p Other
76  /// have distance smaller than \p MaxDistance in the dimension associated with
77  /// the given loop \p L. Return false if the distance is not smaller than \p
78  /// MaxDistance and None if unsure.
80  unsigned MaxDistance, const Loop &L,
81  DependenceInfo &DI, AliasAnalysis &AA) const;
82 
83  /// Compute the cost of the reference w.r.t. the given loop \p L when it is
84  /// considered in the innermost position in the loop nest.
85  /// The cost is defined as:
86  /// - equal to one if the reference is loop invariant, or
87  /// - equal to '(TripCount * stride) / cache_line_size' if:
88  /// + the reference stride is less than the cache line size, and
89  /// + the coefficient of this loop's index variable used in all other
90  /// subscripts is zero
91  /// - or otherwise equal to 'TripCount'.
92  CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const;
93 
94 private:
95  /// Attempt to delinearize the indexed reference.
96  bool delinearize(const LoopInfo &LI);
97 
98  /// Return true if the index reference is invariant with respect to loop \p L.
99  bool isLoopInvariant(const Loop &L) const;
100 
101  /// Return true if the indexed reference is 'consecutive' in loop \p L.
102  /// An indexed reference is 'consecutive' if the only coefficient that uses
103  /// the loop induction variable is the rightmost one, and the access stride is
104  /// smaller than the cache line size \p CLS.
105  bool isConsecutive(const Loop &L, unsigned CLS) const;
106 
107  /// Return the coefficient used in the rightmost dimension.
108  const SCEV *getLastCoefficient() const;
109 
110  /// Return true if the coefficient corresponding to induction variable of
111  /// loop \p L in the given \p Subscript is zero or is loop invariant in \p L.
112  bool isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
113  const Loop &L) const;
114 
115  /// Verify that the given \p Subscript is 'well formed' (must be a simple add
116  /// recurrence).
117  bool isSimpleAddRecurrence(const SCEV &Subscript, const Loop &L) const;
118 
119  /// Return true if the given reference \p Other is definetely aliased with
120  /// the indexed reference represented by this class.
121  bool isAliased(const IndexedReference &Other, AliasAnalysis &AA) const;
122 
123 private:
124  /// True if the reference can be delinearized, false otherwise.
125  bool IsValid = false;
126 
127  /// Represent the memory reference instruction.
128  Instruction &StoreOrLoadInst;
129 
130  /// The base pointer of the memory reference.
131  const SCEV *BasePointer = nullptr;
132 
133  /// The subscript (indexes) of the memory reference.
134  SmallVector<const SCEV *, 3> Subscripts;
135 
136  /// The dimensions of the memory reference.
138 
139  ScalarEvolution &SE;
140 };
141 
142 /// A reference group represents a set of memory references that exhibit
143 /// temporal or spacial reuse. Two references belong to the same
144 /// reference group with respect to a inner loop L iff:
145 /// 1. they have a loop independent dependency, or
146 /// 2. they have a loop carried dependence with a small dependence distance
147 /// (e.g. less than 2) carried by the inner loop, or
148 /// 3. they refer to the same array, and the subscript in their innermost
149 /// dimension is less than or equal to 'd' (where 'd' is less than the cache
150 /// line size)
151 ///
152 /// Intuitively a reference group represents memory references that access
153 /// the same cache line. Conditions 1,2 above account for temporal reuse, while
154 /// contition 3 accounts for spacial reuse.
157 
158 /// \c CacheCost represents the estimated cost of a inner loop as the number of
159 /// cache lines used by the memory references it contains.
160 /// The 'cache cost' of a loop 'L' in a loop nest 'LN' is computed as the sum of
161 /// the cache costs of all of its reference groups when the loop is considered
162 /// to be in the innermost position in the nest.
163 /// A reference group represents memory references that fall into the same cache
164 /// line. Each reference group is analysed with respect to the innermost loop in
165 /// a loop nest. The cost of a reference is defined as follow:
166 /// - one if it is loop invariant w.r.t the innermost loop,
167 /// - equal to the loop trip count divided by the cache line times the
168 /// reference stride if the reference stride is less than the cache line
169 /// size (CLS), and the coefficient of this loop's index variable used in all
170 /// other subscripts is zero (e.g. RefCost = TripCount/(CLS/RefStride))
171 /// - equal to the innermost loop trip count if the reference stride is greater
172 /// or equal to the cache line size CLS.
173 class CacheCost {
174  friend raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC);
175  using LoopTripCountTy = std::pair<const Loop *, unsigned>;
176  using LoopCacheCostTy = std::pair<const Loop *, CacheCostTy>;
177 
178 public:
179  static CacheCostTy constexpr InvalidCost = -1;
180 
181  /// Construct a CacheCost object for the loop nest described by \p Loops.
182  /// The optional parameter \p TRT can be used to specify the max. distance
183  /// between array elements accessed in a loop so that the elements are
184  /// classified to have temporal reuse.
185  CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE,
187  Optional<unsigned> TRT = None);
188 
189  /// Create a CacheCost for the loop nest rooted by \p Root.
190  /// The optional parameter \p TRT can be used to specify the max. distance
191  /// between array elements accessed in a loop so that the elements are
192  /// classified to have temporal reuse.
193  static std::unique_ptr<CacheCost>
194  getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI,
195  Optional<unsigned> TRT = None);
196 
197  /// Return the estimated cost of loop \p L if the given loop is part of the
198  /// loop nest associated with this object. Return -1 otherwise.
199  CacheCostTy getLoopCost(const Loop &L) const {
200  auto IT = std::find_if(
201  LoopCosts.begin(), LoopCosts.end(),
202  [&L](const LoopCacheCostTy &LCC) { return LCC.first == &L; });
203  return (IT != LoopCosts.end()) ? (*IT).second : -1;
204  }
205 
206  /// Return the estimated ordered loop costs.
207  const ArrayRef<LoopCacheCostTy> getLoopCosts() const { return LoopCosts; }
208 
209 private:
210  /// Calculate the cache footprint of each loop in the nest (when it is
211  /// considered to be in the innermost position).
212  void calculateCacheFootprint();
213 
214  /// Partition store/load instructions in the loop nest into reference groups.
215  /// Two or more memory accesses belong in the same reference group if they
216  /// share the same cache line.
217  bool populateReferenceGroups(ReferenceGroupsTy &RefGroups) const;
218 
219  /// Calculate the cost of the given loop \p L assuming it is the innermost
220  /// loop in nest.
221  CacheCostTy computeLoopCacheCost(const Loop &L,
222  const ReferenceGroupsTy &RefGroups) const;
223 
224  /// Compute the cost of a representative reference in reference group \p RG
225  /// when the given loop \p L is considered as the innermost loop in the nest.
226  /// The computed cost is an estimate for the number of cache lines used by the
227  /// reference group. The representative reference cost is defined as:
228  /// - equal to one if the reference is loop invariant, or
229  /// - equal to '(TripCount * stride) / cache_line_size' if (a) loop \p L's
230  /// induction variable is used only in the reference subscript associated
231  /// with loop \p L, and (b) the reference stride is less than the cache
232  /// line size, or
233  /// - TripCount otherwise
234  CacheCostTy computeRefGroupCacheCost(const ReferenceGroupTy &RG,
235  const Loop &L) const;
236 
237  /// Sort the LoopCosts vector by decreasing cache cost.
238  void sortLoopCosts() {
239  sort(LoopCosts, [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {
240  return A.second > B.second;
241  });
242  }
243 
244 private:
245  /// Loops in the loop nest associated with this object.
247 
248  /// Trip counts for the loops in the loop nest associated with this object.
250 
251  /// Cache costs for the loops in the loop nest associated with this object.
253 
254  /// The max. distance between array elements accessed in a loop so that the
255  /// elements are classified to have temporal reuse.
256  Optional<unsigned> TRT;
257 
258  const LoopInfo &LI;
259  ScalarEvolution &SE;
260  TargetTransformInfo &TTI;
261  AliasAnalysis &AA;
262  DependenceInfo &DI;
263 };
264 
267 
268 /// Printer pass for the \c CacheCost results.
269 class LoopCachePrinterPass : public PassInfoMixin<LoopCachePrinterPass> {
270  raw_ostream &OS;
271 
272 public:
273  explicit LoopCachePrinterPass(raw_ostream &OS) : OS(OS) {}
274 
277 };
278 
279 } // namespace llvm
280 
281 #endif // LLVM_ANALYSIS_LOOPCACHEANALYSIS_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
int64_t CacheCostTy
The main scalar evolution driver.
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:953
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
DependenceInfo - This class is the main dependence-analysis driver.
Hexagon Hardware Loops
LoopCachePrinterPass(raw_ostream &OS)
const SCEV * getFirstSubscript() const
friend raw_ostream & operator<<(raw_ostream &OS, const IndexedReference &R)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:373
This header provides classes for managing per-loop analyses.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
CacheCost represents the estimated cost of a inner loop as the number of cache lines used by the memo...
Printer pass for the CacheCost results.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
Optional< bool > hasSpacialReuse(const IndexedReference &Other, unsigned CLS, AliasAnalysis &AA) const
Return true/false if the current object and the indexed reference Other are/aren&#39;t in the same cache ...
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1193
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
size_t getNumSubscripts() const
const SCEV * getSubscript(unsigned SubNum) const
const ArrayRef< LoopCacheCostTy > getLoopCosts() const
Return the estimated ordered loop costs.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Optional< bool > hasTemporalReuse(const IndexedReference &Other, unsigned MaxDistance, const Loop &L, DependenceInfo &DI, AliasAnalysis &AA) const
Return true if the current object and the indexed reference Other have distance smaller than MaxDista...
Represents a memory reference as a base pointer and a set of indexing operations. ...
const SCEV * getLastSubscript() const
IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI, ScalarEvolution &SE)
Construct an indexed reference given a StoreOrLoadInst instruction.
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
CacheCostTy getLoopCost(const Loop &L) const
Return the estimated cost of loop L if the given loop is part of the loop nest associated with this o...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const
Compute the cost of the reference w.r.t.
const SCEV * getBasePointer() const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
A container for analyses that lazily runs them and caches their results.
This pass exposes codegen information to IR-level passes.