LLVM  16.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  const SCEV *Stride = nullptr;
293  if (isConsecutive(L, Stride, CLS)) {
294  // If the indexed reference is 'consecutive' the cost is
295  // (TripCount*Stride)/CLS.
296  assert(Stride != nullptr &&
297  "Stride should not be null for consecutive access!");
298  Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());
299  const SCEV *CacheLineSize = SE.getConstant(WiderType, CLS);
300  Stride = SE.getNoopOrAnyExtend(Stride, WiderType);
301  TripCount = SE.getNoopOrAnyExtend(TripCount, WiderType);
302  const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);
303  RefCost = SE.getUDivExpr(Numerator, CacheLineSize);
304 
305  LLVM_DEBUG(dbgs().indent(4)
306  << "Access is consecutive: RefCost=(TripCount*Stride)/CLS="
307  << *RefCost << "\n");
308  } else {
309  // If the indexed reference is not 'consecutive' the cost is proportional to
310  // the trip count and the depth of the dimension which the subject loop
311  // subscript is accessing. We try to estimate this by multiplying the cost
312  // by the trip counts of loops corresponding to the inner dimensions. For
313  // example, given the indexed reference 'A[i][j][k]', and assuming the
314  // i-loop is in the innermost position, the cost would be equal to the
315  // iterations of the i-loop multiplied by iterations of the j-loop.
316  RefCost = TripCount;
317 
318  int Index = getSubscriptIndex(L);
319  assert(Index >= 0 && "Cound not locate a valid Index");
320 
321  for (unsigned I = Index + 1; I < getNumSubscripts() - 1; ++I) {
322  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(I));
323  assert(AR && AR->getLoop() && "Expecting valid loop");
324  const SCEV *TripCount =
325  computeTripCount(*AR->getLoop(), *Sizes.back(), SE);
326  Type *WiderType = SE.getWiderType(RefCost->getType(), TripCount->getType());
327  RefCost = SE.getMulExpr(SE.getNoopOrAnyExtend(RefCost, WiderType),
328  SE.getNoopOrAnyExtend(TripCount, WiderType));
329  }
330 
331  LLVM_DEBUG(dbgs().indent(4)
332  << "Access is not consecutive: RefCost=" << *RefCost << "\n");
333  }
334  assert(RefCost && "Expecting a valid RefCost");
335 
336  // Attempt to fold RefCost into a constant.
337  if (auto ConstantCost = dyn_cast<SCEVConstant>(RefCost))
338  return ConstantCost->getValue()->getSExtValue();
339 
340  LLVM_DEBUG(dbgs().indent(4)
341  << "RefCost is not a constant! Setting to RefCost=InvalidCost "
342  "(invalid value).\n");
343 
344  return CacheCost::InvalidCost;
345 }
346 
347 bool IndexedReference::tryDelinearizeFixedSize(
348  const SCEV *AccessFn, SmallVectorImpl<const SCEV *> &Subscripts) {
349  SmallVector<int, 4> ArraySizes;
350  if (!tryDelinearizeFixedSizeImpl(&SE, &StoreOrLoadInst, AccessFn, Subscripts,
351  ArraySizes))
352  return false;
353 
354  // Populate Sizes with scev expressions to be used in calculations later.
355  for (auto Idx : seq<unsigned>(1, Subscripts.size()))
356  Sizes.push_back(
357  SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1]));
358 
359  LLVM_DEBUG({
360  dbgs() << "Delinearized subscripts of fixed-size array\n"
361  << "GEP:" << *getLoadStorePointerOperand(&StoreOrLoadInst)
362  << "\n";
363  });
364  return true;
365 }
366 
367 bool IndexedReference::delinearize(const LoopInfo &LI) {
368  assert(Subscripts.empty() && "Subscripts should be empty");
369  assert(Sizes.empty() && "Sizes should be empty");
370  assert(!IsValid && "Should be called once from the constructor");
371  LLVM_DEBUG(dbgs() << "Delinearizing: " << StoreOrLoadInst << "\n");
372 
373  const SCEV *ElemSize = SE.getElementSize(&StoreOrLoadInst);
374  const BasicBlock *BB = StoreOrLoadInst.getParent();
375 
376  if (Loop *L = LI.getLoopFor(BB)) {
377  const SCEV *AccessFn =
378  SE.getSCEVAtScope(getPointerOperand(&StoreOrLoadInst), L);
379 
380  BasePointer = dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFn));
381  if (BasePointer == nullptr) {
382  LLVM_DEBUG(
383  dbgs().indent(2)
384  << "ERROR: failed to delinearize, can't identify base pointer\n");
385  return false;
386  }
387 
388  bool IsFixedSize = false;
389  // Try to delinearize fixed-size arrays.
390  if (tryDelinearizeFixedSize(AccessFn, Subscripts)) {
391  IsFixedSize = true;
392  // The last element of Sizes is the element size.
393  Sizes.push_back(ElemSize);
394  LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
395  << "', AccessFn: " << *AccessFn << "\n");
396  }
397 
398  AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
399 
400  // Try to delinearize parametric-size arrays.
401  if (!IsFixedSize) {
402  LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
403  << "', AccessFn: " << *AccessFn << "\n");
404  llvm::delinearize(SE, AccessFn, Subscripts, Sizes,
405  SE.getElementSize(&StoreOrLoadInst));
406  }
407 
408  if (Subscripts.empty() || Sizes.empty() ||
409  Subscripts.size() != Sizes.size()) {
410  // Attempt to determine whether we have a single dimensional array access.
411  // before giving up.
412  if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {
413  LLVM_DEBUG(dbgs().indent(2)
414  << "ERROR: failed to delinearize reference\n");
415  Subscripts.clear();
416  Sizes.clear();
417  return false;
418  }
419 
420  // The array may be accessed in reverse, for example:
421  // for (i = N; i > 0; i--)
422  // A[i] = 0;
423  // In this case, reconstruct the access function using the absolute value
424  // of the step recurrence.
425  const SCEVAddRecExpr *AccessFnAR = dyn_cast<SCEVAddRecExpr>(AccessFn);
426  const SCEV *StepRec = AccessFnAR ? AccessFnAR->getStepRecurrence(SE) : nullptr;
427 
428  if (StepRec && SE.isKnownNegative(StepRec))
429  AccessFn = SE.getAddRecExpr(AccessFnAR->getStart(),
430  SE.getNegativeSCEV(StepRec),
431  AccessFnAR->getLoop(),
432  AccessFnAR->getNoWrapFlags());
433  const SCEV *Div = SE.getUDivExactExpr(AccessFn, ElemSize);
434  Subscripts.push_back(Div);
435  Sizes.push_back(ElemSize);
436  }
437 
438  return all_of(Subscripts, [&](const SCEV *Subscript) {
439  return isSimpleAddRecurrence(*Subscript, *L);
440  });
441  }
442 
443  return false;
444 }
445 
446 bool IndexedReference::isLoopInvariant(const Loop &L) const {
447  Value *Addr = getPointerOperand(&StoreOrLoadInst);
448  assert(Addr != nullptr && "Expecting either a load or a store instruction");
449  assert(SE.isSCEVable(Addr->getType()) && "Addr should be SCEVable");
450 
451  if (SE.isLoopInvariant(SE.getSCEV(Addr), &L))
452  return true;
453 
454  // The indexed reference is loop invariant if none of the coefficients use
455  // the loop induction variable.
456  bool allCoeffForLoopAreZero = all_of(Subscripts, [&](const SCEV *Subscript) {
457  return isCoeffForLoopZeroOrInvariant(*Subscript, L);
458  });
459 
460  return allCoeffForLoopAreZero;
461 }
462 
463 bool IndexedReference::isConsecutive(const Loop &L, const SCEV *&Stride,
464  unsigned CLS) const {
465  // The indexed reference is 'consecutive' if the only coefficient that uses
466  // the loop induction variable is the last one...
467  const SCEV *LastSubscript = Subscripts.back();
468  for (const SCEV *Subscript : Subscripts) {
469  if (Subscript == LastSubscript)
470  continue;
471  if (!isCoeffForLoopZeroOrInvariant(*Subscript, L))
472  return false;
473  }
474 
475  // ...and the access stride is less than the cache line size.
476  const SCEV *Coeff = getLastCoefficient();
477  const SCEV *ElemSize = Sizes.back();
478  Type *WiderType = SE.getWiderType(Coeff->getType(), ElemSize->getType());
479  // FIXME: This assumes that all values are signed integers which may
480  // be incorrect in unusual codes and incorrectly use sext instead of zext.
481  // for (uint32_t i = 0; i < 512; ++i) {
482  // uint8_t trunc = i;
483  // A[trunc] = 42;
484  // }
485  // This consecutively iterates twice over A. If `trunc` is sign-extended,
486  // we would conclude that this may iterate backwards over the array.
487  // However, LoopCacheAnalysis is heuristic anyway and transformations must
488  // not result in wrong optimizations if the heuristic was incorrect.
489  Stride = SE.getMulExpr(SE.getNoopOrSignExtend(Coeff, WiderType),
490  SE.getNoopOrSignExtend(ElemSize, WiderType));
491  const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
492 
493  Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;
495 }
496 
497 int IndexedReference::getSubscriptIndex(const Loop &L) const {
498  for (auto Idx : seq<int>(0, getNumSubscripts())) {
499  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(Idx));
500  if (AR && AR->getLoop() == &L) {
501  return Idx;
502  }
503  }
504  return -1;
505 }
506 
507 const SCEV *IndexedReference::getLastCoefficient() const {
508  const SCEV *LastSubscript = getLastSubscript();
509  auto *AR = cast<SCEVAddRecExpr>(LastSubscript);
510  return AR->getStepRecurrence(SE);
511 }
512 
513 bool IndexedReference::isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
514  const Loop &L) const {
515  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(&Subscript);
516  return (AR != nullptr) ? AR->getLoop() != &L
517  : SE.isLoopInvariant(&Subscript, &L);
518 }
519 
520 bool IndexedReference::isSimpleAddRecurrence(const SCEV &Subscript,
521  const Loop &L) const {
522  if (!isa<SCEVAddRecExpr>(Subscript))
523  return false;
524 
525  const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(&Subscript);
526  assert(AR->getLoop() && "AR should have a loop");
527 
528  if (!AR->isAffine())
529  return false;
530 
531  const SCEV *Start = AR->getStart();
532  const SCEV *Step = AR->getStepRecurrence(SE);
533 
534  if (!SE.isLoopInvariant(Start, &L) || !SE.isLoopInvariant(Step, &L))
535  return false;
536 
537  return true;
538 }
539 
540 bool IndexedReference::isAliased(const IndexedReference &Other,
541  AAResults &AA) const {
542  const auto &Loc1 = MemoryLocation::get(&StoreOrLoadInst);
543  const auto &Loc2 = MemoryLocation::get(&Other.StoreOrLoadInst);
544  return AA.isMustAlias(Loc1, Loc2);
545 }
546 
547 //===----------------------------------------------------------------------===//
548 // CacheCost implementation
549 //
551  for (const auto &LC : CC.LoopCosts) {
552  const Loop *L = LC.first;
553  OS << "Loop '" << L->getName() << "' has cost = " << LC.second << "\n";
554  }
555  return OS;
556 }
557 
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>
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  Optional<bool> HasTemporalReuse =
652  R->hasTemporalReuse(Representative, *TRT, *InnerMostLoop, DI, AA);
653  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:4464
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:1723
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:59
llvm::Function
Definition: Function.h:60
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:3611
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
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:4649
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
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:3557
llvm::ScalarEvolution::getWiderType
Type * getWiderType(Type *Ty1, Type *Ty2) const
Definition: ScalarEvolution.cpp:4356
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:4718
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:265
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:3090
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: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:1709
llvm::ScalarEvolution::getTripCountFromExitCount
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount, bool Extend=true)
Convert from an "exit count" (i.e.
Definition: ScalarEvolution.cpp:7985
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:575
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:3385
llvm::IndexedReference::getNumSubscripts
size_t getNumSubscripts() const
Definition: LoopCacheAnalysis.h:58
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: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:10757
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:53
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:291
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::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:4442
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:8016
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:1412
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:291
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:5375
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:447
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:4637
llvm::SCEVNAryExpr::getNoWrapFlags
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
Definition: ScalarEvolutionExpressions.h:213
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:472
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
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:185
llvm::ScalarEvolution::getElementSize
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
Definition: ScalarEvolution.cpp:13209
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1988
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: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:13637
llvm::TargetTransformInfo::getCacheLineSize
unsigned getCacheLineSize() const
Definition: TargetTransformInfo.cpp:687
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:4550
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
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: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:4328
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:1858
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
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: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: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:403
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:5361
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:413
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:8242
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:10674
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:9621
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:558
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:1251