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 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 | /// Implementation of fixed size array delinearization. Try to delinearize |
129 | /// access function for a fixed size multi-dimensional array, by deriving |
130 | /// subscripts from GEP instructions. Returns true upon success and false |
131 | /// otherwise. \p Inst is the load/store instruction whose pointer operand is |
132 | /// the one we want to delinearize. \p AccessFn is its corresponding SCEV |
133 | /// expression w.r.t. the surrounding loop. |
134 | bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, |
135 | const SCEV *AccessFn, |
136 | SmallVectorImpl<const SCEV *> &Subscripts, |
137 | SmallVectorImpl<int> &Sizes); |
138 | |
139 | struct DelinearizationPrinterPass |
140 | : public PassInfoMixin<DelinearizationPrinterPass> { |
141 | explicit DelinearizationPrinterPass(raw_ostream &OS); |
142 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
143 | static bool isRequired() { return true; } |
144 | |
145 | private: |
146 | raw_ostream &OS; |
147 | }; |
148 | } // namespace llvm |
149 | |
150 | #endif // LLVM_ANALYSIS_DELINEARIZATION_H |
151 | |