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