LLVM  15.0.0git
LoopCacheAnalysis.cpp
Go to the documentation of this file.
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 
30 #include "llvm/ADT/Sequence.h"
31 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/Analysis/LoopInfo.h"
39 #include "llvm/Support/Debug.h"
40 
41 using namespace llvm;
42 
43 #define DEBUG_TYPE "loop-cache-cost"
44 
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 temporal
50 // reuse if they access either the same memory location, or a memory location
51 // with distance smaller than a configurable threshold.
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 a
59 /// 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-first
61 /// order.
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  ? LastLoop
78  : nullptr;
79 }
80 
81 static 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 if
107 /// it is not a compile time constant. Return the SCEV expression for the trip
108 /// count.
109 static 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 implementation
128 //
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 
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: " << *this
156  << "\n");
157 }
158 
160  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 line
188  // 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" << OtherLastSubscript
198  << "\nis not constant.\n");
199  return None;
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  else
208  dbgs().indent(2) << "No spacial reuse.\n";
209  });
210 
211  return InSameCacheLine;
212 }
213 
215  unsigned MaxDistance,
216  const Loop &L,
217  DependenceInfo &DI,
218  AAResults &AA) const {
219  assert(IsValid && "Expecting a valid reference");
220 
221  if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
222  LLVM_DEBUG(dbgs().indent(2)
223  << "No temporal reuse: different base pointer\n");
224  return false;
225  }
226 
227  std::unique_ptr<Dependence> D =
228  DI.depends(&StoreOrLoadInst, &Other.StoreOrLoadInst, true);
229 
230  if (D == nullptr) {
231  LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: no dependence\n");
232  return false;
233  }
234 
235  if (D->isLoopIndependent()) {
236  LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
237  return true;
238  }
239 
240  // Check the dependence distance at every loop level. There is temporal reuse
241  // if the distance at the given loop's depth is small (|d| <= MaxDistance) and
242  // it is zero at every other loop level.
243  int LoopDepth = L.getLoopDepth();
244  int Levels = D->getLevels();
245  for (int Level = 1; Level <= Levels; ++Level) {
246  const SCEV *Distance = D->getDistance(Level);
247  const SCEVConstant *SCEVConst = dyn_cast_or_null<SCEVConstant>(Distance);
248 
249  if (SCEVConst == nullptr) {
250  LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: distance unknown\n");
251  return None;
252  }
253 
254  const ConstantInt &CI = *SCEVConst->getValue();
255  if (Level != LoopDepth && !CI.isZero()) {
256  LLVM_DEBUG(dbgs().indent(2)
257  << "No temporal reuse: distance is not zero at depth=" << Level
258  << "\n");
259  return false;
260  } else if (Level == LoopDepth && CI.getSExtValue() > MaxDistance) {
261  LLVM_DEBUG(
262  dbgs().indent(2)
263  << "No temporal reuse: distance is greater than MaxDistance at depth="
264  << Level << "\n");
265  return false;
266  }
267  }
268 
269  LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
270  return true;
271 }
272 
274  unsigned CLS) const {
275  assert(IsValid && "Expecting a valid reference");
276  LLVM_DEBUG({
277  dbgs().indent(2) << "Computing cache cost for:\n";
278  dbgs().indent(4) << *this << "\n";
279  });
280 
281  // If the indexed reference is loop invariant the cost is one.
282  if (isLoopInvariant(L)) {
283  LLVM_DEBUG(dbgs().indent(4) << "Reference is loop invariant: RefCost=1\n");
284  return 1;
285  }
286 
287  const SCEV *TripCount = computeTripCount(L, *Sizes.back(), SE);
288  assert(TripCount && "Expecting valid TripCount");
289  LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n");
290 
291  const SCEV *RefCost = nullptr;
292  if (isConsecutive(L, CLS)) {
293  // If the indexed reference is 'consecutive' the cost is
294  // (TripCount*Stride)/CLS.
295  const SCEV *Coeff = getLastCoefficient();
296  const SCEV *ElemSize = Sizes.back();
297  assert(Coeff->getType() == ElemSize->getType() &&
298  "Expecting the same type");
299  const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize);
300  Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());
301  const SCEV *CacheLineSize = SE.getConstant(WiderType, CLS);
302  if (SE.isKnownNegative(Stride))
303  Stride = SE.getNegativeSCEV(Stride);
304  Stride = SE.getNoopOrAnyExtend(Stride, WiderType);
305  TripCount = SE.getNoopOrAnyExtend(TripCount, WiderType);
306  const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);
307  RefCost = SE.getUDivExpr(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 to
314  // the trip count and the depth of the dimension which the subject loop
315  // subscript is accessing. We try to estimate this by multiplying the cost
316  // by the trip counts of loops corresponding to the inner dimensions. For
317  // example, given the indexed reference 'A[i][j][k]', and assuming the
318  // i-loop is in the innermost position, the cost would be equal to the
319  // 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 && "Cound 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  RefCost = SE.getMulExpr(SE.getNoopOrAnyExtend(RefCost, WiderType),
332  SE.getNoopOrAnyExtend(TripCount, WiderType));
333  }
334 
335  LLVM_DEBUG(dbgs().indent(4)
336  << "Access is not consecutive: RefCost=" << *RefCost << "\n");
337  }
338  assert(RefCost && "Expecting a valid RefCost");
339 
340  // Attempt to fold RefCost into a constant.
341  if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost))
342  return ConstantCost->getValue()->getSExtValue();
343 
344  LLVM_DEBUG(dbgs().indent(4)
345  << "RefCost is not a constant! Setting to RefCost=InvalidCost "
346  "(invalid value).\n");
347 
348  return CacheCost::InvalidCost;
349 }
350 
351 bool IndexedReference::tryDelinearizeFixedSize(
352  const SCEV *AccessFn, SmallVectorImpl<const SCEV *> &Subscripts) {
353  SmallVector<int, 4> ArraySizes;
354  if (!tryDelinearizeFixedSizeImpl(&SE, &StoreOrLoadInst, AccessFn, Subscripts,
355  ArraySizes))
356  return false;
357 
358  // Populate Sizes with scev expressions to be used in calculations later.
359  for (auto Idx : seq<unsigned>(1, Subscripts.size()))
360  Sizes.push_back(
361  SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1]));
362 
363  LLVM_DEBUG({
364  dbgs() << "Delinearized subscripts of fixed-size array\n"
365  << "GEP:" << *getLoadStorePointerOperand(&StoreOrLoadInst)
366  << "\n";
367  });
368  return true;
369 }
370 
371 bool IndexedReference::delinearize(const LoopInfo &LI) {
372  assert(Subscripts.empty() && "Subscripts should be empty");
373  assert(Sizes.empty() && "Sizes should be empty");
374  assert(!IsValid && "Should be called once from the constructor");
375  LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");
376 
377  const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);
378  const BasicBlock *BB = StoreOrLoadInst.getParent();
379 
380  if (Loop *L = LI.getLoopFor(BB)) {
381  const SCEV *AccessFn =
382  SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L);
383 
384  BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));
385  if (BasePointer == nullptr) {
386  LLVM_DEBUG(
387  dbgs().indent(2)
388  << "ERROR: failed to delinearize, can't identify base pointer\n");
389  return false;
390  }
391 
392  bool IsFixedSize = false;
393  // Try to delinearize fixed-size arrays.
394  if (tryDelinearizeFixedSize(AccessFn, Subscripts)) {
395  IsFixedSize = true;
396  // The last element of Sizes is the element size.
397  Sizes.push_back(ElemSize);
398  LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
399  << "', AccessFn: " << *AccessFn << "\n");
400  }
401 
402  AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
403 
404  // Try to delinearize parametric-size arrays.
405  if (!IsFixedSize) {
406  LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
407  << "', AccessFn: " << *AccessFn << "\n");
408  llvm::delinearize(SE, AccessFn, Subscripts, Sizes,
409  SE.getElementSize(&StoreOrLoadInst));
410  }
411 
412  if (Subscripts.empty() || Sizes.empty() ||
413  Subscripts.size() != Sizes.size()) {
414  // Attempt to determine whether we have a single dimensional array access.
415  // before giving up.
416  if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {
417  LLVM_DEBUG(dbgs().indent(2)
418  << "ERROR: failed to delinearize reference\n");
419  Subscripts.clear();
420  Sizes.clear();
421  return false;
422  }
423 
424  // The array may be accessed in reverse, for example:
425  // for (i = N; i > 0; i--)
426  // A[i] = 0;
427  // In this case, reconstruct the access function using the absolute value
428  // of the step recurrence.
429  const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn);
430  const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;
431 
432  if (StepRec && SE.isKnownNegative(StepRec))
433  AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(),
434  SE.getNegativeSCEV(StepRec),
435  AccessFnAR->getLoop(),
436  AccessFnAR->getNoWrapFlags());
437  const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);
438  Subscripts.push_back(Div);
439  Sizes.push_back(ElemSize);
440  }
441 
442  return all_of(Subscripts, [&](const SCEV *Subscript) {
443  return isSimpleAddRecurrence(*Subscript, *L);
444  });
445  }
446 
447  return false;
448 }
449 
450 bool IndexedReference::isLoopInvariant(const Loop &L) const {
451  Value *Addr = getPointerOperand(&StoreOrLoadInst);
452  assert(Addr != nullptr && "Expecting either a load or a store instruction");
453  assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");
454 
455  if (SE.isLoopInvariant(SE.getSCEV(Addr), &L))
456  return true;
457 
458  // The indexed reference is loop invariant if none of the coefficients use
459  // the loop induction variable.
460  bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) {
461  return isCoeffForLoopZeroOrInvariant(*Subscript, L);
462  });
463 
464  return allCoeffForLoopAreZero;
465 }
466 
467 bool IndexedReference::isConsecutive(const Loop &L, unsigned CLS) const {
468  // The indexed reference is 'consecutive' if the only coefficient that uses
469  // the loop induction variable is the last one...
470  const SCEV *LastSubscript = Subscripts.back();
471  for (const SCEV *Subscript : Subscripts) {
472  if (Subscript == LastSubscript)
473  continue;
474  if (!isCoeffForLoopZeroOrInvariant(*Subscript, L))
475  return false;
476  }
477 
478  // ...and the access stride is less than the cache line size.
479  const SCEV *Coeff = getLastCoefficient();
480  const SCEV *ElemSize = Sizes.back();
481  const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize);
482  const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
483 
484  Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;
486 }
487 
488 int IndexedReference::getSubscriptIndex(const Loop &L) const {
489  for (auto Idx : seq<int>(0, getNumSubscripts())) {
490  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(Idx));
491  if (AR && AR->getLoop() == &L) {
492  return Idx;
493  }
494  }
495  return -1;
496 }
497 
498 const SCEV *IndexedReference::getLastCoefficient() const {
499  const SCEV *LastSubscript = getLastSubscript();
500  auto *AR = cast<SCEVAddRecExpr>(LastSubscript);
501  return AR->getStepRecurrence(SE);
502 }
503 
504 bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
505  const Loop &L) const {
506  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript);
507  return (AR != nullptr) ? AR->getLoop() != &L
508  : SE.isLoopInvariant(&Subscript, &L);
509 }
510 
511 bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,
512  const Loop &L) const {
513  if (!isa<SCEVAddRecExpr>(Subscript))
514  return false;
515 
516  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript);
517  assert(AR->getLoop() && "AR should have a loop");
518 
519  if (!AR->isAffine())
520  return false;
521 
522  const SCEV *Start = AR->getStart();
523  const SCEV *Step = AR->getStepRecurrence(SE);
524 
525  if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))
526  return false;
527 
528  return true;
529 }
530 
531 bool IndexedReference::isAliased(const IndexedReference &Other,
532  AAResults &AA) const {
533  const auto &Loc1 = MemoryLocation::get(&StoreOrLoadInst);
534  const auto &Loc2 = MemoryLocation::get(&Other.StoreOrLoadInst);
535  return AA.isMustAlias(Loc1, Loc2);
536 }
537 
538 //===----------------------------------------------------------------------===//
539 // CacheCost implementation
540 //
542  for (const auto &LC : CC.LoopCosts) {
543  const Loop *L = LC.first;
544  OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";
545  }
546  return OS;
547 }
548 
552  : Loops(Loops),
553  TRT((TRT == None) ? Optional<unsigned>(TemporalReuseThreshold) : TRT),
554  LI(LI), SE(SE), TTI(TTI), AA(AA), DI(DI) {
555  assert(!Loops.empty() && "Expecting a non-empty loop vector.");
556 
557  for (const Loop *L : Loops) {
558  unsigned TripCount = SE.getSmallConstantTripCount(L);
559  TripCount = (TripCount == 0) ? DefaultTripCount : TripCount;
560  TripCounts.push_back({L, TripCount});
561  }
562 
563  calculateCacheFootprint();
564 }
565 
566 std::unique_ptr<CacheCost>
569  if (!Root.isOutermost()) {
570  LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");
571  return nullptr;
572  }
573 
574  LoopVectorTy Loops;
576 
577  if (!getInnerMostLoop(Loops)) {
578  LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "
579  "than one innermost loop\n");
580  return nullptr;
581  }
582 
583  return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);
584 }
585 
586 void CacheCost::calculateCacheFootprint() {
587  LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n");
588  ReferenceGroupsTy RefGroups;
589  if (!populateReferenceGroups(RefGroups))
590  return;
591 
592  LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n");
593  for (const Loop *L : Loops) {
595  LoopCosts,
596  [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) &&
597  "Should not add duplicate element");
598  CacheCostTy LoopCost = computeLoopCacheCost(*L, RefGroups);
599  LoopCosts.push_back(std::make_pair(L, LoopCost));
600  }
601 
602  sortLoopCosts();
603  RefGroups.clear();
604 }
605 
606 bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const {
607  assert(RefGroups.empty() && "Reference groups should be empty");
608 
609  unsigned CLS = TTI.getCacheLineSize();
610  Loop *InnerMostLoop = getInnerMostLoop(Loops);
611  assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop");
612 
613  for (BasicBlock *BB : InnerMostLoop->getBlocks()) {
614  for (Instruction &I : *BB) {
615  if (!isa<StoreInst>(I) && !isa<LoadInst>(I))
616  continue;
617 
618  std::unique_ptr<IndexedReference> R(new IndexedReference(I, LI, SE));
619  if (!R->isValid())
620  continue;
621 
622  bool Added = false;
623  for (ReferenceGroupTy &RefGroup : RefGroups) {
624  const IndexedReference &Representative = *RefGroup.front();
625  LLVM_DEBUG({
626  dbgs() << "References:\n";
627  dbgs().indent(2) << *R << "\n";
628  dbgs().indent(2) << Representative << "\n";
629  });
630 
631 
632  // FIXME: Both positive and negative access functions will be placed
633  // into the same reference group, resulting in a bi-directional array
634  // access such as:
635  // for (i = N; i > 0; i--)
636  // A[i] = A[N - i];
637  // having the same cost calculation as a single dimention access pattern
638  // for (i = 0; i < N; i++)
639  // A[i] = A[i];
640  // when in actuality, depending on the array size, the first example
641  // should have a cost closer to 2x the second due to the two cache
642  // access per iteration from opposite ends of the array
643  Optional<bool> HasTemporalReuse =
644  R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);
645  Optional<bool> HasSpacialReuse =
646  R->hasSpacialReuse(Representative, CLS, AA);
647 
648  if ((HasTemporalReuse.hasValue() && *HasTemporalReuse) ||
649  (HasSpacialReuse.hasValue() && *HasSpacialReuse)) {
650  RefGroup.push_back(std::move(R));
651  Added = true;
652  break;
653  }
654  }
655 
656  if (!Added) {
658  RG.push_back(std::move(R));
659  RefGroups.push_back(std::move(RG));
660  }
661  }
662  }
663 
664  if (RefGroups.empty())
665  return false;
666 
667  LLVM_DEBUG({
668  dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";
669  int n = 1;
670  for (const ReferenceGroupTy &RG : RefGroups) {
671  dbgs().indent(2) << "RefGroup " << n << ":\n";
672  for (const auto &IR : RG)
673  dbgs().indent(4) << *IR << "\n";
674  n++;
675  }
676  dbgs() << "\n";
677  });
678 
679  return true;
680 }
681 
683 CacheCost::computeLoopCacheCost(const Loop &L,
684  const ReferenceGroupsTy &RefGroups) const {
685  if (!L.isLoopSimplifyForm())
686  return InvalidCost;
687 
688  LLVM_DEBUG(dbgs() << "Considering loop '" << L.getName()
689  << "' as innermost loop.\n");
690 
691  // Compute the product of the trip counts of each other loop in the nest.
692  CacheCostTy TripCountsProduct = 1;
693  for (const auto &TC : TripCounts) {
694  if (TC.first == &L)
695  continue;
696  TripCountsProduct *= TC.second;
697  }
698 
699  CacheCostTy LoopCost = 0;
700  for (const ReferenceGroupTy &RG : RefGroups) {
701  CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);
702  LoopCost += RefGroupCost * TripCountsProduct;
703  }
704 
705  LLVM_DEBUG(dbgs().indent(2) << "Loop '" << L.getName()
706  << "' has cost=" << LoopCost << "\n");
707 
708  return LoopCost;
709 }
710 
711 CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG,
712  const Loop &L) const {
713  assert(!RG.empty() && "Reference group should have at least one member.");
714 
715  const IndexedReference *Representative = RG.front().get();
716  return Representative->computeRefCost(L, TTI.getCacheLineSize());
717 }
718 
719 //===----------------------------------------------------------------------===//
720 // LoopCachePrinterPass implementation
721 //
724  LPMUpdater &U) {
725  Function *F = L.getHeader()->getParent();
726  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
727 
728  if (auto CC = CacheCost::getCacheCost(L, AR, DI))
729  OS << *CC;
730 
731  return PreservedAnalyses::all();
732 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
TemporalReuseThreshold
static cl::opt< unsigned > TemporalReuseThreshold("temporal-reuse-threshold", cl::init(2), cl::Hidden, cl::desc("Use this to specify the max. distance between array elements " "accessed in a loop so that the elements are classified to have " "temporal reuse"))
isOneDimensionalArray
static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize, const Loop &L, ScalarEvolution &SE)
Definition: LoopCacheAnalysis.cpp:81
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:35
llvm::ScalarEvolution::getNegativeSCEV
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
Definition: ScalarEvolution.cpp:4437
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1631
BreadthFirstIterator.h
llvm::IndexedReference::hasSpacialReuse
Optional< bool > hasSpacialReuse(const IndexedReference &Other, unsigned CLS, AAResults &AA) const
Return true/false if the current object and the indexed reference Other are/aren't in the same cache ...
Definition: LoopCacheAnalysis.cpp:159
llvm::SCEVAddRecExpr::isAffine
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
Definition: ScalarEvolutionExpressions.h:370
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:353
llvm::IndexedReference::getSubscript
const SCEV * getSubscript(unsigned SubNum) const
Definition: LoopCacheAnalysis.h:58
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::ScalarEvolution::getAddRecExpr
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
Definition: ScalarEvolution.cpp:3575
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::ScalarEvolution::getNoopOrAnyExtend
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4622
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
getInnerMostLoop
static Loop * getInnerMostLoop(const LoopVectorTy &Loops)
Retrieve the innermost loop in the given loop nest Loops.
Definition: LoopCacheAnalysis.cpp:62
llvm::Optional< bool >
llvm::ScalarEvolution::getUDivExactExpr
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3521
llvm::ScalarEvolution::getWiderType
Type * getWiderType(Type *Ty1, Type *Ty2) const
Definition: ScalarEvolution.cpp:4320
llvm::SCEVConstant::getValue
ConstantInt * getValue() const
Definition: ScalarEvolutionExpressions.h:69
Sequence.h
llvm::ScalarEvolution::getPointerBase
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
Definition: ScalarEvolution.cpp:4691
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
llvm::Optional::hasValue
constexpr bool hasValue() const
Definition: Optional.h:312
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ScalarEvolution::getMulExpr
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3050
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1617
llvm::ScalarEvolution::getTripCountFromExitCount
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
Definition: ScalarEvolution.cpp:7645
llvm::CacheCost::getCacheCost
static std::unique_ptr< CacheCost > getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI, Optional< unsigned > TRT=None)
Create a CacheCost for the loop nest rooted by Root.
Definition: LoopCacheAnalysis.cpp:567
L2
add sub stmia L5 ldr L2
Definition: README.txt:201
llvm::SPIRV::ImageChannelOrder::RG
@ RG
llvm::AAResults
Definition: AliasAnalysis.h:511
DefaultTripCount
static cl::opt< unsigned > DefaultTripCount("default-trip-count", cl::init(100), cl::Hidden, cl::desc("Use this to specify the default trip count of a loop"))
llvm::ScalarEvolution::getUDivExpr
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
Definition: ScalarEvolution.cpp:3345
llvm::IndexedReference::getNumSubscripts
size_t getNumSubscripts() const
Definition: LoopCacheAnalysis.h:57
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::breadth_first
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition: BreadthFirstIterator.h:158
llvm::LoopCachePrinterPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopCacheAnalysis.cpp:722
llvm::tryDelinearizeFixedSizeImpl
bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Implementation of fixed size array delinearization.
Definition: Delinearization.cpp:524
llvm::LoopBase::getBlocks
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:187
llvm::ScalarEvolution::isKnownPredicate
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
Definition: ScalarEvolution.cpp:10404
llvm::Instruction
Definition: Instruction.h:42
llvm::IndexedReference::computeRefCost
CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const
Compute the cost of the reference w.r.t.
Definition: LoopCacheAnalysis.cpp:273
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::IndexedReference::hasTemporalReuse
Optional< bool > hasTemporalReuse(const IndexedReference &Other, unsigned MaxDistance, const Loop &L, DependenceInfo &DI, AAResults &AA) const
Return true if the current object and the indexed reference Other have distance smaller than MaxDista...
Definition: LoopCacheAnalysis.cpp:214
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:751
llvm::IndexedReference::IndexedReference
IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI, ScalarEvolution &SE)
Construct an indexed reference given a StoreOrLoadInst instruction.
Definition: LoopCacheAnalysis.cpp:147
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:885
llvm::None
const NoneType None
Definition: None.h:24
LoopInfo.h
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4406
llvm::ScalarEvolution::getSmallConstantTripCount
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
Definition: ScalarEvolution.cpp:7676
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:475
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::DependenceInfo
DependenceInfo - This class is the main dependence-analysis driver.
Definition: DependenceAnalysis.h:269
computeTripCount
static const SCEV * computeTripCount(const Loop &L, const SCEV &ElemSize, ScalarEvolution &SE)
Compute the trip count for the given loop L or assume a default value if it is not a compile time con...
Definition: LoopCacheAnalysis.cpp:109
CacheLineSize
static cl::opt< unsigned > CacheLineSize("cache-line-size", cl::init(0), cl::Hidden, cl::desc("Use this to override the target cache line size when " "specified by the user."))
llvm::getPointerOperand
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
Definition: Instructions.h:5331
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:78
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:986
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::IndexedReference
Represents a memory reference as a base pointer and a set of indexing operations.
Definition: LoopCacheAnalysis.h:47
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
llvm::SCEVConstant
This class represents a constant integer value.
Definition: ScalarEvolutionExpressions.h:60
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LoopBase::getLoopDepth
unsigned getLoopDepth() const
Return the nesting level of this loop.
Definition: LoopInfo.h:96
llvm::IndexedReference::getLastSubscript
const SCEV * getLastSubscript() const
Definition: LoopCacheAnalysis.h:66
llvm::SCEVNAryExpr::getNoWrapFlags
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Definition: ScalarEvolutionExpressions.h:213
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:461
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:744
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:194
llvm::LoopBase::isOutermost
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:184
llvm::ScalarEvolution::getElementSize
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
Definition: ScalarEvolution.cpp:12834
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1823
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:55
llvm::PICLevel::Level
Level
Definition: CodeGen.h:33
llvm::ConstantInt::getSExtValue
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition: Constants.h:148
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:13240
llvm::TargetTransformInfo::getCacheLineSize
unsigned getCacheLineSize() const
Definition: TargetTransformInfo.cpp:667
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:354
llvm::delinearize
void delinearize(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array...
Definition: Delinearization.cpp:450
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
Definition: ScalarEvolution.cpp:4523
llvm::LoopStandardAnalysisResults::TTI
TargetTransformInfo & TTI
Definition: LoopAnalysisManager.h:58
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:4292
llvm::is_sorted
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition: STLExtras.h:1697
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
llvm::LoopStandardAnalysisResults::AA
AAResults & AA
Definition: LoopAnalysisManager.h:52
AA
ScalarEvolutionExpressions.h
llvm::CacheCostTy
int64_t CacheCostTy
Definition: LoopCacheAnalysis.h:33
llvm::DependenceInfo::depends
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
Definition: DependenceAnalysis.cpp:3527
SmallVector.h
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:496
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::CacheCost
CacheCost represents the estimated cost of a inner loop as the number of cache lines used by the memo...
Definition: LoopCacheAnalysis.h:187
TargetTransformInfo.h
Delinearization.h
LoopCacheAnalysis.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::SCEV::getType
Type * getType() const
Return the LLVM type of this SCEV expression.
Definition: ScalarEvolution.cpp:392
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::getLoadStorePointerOperand
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
Definition: Instructions.h:5317
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
DependenceAnalysis.h
llvm::cl::desc
Definition: CommandLine.h:405
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::ScalarEvolution::getBackedgeTakenCount
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
Definition: ScalarEvolution.cpp:7901
llvm::CacheCost::InvalidCost
static constexpr CacheCostTy InvalidCost
Definition: LoopCacheAnalysis.h:193
llvm::ScalarEvolution::isKnownNegative
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
Definition: ScalarEvolution.cpp:10321
llvm::ScalarEvolution::getSCEVAtScope
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
Definition: ScalarEvolution.cpp:9237
llvm::CacheCost::CacheCost
CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE, TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI, Optional< unsigned > TRT=None)
Construct a CacheCost object for the loop nest described by Loops.
Definition: LoopCacheAnalysis.cpp:549
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::SCEVAddRecExpr::getStepRecurrence
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
Definition: ScalarEvolutionExpressions.h:360
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236