LLVM  14.0.0git
Delinearization.h
Go to the documentation of this file.
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"
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 
129  : public PassInfoMixin<DelinearizationPrinterPass> {
132 
133 private:
134  raw_ostream &OS;
135 };
136 } // namespace llvm
137 
138 #endif // LLVM_ANALYSIS_DELINEARIZATION_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:62
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::DelinearizationPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Delinearization.cpp:626
llvm::collectParametricTerms
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
Definition: Delinearization.cpp:175
llvm::DelinearizationPrinterPass
Definition: Delinearization.h:128
llvm::findArrayDimensions
void findArrayDimensions(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Terms, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Compute the array dimensions Sizes from the set of Terms extracted from the memory access function of...
Definition: Delinearization.cpp:281
llvm::getIndexExpressionsFromGEP
bool getIndexExpressionsFromGEP(ScalarEvolution &SE, const GetElementPtrInst *GEP, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Gathers the individual index expressions from a GEP instruction.
Definition: Delinearization.cpp:488
llvm::delinearize
void delinearize(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes, const SCEV *ElementSize)
Split this SCEVAddRecExpr into two vectors of SCEVs representing the subscripts and sizes of an array...
Definition: Delinearization.cpp:452
llvm::computeAccessFunctions
void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes)
Return in Subscripts the access functions for each dimension in Sizes (third step of delinearization)...
Definition: Delinearization.cpp:345
PassManager.h
SmallVector.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
raw_ostream.h
llvm::DelinearizationPrinterPass::DelinearizationPrinterPass
DelinearizationPrinterPass(raw_ostream &OS)
Definition: Delinearization.cpp:624