Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

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