LLVM 22.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/IR/PassManager.h"
20
21namespace llvm {
22class raw_ostream;
23template <typename T> class SmallVectorImpl;
24class GetElementPtrInst;
25class Instruction;
26class ScalarEvolution;
27class 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).
32void 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).
39void 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).
44void 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].
111void delinearize(ScalarEvolution &SE, const SCEV *Expr,
112 SmallVectorImpl<const SCEV *> &Subscripts,
113 SmallVectorImpl<const SCEV *> &Sizes, const SCEV *ElementSize);
114
115/// Compute the dimensions of fixed size array from \Expr and save the results
116/// in \p Sizes.
117bool findFixedSizeArrayDimensions(ScalarEvolution &SE, const SCEV *Expr,
118 SmallVectorImpl<uint64_t> &Sizes,
119 const SCEV *ElementSize);
120
121/// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
122/// subscripts and sizes of an access to a fixed size array. This is a special
123/// case of delinearization for fixed size arrays.
124///
125/// The delinearization is a 2 step process: the first step estimates the sizes
126/// of each dimension of the array. The second step computes the access
127/// functions for the delinearized array:
128///
129/// 1. Compute the array size
130/// 2. Compute the access function: same as normal delinearization
131///
132/// Different from the normal delinearization, this function assumes that NO
133/// terms exist in the \p Expr. In other words, it assumes that the all step
134/// values are constant.
135///
136/// This function is intended to replace getIndexExpressionsFromGEP and
137/// tryDelinearizeFixedSizeImpl. They rely on the GEP source element type so
138/// that they will be removed in the future.
139bool delinearizeFixedSizeArray(ScalarEvolution &SE, const SCEV *Expr,
140 SmallVectorImpl<const SCEV *> &Subscripts,
141 SmallVectorImpl<const SCEV *> &Sizes,
142 const SCEV *ElementSize);
143
144/// Gathers the individual index expressions from a GEP instruction.
145///
146/// This function optimistically assumes the GEP references into a fixed size
147/// array. If this is actually true, this function returns a list of array
148/// subscript expressions in \p Subscripts and a list of integers describing
149/// the size of the individual array dimensions in \p Sizes. Both lists have
150/// either equal length or the size list is one element shorter in case there
151/// is no known size available for the outermost array dimension. Returns true
152/// if successful and false otherwise.
153bool getIndexExpressionsFromGEP(ScalarEvolution &SE,
154 const GetElementPtrInst *GEP,
155 SmallVectorImpl<const SCEV *> &Subscripts,
156 SmallVectorImpl<int> &Sizes);
157
158/// Implementation of fixed size array delinearization. Try to delinearize
159/// access function for a fixed size multi-dimensional array, by deriving
160/// subscripts from GEP instructions. Returns true upon success and false
161/// otherwise. \p Inst is the load/store instruction whose pointer operand is
162/// the one we want to delinearize. \p AccessFn is its corresponding SCEV
163/// expression w.r.t. the surrounding loop.
164bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst,
165 const SCEV *AccessFn,
166 SmallVectorImpl<const SCEV *> &Subscripts,
167 SmallVectorImpl<int> &Sizes);
168
170 : public PassInfoMixin<DelinearizationPrinterPass> {
173 static bool isRequired() { return true; }
174
175private:
177};
178} // namespace llvm
179
180#endif // LLVM_ANALYSIS_DELINEARIZATION_H
Hexagon Common GEP
This header defines various interfaces for pass management in LLVM.
#define F(x, y, z)
Definition: MD5.cpp:55
raw_pwrite_stream & OS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:255
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:112
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< const SCEV * > &Terms)
Collect parametric terms occurring in step expressions (first step of delinearization).
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...
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)...
bool delinearizeFixedSizeArray(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 acces...
bool getIndexExpressionsFromGEP(ScalarEvolution &SE, const GetElementPtrInst *GEP, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Gathers the individual index expressions from a GEP instruction.
bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< int > &Sizes)
Implementation of fixed size array delinearization.
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...
bool findFixedSizeArrayDimensions(ScalarEvolution &SE, const SCEV *Expr, SmallVectorImpl< uint64_t > &Sizes, const SCEV *ElementSize)
Compute the dimensions of fixed size array from \Expr and save the results in Sizes.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:70