LLVM  17.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 
159 std::optional<bool>
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 std::nullopt;
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 
214 std::optional<bool>
216  unsigned MaxDistance, const Loop &L,
217  DependenceInfo &DI, AAResults &AA) const {
218  assert(IsValid && "Expecting a valid reference");
219 
220  if (BasePointer != Other.getBasePointer() && !isAliased(Other, AA)) {
221  LLVM_DEBUG(dbgs().indent(2)
222  << "No temporal reuse: different base pointer\n");
223  return false;
224  }
225 
226  std::unique_ptr<Dependence> D =
227  DI.depends(&StoreOrLoadInst, &Other.StoreOrLoadInst, true);
228 
229  if (D == nullptr) {
230  LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: no dependence\n");
231  return false;
232  }
233 
234  if (D->isLoopIndependent()) {
235  LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
236  return true;
237  }
238 
239  // Check the dependence distance at every loop level. There is temporal reuse
240  // if the distance at the given loop's depth is small (|d| <= MaxDistance) and
241  // it is zero at every other loop level.
242  int LoopDepth = L.getLoopDepth();
243  int Levels = D->getLevels();
244  for (int Level = 1; Level <= Levels; ++Level) {
245  const SCEV *Distance = D->getDistance(Level);
246  const SCEVConstant *SCEVConst = dyn_cast_or_null<SCEVConstant>(Distance);
247 
248  if (SCEVConst == nullptr) {
249  LLVM_DEBUG(dbgs().indent(2) << "No temporal reuse: distance unknown\n");
250  return std::nullopt;
251  }
252 
253  const ConstantInt &CI = *SCEVConst->getValue();
254  if (Level != LoopDepth && !CI.isZero()) {
255  LLVM_DEBUG(dbgs().indent(2)
256  << "No temporal reuse: distance is not zero at depth=" << Level
257  << "\n");
258  return false;
259  } else if (Level == LoopDepth && CI.getSExtValue() > MaxDistance) {
260  LLVM_DEBUG(
261  dbgs().indent(2)
262  << "No temporal reuse: distance is greater than MaxDistance at depth="
263  << Level << "\n");
264  return false;
265  }
266  }
267 
268  LLVM_DEBUG(dbgs().indent(2) << "Found temporal reuse\n");
269  return true;
270 }
271 
273  unsigned CLS) const {
274  assert(IsValid && "Expecting a valid reference");
275  LLVM_DEBUG({
276  dbgs().indent(2) << "Computing cache cost for:\n";
277  dbgs().indent(4) << *this << "\n";
278  });
279 
280  // If the indexed reference is loop invariant the cost is one.
281  if (isLoopInvariant(L)) {
282  LLVM_DEBUG(dbgs().indent(4) << "Reference is loop invariant: RefCost=1\n");
283  return 1;
284  }
285 
286  const SCEV *TripCount = computeTripCount(L, *Sizes.back(), SE);
287  assert(TripCount && "Expecting valid TripCount");
288  LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n");
289 
290  const SCEV *RefCost = nullptr;
291  const SCEV *Stride = nullptr;
292  if (isConsecutive(L, Stride, CLS)) {
293  // If the indexed reference is 'consecutive' the cost is
294  // (TripCount*Stride)/CLS.
295  assert(Stride != nullptr &&
296  "Stride should not be null for consecutive access!");
297  Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());
298  const SCEV *CacheLineSize = SE.getConstant(WiderType, CLS);
299  Stride = SE.getNoopOrAnyExtend(Stride, WiderType);
300  TripCount = SE.getNoopOrAnyExtend(TripCount, WiderType);
301  const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);
302  RefCost = SE.getUDivExpr(Numerator, CacheLineSize);
303 
304  LLVM_DEBUG(dbgs().indent(4)
305  << "Access is consecutive: RefCost=(TripCount*Stride)/CLS="
306  << *RefCost << "\n");
307  } else {
308  // If the indexed reference is not 'consecutive' the cost is proportional to
309  // the trip count and the depth of the dimension which the subject loop
310  // subscript is accessing. We try to estimate this by multiplying the cost
311  // by the trip counts of loops corresponding to the inner dimensions. For
312  // example, given the indexed reference 'A[i][j][k]', and assuming the
313  // i-loop is in the innermost position, the cost would be equal to the
314  // iterations of the i-loop multiplied by iterations of the j-loop.
315  RefCost = TripCount;
316 
317  int Index = getSubscriptIndex(L);
318  assert(Index >= 0 && "Cound not locate a valid Index");
319 
320  for (unsigned I = Index + 1; I < getNumSubscripts() - 1; ++I) {
321  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(I));
322  assert(AR && AR->getLoop() && "Expecting valid loop");
323  const SCEV *TripCount =
324  computeTripCount(*AR->getLoop(), *Sizes.back(), SE);
325  Type *WiderType = SE.getWiderType(RefCost->getType(), TripCount->getType());
326  RefCost = SE.getMulExpr(SE.getNoopOrAnyExtend(RefCost, WiderType),
327  SE.getNoopOrAnyExtend(TripCount, WiderType));
328  }
329 
330  LLVM_DEBUG(dbgs().indent(4)
331  << "Access is not consecutive: RefCost=" << *RefCost << "\n");
332  }
333  assert(RefCost && "Expecting a valid RefCost");
334 
335  // Attempt to fold RefCost into a constant.
336  if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost))
337  return ConstantCost->getValue()->getSExtValue();
338 
339  LLVM_DEBUG(dbgs().indent(4)
340  << "RefCost is not a constant! Setting to RefCost=InvalidCost "
341  "(invalid value).\n");
342 
343  return CacheCost::InvalidCost;
344 }
345 
346 bool IndexedReference::tryDelinearizeFixedSize(
347  const SCEV *AccessFn, SmallVectorImpl<const SCEV *> &Subscripts) {
348  SmallVector<int, 4> ArraySizes;
349  if (!tryDelinearizeFixedSizeImpl(&SE, &StoreOrLoadInst, AccessFn, Subscripts,
350  ArraySizes))
351  return false;
352 
353  // Populate Sizes with scev expressions to be used in calculations later.
354  for (auto Idx : seq<unsigned>(1, Subscripts.size()))
355  Sizes.push_back(
356  SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1]));
357 
358  LLVM_DEBUG({
359  dbgs() << "Delinearized subscripts of fixed-size array\n"
360  << "GEP:" << *getLoadStorePointerOperand(&StoreOrLoadInst)
361  << "\n";
362  });
363  return true;
364 }
365 
366 bool IndexedReference::delinearize(const LoopInfo &LI) {
367  assert(Subscripts.empty() && "Subscripts should be empty");
368  assert(Sizes.empty() && "Sizes should be empty");
369  assert(!IsValid && "Should be called once from the constructor");
370  LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");
371 
372  const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);
373  const BasicBlock *BB = StoreOrLoadInst.getParent();
374 
375  if (Loop *L = LI.getLoopFor(BB)) {
376  const SCEV *AccessFn =
377  SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L);
378 
379  BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));
380  if (BasePointer == nullptr) {
381  LLVM_DEBUG(
382  dbgs().indent(2)
383  << "ERROR: failed to delinearize, can't identify base pointer\n");
384  return false;
385  }
386 
387  bool IsFixedSize = false;
388  // Try to delinearize fixed-size arrays.
389  if (tryDelinearizeFixedSize(AccessFn, Subscripts)) {
390  IsFixedSize = true;
391  // The last element of Sizes is the element size.
392  Sizes.push_back(ElemSize);
393  LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
394  << "', AccessFn: " << *AccessFn << "\n");
395  }
396 
397  AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
398 
399  // Try to delinearize parametric-size arrays.
400  if (!IsFixedSize) {
401  LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
402  << "', AccessFn: " << *AccessFn << "\n");
403  llvm::delinearize(SE, AccessFn, Subscripts, Sizes,
404  SE.getElementSize(&StoreOrLoadInst));
405  }
406 
407  if (Subscripts.empty() || Sizes.empty() ||
408  Subscripts.size() != Sizes.size()) {
409  // Attempt to determine whether we have a single dimensional array access.
410  // before giving up.
411  if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {
412  LLVM_DEBUG(dbgs().indent(2)
413  << "ERROR: failed to delinearize reference\n");
414  Subscripts.clear();
415  Sizes.clear();
416  return false;
417  }
418 
419  // The array may be accessed in reverse, for example:
420  // for (i = N; i > 0; i--)
421  // A[i] = 0;
422  // In this case, reconstruct the access function using the absolute value
423  // of the step recurrence.
424  const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn);
425  const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;
426 
427  if (StepRec && SE.isKnownNegative(StepRec))
428  AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(),
429  SE.getNegativeSCEV(StepRec),
430  AccessFnAR->getLoop(),
431  AccessFnAR->getNoWrapFlags());
432  const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);
433  Subscripts.push_back(Div);
434  Sizes.push_back(ElemSize);
435  }
436 
437  return all_of(Subscripts, [&](const SCEV *Subscript) {
438  return isSimpleAddRecurrence(*Subscript, *L);
439  });
440  }
441 
442  return false;
443 }
444 
445 bool IndexedReference::isLoopInvariant(const Loop &L) const {
446  Value *Addr = getPointerOperand(&StoreOrLoadInst);
447  assert(Addr != nullptr && "Expecting either a load or a store instruction");
448  assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");
449 
450  if (SE.isLoopInvariant(SE.getSCEV(Addr), &L))
451  return true;
452 
453  // The indexed reference is loop invariant if none of the coefficients use
454  // the loop induction variable.
455  bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) {
456  return isCoeffForLoopZeroOrInvariant(*Subscript, L);
457  });
458 
459  return allCoeffForLoopAreZero;
460 }
461 
462 bool IndexedReference::isConsecutive(const Loop &L, const SCEV *&Stride,
463  unsigned CLS) const {
464  // The indexed reference is 'consecutive' if the only coefficient that uses
465  // the loop induction variable is the last one...
466  const SCEV *LastSubscript = Subscripts.back();
467  for (const SCEV *Subscript : Subscripts) {
468  if (Subscript == LastSubscript)
469  continue;
470  if (!isCoeffForLoopZeroOrInvariant(*Subscript, L))
471  return false;
472  }
473 
474  // ...and the access stride is less than the cache line size.
475  const SCEV *Coeff = getLastCoefficient();
476  const SCEV *ElemSize = Sizes.back();
477  Type *WiderType = SE.getWiderType(Coeff->getType(), ElemSize->getType());
478  // FIXME: This assumes that all values are signed integers which may
479  // be incorrect in unusual codes and incorrectly use sext instead of zext.
480  // for (uint32_t i = 0; i < 512; ++i) {
481  // uint8_t trunc = i;
482  // A[trunc] = 42;
483  // }
484  // This consecutively iterates twice over A. If `trunc` is sign-extended,
485  // we would conclude that this may iterate backwards over the array.
486  // However, LoopCacheAnalysis is heuristic anyway and transformations must
487  // not result in wrong optimizations if the heuristic was incorrect.
488  Stride = SE.getMulExpr(SE.getNoopOrSignExtend(Coeff, WiderType),
489  SE.getNoopOrSignExtend(ElemSize, WiderType));
490  const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
491 
492  Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;
494 }
495 
496 int IndexedReference::getSubscriptIndex(const Loop &L) const {
497  for (auto Idx : seq<int>(0, getNumSubscripts())) {
498  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(Idx));
499  if (AR && AR->getLoop() == &L) {
500  return Idx;
501  }
502  }
503  return -1;
504 }
505 
506 const SCEV *IndexedReference::getLastCoefficient() const {
507  const SCEV *LastSubscript = getLastSubscript();
508  auto *AR = cast<SCEVAddRecExpr>(LastSubscript);
509  return AR->getStepRecurrence(SE);
510 }
511 
512 bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
513  const Loop &L) const {
514  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript);
515  return (AR != nullptr) ? AR->getLoop() != &L
516  : SE.isLoopInvariant(&Subscript, &L);
517 }
518 
519 bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,
520  const Loop &L) const {
521  if (!isa<SCEVAddRecExpr>(Subscript))
522  return false;
523 
524  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript);
525  assert(AR->getLoop() && "AR should have a loop");
526 
527  if (!AR->isAffine())
528  return false;
529 
530  const SCEV *Start = AR->getStart();
531  const SCEV *Step = AR->getStepRecurrence(SE);
532 
533  if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))
534  return false;
535 
536  return true;
537 }
538 
539 bool IndexedReference::isAliased(const IndexedReference &Other,
540  AAResults &AA) const {
541  const auto &Loc1 = MemoryLocation::get(&StoreOrLoadInst);
542  const auto &Loc2 = MemoryLocation::get(&Other.StoreOrLoadInst);
543  return AA.isMustAlias(Loc1, Loc2);
544 }
545 
546 //===----------------------------------------------------------------------===//
547 // CacheCost implementation
548 //
550  for (const auto &LC : CC.LoopCosts) {
551  const Loop *L = LC.first;
552  OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";
553  }
554  return OS;
555 }
556 
559  AAResults &AA, DependenceInfo &DI,
560  std::optional<unsigned> TRT)
561  : Loops(Loops), TRT(TRT.value_or(TemporalReuseThreshold)), LI(LI), SE(SE),
562  TTI(TTI), AA(AA), DI(DI) {
563  assert(!Loops.empty() && "Expecting a non-empty loop vector.");
564 
565  for (const Loop *L : Loops) {
566  unsigned TripCount = SE.getSmallConstantTripCount(L);
567  TripCount = (TripCount == 0) ? DefaultTripCount : TripCount;
568  TripCounts.push_back({L, TripCount});
569  }
570 
571  calculateCacheFootprint();
572 }
573 
574 std::unique_ptr<CacheCost>
576  DependenceInfo &DI, std::optional<unsigned> TRT) {
577  if (!Root.isOutermost()) {
578  LLVM_DEBUG(dbgs() << "Expecting the outermost loop in a loop nest\n");
579  return nullptr;
580  }
581 
582  LoopVectorTy Loops;
584 
585  if (!getInnerMostLoop(Loops)) {
586  LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "
587  "than one innermost loop\n");
588  return nullptr;
589  }
590 
591  return std::make_unique<CacheCost>(Loops, AR.LI, AR.SE, AR.TTI, AR.AA, DI, TRT);
592 }
593 
594 void CacheCost::calculateCacheFootprint() {
595  LLVM_DEBUG(dbgs() << "POPULATING REFERENCE GROUPS\n");
596  ReferenceGroupsTy RefGroups;
597  if (!populateReferenceGroups(RefGroups))
598  return;
599 
600  LLVM_DEBUG(dbgs() << "COMPUTING LOOP CACHE COSTS\n");
601  for (const Loop *L : Loops) {
603  LoopCosts,
604  [L](const LoopCacheCostTy &LCC) { return LCC.first == L; }) &&
605  "Should not add duplicate element");
606  CacheCostTy LoopCost = computeLoopCacheCost(*L, RefGroups);
607  LoopCosts.push_back(std::make_pair(L, LoopCost));
608  }
609 
610  sortLoopCosts();
611  RefGroups.clear();
612 }
613 
614 bool CacheCost::populateReferenceGroups(ReferenceGroupsTy &RefGroups) const {
615  assert(RefGroups.empty() && "Reference groups should be empty");
616 
617  unsigned CLS = TTI.getCacheLineSize();
618  Loop *InnerMostLoop = getInnerMostLoop(Loops);
619  assert(InnerMostLoop != nullptr && "Expecting a valid innermost loop");
620 
621  for (BasicBlock *BB : InnerMostLoop->getBlocks()) {
622  for (Instruction &I : *BB) {
623  if (!isa<StoreInst>(I) && !isa<LoadInst>(I))
624  continue;
625 
626  std::unique_ptr<IndexedReference> R(new IndexedReference(I, LI, SE));
627  if (!R->isValid())
628  continue;
629 
630  bool Added = false;
631  for (ReferenceGroupTy &RefGroup : RefGroups) {
632  const IndexedReference &Representative = *RefGroup.front();
633  LLVM_DEBUG({
634  dbgs() << "References:\n";
635  dbgs().indent(2) << *R << "\n";
636  dbgs().indent(2) << Representative << "\n";
637  });
638 
639 
640  // FIXME: Both positive and negative access functions will be placed
641  // into the same reference group, resulting in a bi-directional array
642  // access such as:
643  // for (i = N; i > 0; i--)
644  // A[i] = A[N - i];
645  // having the same cost calculation as a single dimention access pattern
646  // for (i = 0; i < N; i++)
647  // A[i] = A[i];
648  // when in actuality, depending on the array size, the first example
649  // should have a cost closer to 2x the second due to the two cache
650  // access per iteration from opposite ends of the array
651  std::optional<bool> HasTemporalReuse =
652  R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);
653  std::optional<bool> HasSpacialReuse =
654  R->hasSpacialReuse(Representative, CLS, AA);
655 
656  if ((HasTemporalReuse && *HasTemporalReuse) ||
657  (HasSpacialReuse && *HasSpacialReuse)) {
658  RefGroup.push_back(std::move(R));
659  Added = true;
660  break;
661  }
662  }
663 
664  if (!Added) {
665  ReferenceGroupTy RG;
666  RG.push_back(std::move(R));
667  RefGroups.push_back(std::move(RG));
668  }
669  }
670  }
671 
672  if (RefGroups.empty())
673  return false;
674 
675  LLVM_DEBUG({
676  dbgs() << "\nIDENTIFIED REFERENCE GROUPS:\n";
677  int n = 1;
678  for (const ReferenceGroupTy &RG : RefGroups) {
679  dbgs().indent(2) << "RefGroup " << n << ":\n";
680  for (const auto &IR : RG)
681  dbgs().indent(4) << *IR << "\n";
682  n++;
683  }
684  dbgs() << "\n";
685  });
686 
687  return true;
688 }
689 
691 CacheCost::computeLoopCacheCost(const Loop &L,
692  const ReferenceGroupsTy &RefGroups) const {
693  if (!L.isLoopSimplifyForm())
694  return InvalidCost;
695 
696  LLVM_DEBUG(dbgs() << "Considering loop '" << L.getName()
697  << "' as innermost loop.\n");
698 
699  // Compute the product of the trip counts of each other loop in the nest.
700  CacheCostTy TripCountsProduct = 1;
701  for (const auto &TC : TripCounts) {
702  if (TC.first == &L)
703  continue;
704  TripCountsProduct *= TC.second;
705  }
706 
707  CacheCostTy LoopCost = 0;
708  for (const ReferenceGroupTy &RG : RefGroups) {
709  CacheCostTy RefGroupCost = computeRefGroupCacheCost(RG, L);
710  LoopCost += RefGroupCost * TripCountsProduct;
711  }
712 
713  LLVM_DEBUG(dbgs().indent(2) << "Loop '" << L.getName()
714  << "' has cost=" << LoopCost << "\n");
715 
716  return LoopCost;
717 }
718 
719 CacheCostTy CacheCost::computeRefGroupCacheCost(const ReferenceGroupTy &RG,
720  const Loop &L) const {
721  assert(!RG.empty() && "Reference group should have at least one member.");
722 
723  const IndexedReference *Representative = RG.front().get();
724  return Representative->computeRefCost(L, TTI.getCacheLineSize());
725 }
726 
727 //===----------------------------------------------------------------------===//
728 // LoopCachePrinterPass implementation
729 //
732  LPMUpdater &U) {
733  Function *F = L.getHeader()->getParent();
734  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
735 
736  if (auto CC = CacheCost::getCacheCost(L, AR, DI))
737  OS << *CC;
738 
739  return PreservedAnalyses::all();
740 }
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:36
llvm::ScalarEvolution::getNegativeSCEV
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
Definition: ScalarEvolution.cpp:4556
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1749
BreadthFirstIterator.h
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:358
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
llvm::SCEVAddRecExpr::getStart
const SCEV * getStart() const
Definition: ScalarEvolutionExpressions.h:341
llvm::IndexedReference::getSubscript
const SCEV * getSubscript(unsigned SubNum) const
Definition: LoopCacheAnalysis.h:59
llvm::Function
Definition: Function.h:59
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:374
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
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:3653
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:172
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:452
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:4741
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:138
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::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:3599
llvm::ScalarEvolution::getWiderType
Type * getWiderType(Type *Ty1, Type *Ty2) const
Definition: ScalarEvolution.cpp:4448
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:4810
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:275
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
AliasAnalysis.h
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:3132
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
llvm::LoopBase::getParentLoop
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:114
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:1735
llvm::ScalarEvolution::getTripCountFromExitCount
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
Definition: ScalarEvolution.cpp:8074
L2
add sub stmia L5 ldr L2
Definition: README.txt:201
llvm::AAResults
Definition: AliasAnalysis.h:294
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:3427
llvm::IndexedReference::getNumSubscripts
size_t getNumSubscripts() const
Definition: LoopCacheAnalysis.h:58
llvm::dwarf::Index
Index
Definition: Dwarf.h:550
llvm::breadth_first
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition: BreadthFirstIterator.h:157
llvm::LoopCachePrinterPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: LoopCacheAnalysis.cpp:730
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:188
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:10904
llvm::Instruction
Definition: Instruction.h:41
llvm::IndexedReference::computeRefCost
CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const
Compute the cost of the reference w.r.t.
Definition: LoopCacheAnalysis.cpp:272
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:746
llvm::IndexedReference::IndexedReference
IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI, ScalarEvolution &SE)
Construct an indexed reference given a StoreOrLoadInst instruction.
Definition: LoopCacheAnalysis.cpp:147
llvm::IndexedReference::hasSpacialReuse
std::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:160
llvm::Loop::getName
StringRef getName() const
Definition: LoopInfo.h:891
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:4534
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:8105
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:479
llvm::cl::opt
Definition: CommandLine.h:1410
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:293
llvm::CacheCost::getCacheCost
static std::unique_ptr< CacheCost > getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI, std::optional< unsigned > TRT=std::nullopt)
Create a CacheCost for the loop nest rooted by Root.
Definition: LoopCacheAnalysis.cpp:575
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
llvm::CacheCost::CacheCost
CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE, TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI, std::optional< unsigned > TRT=std::nullopt)
Construct a CacheCost object for the loop nest described by Loops.
Definition: LoopCacheAnalysis.cpp:557
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:5377
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:79
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:992
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:48
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
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:97
llvm::IndexedReference::getLastSubscript
const SCEV * getLastSubscript() const
Definition: LoopCacheAnalysis.h:67
llvm::ScalarEvolution::getNoopOrSignExtend
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
Definition: ScalarEvolution.cpp:4729
llvm::SCEVNAryExpr::getNoWrapFlags
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Definition: ScalarEvolutionExpressions.h:205
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:497
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
llvm::ConstantInt::isZero
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
llvm::LoopBase::isOutermost
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:185
llvm::ScalarEvolution::getElementSize
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
Definition: ScalarEvolution.cpp:13372
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:55
CC
auto CC
Definition: RISCVRedundantCopyElimination.cpp:79
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:147
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:13775
llvm::TargetTransformInfo::getCacheLineSize
unsigned getCacheLineSize() const
Definition: TargetTransformInfo.cpp:693
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:342
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:4642
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:330
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
llvm::ScalarEvolution::isSCEVable
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Definition: ScalarEvolution.cpp:4420
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:1884
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:56
llvm::LoopStandardAnalysisResults::AA
AAResults & AA
Definition: LoopAnalysisManager.h:52
ScalarEvolutionExpressions.h
llvm::CacheCostTy
int64_t CacheCostTy
Definition: LoopCacheAnalysis.h:34
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:3590
Other
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1260
SmallVector.h
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:494
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:90
llvm::CacheCost
CacheCost represents the estimated cost of a inner loop as the number of cache lines used by the memo...
Definition: LoopCacheAnalysis.h:189
TargetTransformInfo.h
Delinearization.h
llvm::AAResults::isMustAlias
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
Definition: AliasAnalysis.h:366
llvm::logicalview::LVComparePass::Added
@ Added
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:401
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:5363
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:411
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:8331
llvm::CacheCost::InvalidCost
static constexpr CacheCostTy InvalidCost
Definition: LoopCacheAnalysis.h:195
llvm::ScalarEvolution::isKnownNegative
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
Definition: ScalarEvolution.cpp:10821
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:9735
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:348
llvm::IndexedReference::hasTemporalReuse
std::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:215