1 //===---- Delinearization.h - MultiDimensional Index Delinearization ------===// 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 // This implements an analysis pass that tries to delinearize all GEP 10 // instructions in all loops using the SCEV analysis functionality. This pass is 11 // only used for testing purposes: if your pass needs delinearization, please 12 // use the on-demand SCEVAddRecExpr::delinearize() function. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_ANALYSIS_DELINEARIZATION_H 17 #define LLVM_ANALYSIS_DELINEARIZATION_H 18 19 #include "llvm/IR/PassManager.h" 20 21 namespace llvm { 22 class raw_ostream; 23 template <typename T> class SmallVectorImpl; 24 class GetElementPtrInst; 25 class Instruction; 26 class ScalarEvolution; 27 class SCEV; 28 29 /// Compute the array dimensions Sizes from the set of Terms extracted from 30 /// the memory access function of this SCEVAddRecExpr (second step of 31 /// delinearization). 32 void findArrayDimensions(ScalarEvolution &SE, 33 SmallVectorImpl<const SCEV *> &Terms, 34 SmallVectorImpl<const SCEV *> &Sizes, 35 const SCEV *ElementSize); 36 37 /// Collect parametric terms occurring in step expressions (first step of 38 /// delinearization). 39 void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, 40 SmallVectorImpl<const SCEV *> &Terms); 41 42 /// Return in Subscripts the access functions for each dimension in Sizes 43 /// (third step of delinearization). 44 void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, 45 SmallVectorImpl<const SCEV *> &Subscripts, 46 SmallVectorImpl<const SCEV *> &Sizes); 47 /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the 48 /// subscripts and sizes of an array access. 49 /// 50 /// The delinearization is a 3 step process: the first two steps compute the 51 /// sizes of each subscript and the third step computes the access functions 52 /// for the delinearized array: 53 /// 54 /// 1. Find the terms in the step functions 55 /// 2. Compute the array size 56 /// 3. Compute the access function: divide the SCEV by the array size 57 /// starting with the innermost dimensions found in step 2. The Quotient 58 /// is the SCEV to be divided in the next step of the recursion. The 59 /// Remainder is the subscript of the innermost dimension. Loop over all 60 /// array dimensions computed in step 2. 61 /// 62 /// To compute a uniform array size for several memory accesses to the same 63 /// object, one can collect in step 1 all the step terms for all the memory 64 /// accesses, and compute in step 2 a unique array shape. This guarantees 65 /// that the array shape will be the same across all memory accesses. 66 /// 67 /// FIXME: We could derive the result of steps 1 and 2 from a description of 68 /// the array shape given in metadata. 69 /// 70 /// Example: 71 /// 72 /// A[][n][m] 73 /// 74 /// for i 75 /// for j 76 /// for k 77 /// A[j+k][2i][5i] = 78 /// 79 /// The initial SCEV: 80 /// 81 /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] 82 /// 83 /// 1. Find the different terms in the step functions: 84 /// -> [2*m, 5, n*m, n*m] 85 /// 86 /// 2. Compute the array size: sort and unique them 87 /// -> [n*m, 2*m, 5] 88 /// find the GCD of all the terms = 1 89 /// divide by the GCD and erase constant terms 90 /// -> [n*m, 2*m] 91 /// GCD = m 92 /// divide by GCD -> [n, 2] 93 /// remove constant terms 94 /// -> [n] 95 /// size of the array is A[unknown][n][m] 96 /// 97 /// 3. Compute the access function 98 /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m 99 /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k 100 /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k 101 /// The remainder is the subscript of the innermost array dimension: [5i]. 102 /// 103 /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n 104 /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k 105 /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k 106 /// The Remainder is the subscript of the next array dimension: [2i]. 107 /// 108 /// The subscript of the outermost dimension is the Quotient: [j+k]. 109 /// 110 /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. 111 void delinearize(ScalarEvolution &SE, const SCEV *Expr, 112 SmallVectorImpl<const SCEV *> &Subscripts, 113 SmallVectorImpl<const SCEV *> &Sizes, const SCEV *ElementSize); 114 115 /// Gathers the individual index expressions from a GEP instruction. 116 /// 117 /// This function optimistically assumes the GEP references into a fixed size 118 /// array. If this is actually true, this function returns a list of array 119 /// subscript expressions in \p Subscripts and a list of integers describing 120 /// the size of the individual array dimensions in \p Sizes. Both lists have 121 /// either equal length or the size list is one element shorter in case there 122 /// is no known size available for the outermost array dimension. Returns true 123 /// if successful and false otherwise. 124 bool getIndexExpressionsFromGEP(ScalarEvolution &SE, 125 const GetElementPtrInst *GEP, 126 SmallVectorImpl<const SCEV *> &Subscripts, 127 SmallVectorImpl<int> &Sizes); 128 129 /// Implementation of fixed size array delinearization. Try to delinearize 130 /// access function for a fixed size multi-dimensional array, by deriving 131 /// subscripts from GEP instructions. Returns true upon success and false 132 /// otherwise. \p Inst is the load/store instruction whose pointer operand is 133 /// the one we want to delinearize. \p AccessFn is its corresponding SCEV 134 /// expression w.r.t. the surrounding loop. 135 bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, 136 const SCEV *AccessFn, 137 SmallVectorImpl<const SCEV *> &Subscripts, 138 SmallVectorImpl<int> &Sizes); 139 140 struct DelinearizationPrinterPass 141 : public PassInfoMixin<DelinearizationPrinterPass> { 142 explicit DelinearizationPrinterPass(raw_ostream &OS); 143 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); isRequiredDelinearizationPrinterPass144 static bool isRequired() { return true; } 145 146 private: 147 raw_ostream &OS; 148 }; 149 } // namespace llvm 150 151 #endif // LLVM_ANALYSIS_DELINEARIZATION_H 152