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