Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- llvm/Analysis/LoopCacheAnalysis.h ------------------------*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. ///
  9. /// \file
  10. /// This file defines the interface for the loop cache analysis.
  11. ///
  12. //===----------------------------------------------------------------------===//
  13.  
  14. #ifndef LLVM_ANALYSIS_LOOPCACHEANALYSIS_H
  15. #define LLVM_ANALYSIS_LOOPCACHEANALYSIS_H
  16.  
  17. #include "llvm/Analysis/LoopAnalysisManager.h"
  18. #include "llvm/IR/PassManager.h"
  19. #include <optional>
  20.  
  21. namespace llvm {
  22.  
  23. class AAResults;
  24. class DependenceInfo;
  25. class Instruction;
  26. class LPMUpdater;
  27. class raw_ostream;
  28. class LoopInfo;
  29. class Loop;
  30. class ScalarEvolution;
  31. class SCEV;
  32. class TargetTransformInfo;
  33.  
  34. using CacheCostTy = int64_t;
  35. using LoopVectorTy = SmallVector<Loop *, 8>;
  36.  
  37. /// Represents a memory reference as a base pointer and a set of indexing
  38. /// operations. For example given the array reference A[i][2j+1][3k+2] in a
  39. /// 3-dim loop nest:
  40. ///   for(i=0;i<n;++i)
  41. ///     for(j=0;j<m;++j)
  42. ///       for(k=0;k<o;++k)
  43. ///         ... A[i][2j+1][3k+2] ...
  44. /// We expect:
  45. ///   BasePointer -> A
  46. ///   Subscripts -> [{0,+,1}<%for.i>][{1,+,2}<%for.j>][{2,+,3}<%for.k>]
  47. ///   Sizes -> [m][o][4]
  48. class IndexedReference {
  49.   friend raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R);
  50.  
  51. public:
  52.   /// Construct an indexed reference given a \p StoreOrLoadInst instruction.
  53.   IndexedReference(Instruction &StoreOrLoadInst, const LoopInfo &LI,
  54.                    ScalarEvolution &SE);
  55.  
  56.   bool isValid() const { return IsValid; }
  57.   const SCEV *getBasePointer() const { return BasePointer; }
  58.   size_t getNumSubscripts() const { return Subscripts.size(); }
  59.   const SCEV *getSubscript(unsigned SubNum) const {
  60.     assert(SubNum < getNumSubscripts() && "Invalid subscript number");
  61.     return Subscripts[SubNum];
  62.   }
  63.   const SCEV *getFirstSubscript() const {
  64.     assert(!Subscripts.empty() && "Expecting non-empty container");
  65.     return Subscripts.front();
  66.   }
  67.   const SCEV *getLastSubscript() const {
  68.     assert(!Subscripts.empty() && "Expecting non-empty container");
  69.     return Subscripts.back();
  70.   }
  71.  
  72.   /// Return true/false if the current object and the indexed reference \p Other
  73.   /// are/aren't in the same cache line of size \p CLS. Two references are in
  74.   /// the same chace line iff the distance between them in the innermost
  75.   /// dimension is less than the cache line size. Return std::nullopt if unsure.
  76.   std::optional<bool> hasSpacialReuse(const IndexedReference &Other,
  77.                                       unsigned CLS, AAResults &AA) const;
  78.  
  79.   /// Return true if the current object and the indexed reference \p Other
  80.   /// have distance smaller than \p MaxDistance in the dimension associated with
  81.   /// the given loop \p L. Return false if the distance is not smaller than \p
  82.   /// MaxDistance and std::nullopt if unsure.
  83.   std::optional<bool> hasTemporalReuse(const IndexedReference &Other,
  84.                                        unsigned MaxDistance, const Loop &L,
  85.                                        DependenceInfo &DI, AAResults &AA) const;
  86.  
  87.   /// Compute the cost of the reference w.r.t. the given loop \p L when it is
  88.   /// considered in the innermost position in the loop nest.
  89.   /// The cost is defined as:
  90.   ///   - equal to one if the reference is loop invariant, or
  91.   ///   - equal to '(TripCount * stride) / cache_line_size' if:
  92.   ///     + the reference stride is less than the cache line size, and
  93.   ///     + the coefficient of this loop's index variable used in all other
  94.   ///       subscripts is zero
  95.   ///   - or otherwise equal to 'TripCount'.
  96.   CacheCostTy computeRefCost(const Loop &L, unsigned CLS) const;
  97.  
  98. private:
  99.   /// Attempt to delinearize the indexed reference.
  100.   bool delinearize(const LoopInfo &LI);
  101.  
  102.   /// Attempt to delinearize \p AccessFn for fixed-size arrays.
  103.   bool tryDelinearizeFixedSize(const SCEV *AccessFn,
  104.                                SmallVectorImpl<const SCEV *> &Subscripts);
  105.  
  106.   /// Return true if the index reference is invariant with respect to loop \p L.
  107.   bool isLoopInvariant(const Loop &L) const;
  108.  
  109.   /// Return true if the indexed reference is 'consecutive' in loop \p L.
  110.   /// An indexed reference is 'consecutive' if the only coefficient that uses
  111.   /// the loop induction variable is the rightmost one, and the access stride is
  112.   /// smaller than the cache line size \p CLS. Provide a valid \p Stride value
  113.   /// if the indexed reference is 'consecutive'.
  114.   bool isConsecutive(const Loop &L, const SCEV *&Stride, unsigned CLS) const;
  115.  
  116.   /// Retrieve the index of the subscript corresponding to the given loop \p
  117.   /// L. Return a zero-based positive index if the subscript index is
  118.   /// succesfully located and a negative value otherwise. For example given the
  119.   /// indexed reference 'A[i][2j+1][3k+2]', the call
  120.   /// 'getSubscriptIndex(loop-k)' would return value 2.
  121.   int getSubscriptIndex(const Loop &L) const;
  122.  
  123.   /// Return the coefficient used in the rightmost dimension.
  124.   const SCEV *getLastCoefficient() const;
  125.  
  126.   /// Return true if the coefficient corresponding to induction variable of
  127.   /// loop \p L in the given \p Subscript is zero or is loop invariant in \p L.
  128.   bool isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
  129.                                      const Loop &L) const;
  130.  
  131.   /// Verify that the given \p Subscript is 'well formed' (must be a simple add
  132.   /// recurrence).
  133.   bool isSimpleAddRecurrence(const SCEV &Subscript, const Loop &L) const;
  134.  
  135.   /// Return true if the given reference \p Other is definetely aliased with
  136.   /// the indexed reference represented by this class.
  137.   bool isAliased(const IndexedReference &Other, AAResults &AA) const;
  138.  
  139. private:
  140.   /// True if the reference can be delinearized, false otherwise.
  141.   bool IsValid = false;
  142.  
  143.   /// Represent the memory reference instruction.
  144.   Instruction &StoreOrLoadInst;
  145.  
  146.   /// The base pointer of the memory reference.
  147.   const SCEV *BasePointer = nullptr;
  148.  
  149.   /// The subscript (indexes) of the memory reference.
  150.   SmallVector<const SCEV *, 3> Subscripts;
  151.  
  152.   /// The dimensions of the memory reference.
  153.   SmallVector<const SCEV *, 3> Sizes;
  154.  
  155.   ScalarEvolution &SE;
  156. };
  157.  
  158. /// A reference group represents a set of memory references that exhibit
  159. /// temporal or spacial reuse. Two references belong to the same
  160. /// reference group with respect to a inner loop L iff:
  161. /// 1. they have a loop independent dependency, or
  162. /// 2. they have a loop carried dependence with a small dependence distance
  163. ///    (e.g. less than 2) carried by the inner loop, or
  164. /// 3. they refer to the same array, and the subscript in their innermost
  165. ///    dimension is less than or equal to 'd' (where 'd' is less than the cache
  166. ///    line size)
  167. ///
  168. /// Intuitively a reference group represents memory references that access
  169. /// the same cache line. Conditions 1,2 above account for temporal reuse, while
  170. /// contition 3 accounts for spacial reuse.
  171. using ReferenceGroupTy = SmallVector<std::unique_ptr<IndexedReference>, 8>;
  172. using ReferenceGroupsTy = SmallVector<ReferenceGroupTy, 8>;
  173.  
  174. /// \c CacheCost represents the estimated cost of a inner loop as the number of
  175. /// cache lines used by the memory references it contains.
  176. /// The 'cache cost' of a loop 'L' in a loop nest 'LN' is computed as the sum of
  177. /// the cache costs of all of its reference groups when the loop is considered
  178. /// to be in the innermost position in the nest.
  179. /// A reference group represents memory references that fall into the same cache
  180. /// line. Each reference group is analysed with respect to the innermost loop in
  181. /// a loop nest. The cost of a reference is defined as follow:
  182. ///  - one if it is loop invariant w.r.t the innermost loop,
  183. ///  - equal to the loop trip count divided by the cache line times the
  184. ///    reference stride if the reference stride is less than the cache line
  185. ///    size (CLS), and the coefficient of this loop's index variable used in all
  186. ///    other subscripts is zero (e.g. RefCost = TripCount/(CLS/RefStride))
  187. ///  - equal to the innermost loop trip count if the reference stride is greater
  188. ///    or equal to the cache line size CLS.
  189. class CacheCost {
  190.   friend raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC);
  191.   using LoopTripCountTy = std::pair<const Loop *, unsigned>;
  192.   using LoopCacheCostTy = std::pair<const Loop *, CacheCostTy>;
  193.  
  194. public:
  195.   static CacheCostTy constexpr InvalidCost = -1;
  196.  
  197.   /// Construct a CacheCost object for the loop nest described by \p Loops.
  198.   /// The optional parameter \p TRT can be used to specify the max. distance
  199.   /// between array elements accessed in a loop so that the elements are
  200.   /// classified to have temporal reuse.
  201.   CacheCost(const LoopVectorTy &Loops, const LoopInfo &LI, ScalarEvolution &SE,
  202.             TargetTransformInfo &TTI, AAResults &AA, DependenceInfo &DI,
  203.             std::optional<unsigned> TRT = std::nullopt);
  204.  
  205.   /// Create a CacheCost for the loop nest rooted by \p Root.
  206.   /// The optional parameter \p TRT can be used to specify the max. distance
  207.   /// between array elements accessed in a loop so that the elements are
  208.   /// classified to have temporal reuse.
  209.   static std::unique_ptr<CacheCost>
  210.   getCacheCost(Loop &Root, LoopStandardAnalysisResults &AR, DependenceInfo &DI,
  211.                std::optional<unsigned> TRT = std::nullopt);
  212.  
  213.   /// Return the estimated cost of loop \p L if the given loop is part of the
  214.   /// loop nest associated with this object. Return -1 otherwise.
  215.   CacheCostTy getLoopCost(const Loop &L) const {
  216.     auto IT = llvm::find_if(LoopCosts, [&L](const LoopCacheCostTy &LCC) {
  217.       return LCC.first == &L;
  218.     });
  219.     return (IT != LoopCosts.end()) ? (*IT).second : -1;
  220.   }
  221.  
  222.   /// Return the estimated ordered loop costs.
  223.   ArrayRef<LoopCacheCostTy> getLoopCosts() const { return LoopCosts; }
  224.  
  225. private:
  226.   /// Calculate the cache footprint of each loop in the nest (when it is
  227.   /// considered to be in the innermost position).
  228.   void calculateCacheFootprint();
  229.  
  230.   /// Partition store/load instructions in the loop nest into reference groups.
  231.   /// Two or more memory accesses belong in the same reference group if they
  232.   /// share the same cache line.
  233.   bool populateReferenceGroups(ReferenceGroupsTy &RefGroups) const;
  234.  
  235.   /// Calculate the cost of the given loop \p L assuming it is the innermost
  236.   /// loop in nest.
  237.   CacheCostTy computeLoopCacheCost(const Loop &L,
  238.                                    const ReferenceGroupsTy &RefGroups) const;
  239.  
  240.   /// Compute the cost of a representative reference in reference group \p RG
  241.   /// when the given loop \p L is considered as the innermost loop in the nest.
  242.   /// The computed cost is an estimate for the number of cache lines used by the
  243.   /// reference group. The representative reference cost is defined as:
  244.   ///   - equal to one if the reference is loop invariant, or
  245.   ///   - equal to '(TripCount * stride) / cache_line_size' if (a) loop \p L's
  246.   ///     induction variable is used only in the reference subscript associated
  247.   ///     with loop \p L, and (b) the reference stride is less than the cache
  248.   ///     line size, or
  249.   ///   - TripCount otherwise
  250.   CacheCostTy computeRefGroupCacheCost(const ReferenceGroupTy &RG,
  251.                                        const Loop &L) const;
  252.  
  253.   /// Sort the LoopCosts vector by decreasing cache cost.
  254.   void sortLoopCosts() {
  255.     stable_sort(LoopCosts,
  256.                 [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {
  257.                   return A.second > B.second;
  258.                 });
  259.   }
  260.  
  261. private:
  262.   /// Loops in the loop nest associated with this object.
  263.   LoopVectorTy Loops;
  264.  
  265.   /// Trip counts for the loops in the loop nest associated with this object.
  266.   SmallVector<LoopTripCountTy, 3> TripCounts;
  267.  
  268.   /// Cache costs for the loops in the loop nest associated with this object.
  269.   SmallVector<LoopCacheCostTy, 3> LoopCosts;
  270.  
  271.   /// The max. distance between array elements accessed in a loop so that the
  272.   /// elements are classified to have temporal reuse.
  273.   std::optional<unsigned> TRT;
  274.  
  275.   const LoopInfo &LI;
  276.   ScalarEvolution &SE;
  277.   TargetTransformInfo &TTI;
  278.   AAResults &AA;
  279.   DependenceInfo &DI;
  280. };
  281.  
  282. raw_ostream &operator<<(raw_ostream &OS, const IndexedReference &R);
  283. raw_ostream &operator<<(raw_ostream &OS, const CacheCost &CC);
  284.  
  285. /// Printer pass for the \c CacheCost results.
  286. class LoopCachePrinterPass : public PassInfoMixin<LoopCachePrinterPass> {
  287.   raw_ostream &OS;
  288.  
  289. public:
  290.   explicit LoopCachePrinterPass(raw_ostream &OS) : OS(OS) {}
  291.  
  292.   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
  293.                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
  294. };
  295.  
  296. } // namespace llvm
  297.  
  298. #endif // LLVM_ANALYSIS_LOOPCACHEANALYSIS_H
  299.