Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
14 | pmbaty | 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 | |||
144 | private: |
||
145 | raw_ostream &OS; |
||
146 | }; |
||
147 | } // namespace llvm |
||
148 | |||
149 | #endif // LLVM_ANALYSIS_DELINEARIZATION_H |