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 ScalarEvolution; 26class 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). 31void 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). 38void 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). 43void 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]. 110void 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. 123bool 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. 134bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, 135 const SCEV *AccessFn, 136 SmallVectorImpl<const SCEV *> &Subscripts, 137 SmallVectorImpl<int> &Sizes); 138 139struct DelinearizationPrinterPass 140 : public PassInfoMixin<DelinearizationPrinterPass> { 141 explicit DelinearizationPrinterPass(raw_ostream &OS); 142 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 143 static bool isRequired() { return true; } 144 145private: 146 raw_ostream &OS; 147}; 148} // namespace llvm 149 150#endif // LLVM_ANALYSIS_DELINEARIZATION_H 151