blob: 670532c6d9a85fc948a22dec2341c0e0e1ff3908 [file] [log] [blame]
//===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This implements an analysis pass that tries to delinearize all GEP
// instructions in all loops using the SCEV analysis functionality. This pass is
// only used for testing purposes: if your pass needs delinearization, please
// use the on-demand SCEVAddRecExpr::delinearize() function.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/Delinearization.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionDivision.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
#define DL_NAME "delinearize"
#define DEBUG_TYPE DL_NAME
// Return true when S contains at least an undef value.
static inline bool containsUndefs(const SCEV *S) {
return SCEVExprContains(S, [](const SCEV *S) {
if (const auto *SU = dyn_cast<SCEVUnknown>(S))
return isa<UndefValue>(SU->getValue());
return false;
});
}
namespace {
// Collect all steps of SCEV expressions.
struct SCEVCollectStrides {
ScalarEvolution &SE;
SmallVectorImpl<const SCEV *> &Strides;
SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &S)
: SE(SE), Strides(S) {}
bool follow(const SCEV *S) {
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
Strides.push_back(AR->getStepRecurrence(SE));
return true;
}
bool isDone() const { return false; }
};
// Collect all SCEVUnknown and SCEVMulExpr expressions.
struct SCEVCollectTerms {
SmallVectorImpl<const SCEV *> &Terms;
SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T) : Terms(T) {}
bool follow(const SCEV *S) {
if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S) ||
isa<SCEVSignExtendExpr>(S)) {
if (!containsUndefs(S))
Terms.push_back(S);
// Stop recursion: once we collected a term, do not walk its operands.
return false;
}
// Keep looking.
return true;
}
bool isDone() const { return false; }
};
// Check if a SCEV contains an AddRecExpr.
struct SCEVHasAddRec {
bool &ContainsAddRec;
SCEVHasAddRec(bool &ContainsAddRec) : ContainsAddRec(ContainsAddRec) {
ContainsAddRec = false;
}
bool follow(const SCEV *S) {
if (isa<SCEVAddRecExpr>(S)) {
ContainsAddRec = true;
// Stop recursion: once we collected a term, do not walk its operands.
return false;
}
// Keep looking.
return true;
}
bool isDone() const { return false; }
};
// Find factors that are multiplied with an expression that (possibly as a
// subexpression) contains an AddRecExpr. In the expression:
//
// 8 * (100 + %p * %q * (%a + {0, +, 1}_loop))
//
// "%p * %q" are factors multiplied by the expression "(%a + {0, +, 1}_loop)"
// that contains the AddRec {0, +, 1}_loop. %p * %q are likely to be array size
// parameters as they form a product with an induction variable.
//
// This collector expects all array size parameters to be in the same MulExpr.
// It might be necessary to later add support for collecting parameters that are
// spread over different nested MulExpr.
struct SCEVCollectAddRecMultiplies {
SmallVectorImpl<const SCEV *> &Terms;
ScalarEvolution &SE;
SCEVCollectAddRecMultiplies(SmallVectorImpl<const SCEV *> &T,
ScalarEvolution &SE)
: Terms(T), SE(SE) {}
bool follow(const SCEV *S) {
if (auto *Mul = dyn_cast<SCEVMulExpr>(S)) {
bool HasAddRec = false;
SmallVector<const SCEV *, 0> Operands;
for (auto Op : Mul->operands()) {
const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Op);
if (Unknown && !isa<CallInst>(Unknown->getValue())) {
Operands.push_back(Op);
} else if (Unknown) {
HasAddRec = true;
} else {
bool ContainsAddRec = false;
SCEVHasAddRec ContiansAddRec(ContainsAddRec);
visitAll(Op, ContiansAddRec);
HasAddRec |= ContainsAddRec;
}
}
if (Operands.size() == 0)
return true;
if (!HasAddRec)
return false;
Terms.push_back(SE.getMulExpr(Operands));
// Stop recursion: once we collected a term, do not walk its operands.
return false;
}
// Keep looking.
return true;
}
bool isDone() const { return false; }
};
} // end anonymous namespace
/// Find parametric terms in this SCEVAddRecExpr. We first for parameters in
/// two places:
/// 1) The strides of AddRec expressions.
/// 2) Unknowns that are multiplied with AddRec expressions.
void llvm::collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr,
SmallVectorImpl<const SCEV *> &Terms) {
SmallVector<const SCEV *, 4> Strides;
SCEVCollectStrides StrideCollector(SE, Strides);
visitAll(Expr, StrideCollector);
LLVM_DEBUG({
dbgs() << "Strides:\n";
for (const SCEV *S : Strides)
dbgs() << *S << "\n";
});
for (const SCEV *S : Strides) {
SCEVCollectTerms TermCollector(Terms);
visitAll(S, TermCollector);
}
LLVM_DEBUG({
dbgs() << "Terms:\n";
for (const SCEV *T : Terms)
dbgs() << *T << "\n";
});
SCEVCollectAddRecMultiplies MulCollector(Terms, SE);
visitAll(Expr, MulCollector);
}
static bool findArrayDimensionsRec(ScalarEvolution &SE,
SmallVectorImpl<const SCEV *> &Terms,
SmallVectorImpl<const SCEV *> &Sizes) {
int Last = Terms.size() - 1;
const SCEV *Step = Terms[Last];
// End of recursion.
if (Last == 0) {
if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Step)) {
SmallVector<const SCEV *, 2> Qs;
for (const SCEV *Op : M->operands())
if (!isa<SCEVConstant>(Op))
Qs.push_back(Op);
Step = SE.getMulExpr(Qs);
}
Sizes.push_back(Step);
return true;
}
for (const SCEV *&Term : Terms) {
// Normalize the terms before the next call to findArrayDimensionsRec.
const SCEV *Q, *R;
SCEVDivision::divide(SE, Term, Step, &Q, &R);
// Bail out when GCD does not evenly divide one of the terms.
if (!R->isZero())
return false;
Term = Q;
}
// Remove all SCEVConstants.
erase_if(Terms, [](const SCEV *E) { return isa<SCEVConstant>(E); });
if (Terms.size() > 0)
if (!findArrayDimensionsRec(SE, Terms, Sizes))
return false;
Sizes.push_back(Step);
return true;
}
// Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter.
static inline bool containsParameters(SmallVectorImpl<const SCEV *> &Terms) {
for (const SCEV *T : Terms)
if (SCEVExprContains(T, [](const SCEV *S) { return isa<SCEVUnknown>(S); }))
return true;
return false;
}
// Return the number of product terms in S.
static inline int numberOfTerms(const SCEV *S) {
if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
return Expr->getNumOperands();
return 1;
}
static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {
if (isa<SCEVConstant>(T))
return nullptr;
if (isa<SCEVUnknown>(T))
return T;
if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(T)) {
SmallVector<const SCEV *, 2> Factors;
for (const SCEV *Op : M->operands())
if (!isa<SCEVConstant>(Op))
Factors.push_back(Op);
return SE.getMulExpr(Factors);
}
return T;
}
void llvm::findArrayDimensions(ScalarEvolution &SE,
SmallVectorImpl<const SCEV *> &Terms,
SmallVectorImpl<const SCEV *> &Sizes,
const SCEV *ElementSize) {
if (Terms.size() < 1 || !ElementSize)
return;
// Early return when Terms do not contain parameters: we do not delinearize
// non parametric SCEVs.
if (!containsParameters(Terms))
return;
LLVM_DEBUG({
dbgs() << "Terms:\n";
for (const SCEV *T : Terms)
dbgs() << *T << "\n";
});
// Remove duplicates.
array_pod_sort(Terms.begin(), Terms.end());
Terms.erase(std::unique(Terms.begin(), Terms.end()), Terms.end());
// Put larger terms first.
llvm::sort(Terms, [](const SCEV *LHS, const SCEV *RHS) {
return numberOfTerms(LHS) > numberOfTerms(RHS);
});
// Try to divide all terms by the element size. If term is not divisible by
// element size, proceed with the original term.
for (const SCEV *&Term : Terms) {
const SCEV *Q, *R;
SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);
if (!Q->isZero())
Term = Q;
}
SmallVector<const SCEV *, 4> NewTerms;
// Remove constant factors.
for (const SCEV *T : Terms)
if (const SCEV *NewT = removeConstantFactors(SE, T))
NewTerms.push_back(NewT);
LLVM_DEBUG({
dbgs() << "Terms after sorting:\n";
for (const SCEV *T : NewTerms)
dbgs() << *T << "\n";
});
if (NewTerms.empty() || !findArrayDimensionsRec(SE, NewTerms, Sizes)) {
Sizes.clear();
return;
}
// The last element to be pushed into Sizes is the size of an element.
Sizes.push_back(ElementSize);
LLVM_DEBUG({
dbgs() << "Sizes:\n";
for (const SCEV *S : Sizes)
dbgs() << *S << "\n";
});
}
void llvm::computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr,
SmallVectorImpl<const SCEV *> &Subscripts,
SmallVectorImpl<const SCEV *> &Sizes) {
// Early exit in case this SCEV is not an affine multivariate function.
if (Sizes.empty())
return;
if (auto *AR = dyn_cast<SCEVAddRecExpr>(Expr))
if (!AR->isAffine())
return;
const SCEV *Res = Expr;
int Last = Sizes.size() - 1;
for (int i = Last; i >= 0; i--) {
const SCEV *Q, *R;
SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R);
LLVM_DEBUG({
dbgs() << "Res: " << *Res << "\n";
dbgs() << "Sizes[i]: " << *Sizes[i] << "\n";
dbgs() << "Res divided by Sizes[i]:\n";
dbgs() << "Quotient: " << *Q << "\n";
dbgs() << "Remainder: " << *R << "\n";
});
Res = Q;
// Do not record the last subscript corresponding to the size of elements in
// the array.
if (i == Last) {
// Bail out if the byte offset is non-zero.
if (!R->isZero()) {
Subscripts.clear();
Sizes.clear();
return;
}
continue;
}
// Record the access function for the current subscript.
Subscripts.push_back(R);
}
// Also push in last position the remainder of the last division: it will be
// the access function of the innermost dimension.
Subscripts.push_back(Res);
std::reverse(Subscripts.begin(), Subscripts.end());
LLVM_DEBUG({
dbgs() << "Subscripts:\n";
for (const SCEV *S : Subscripts)
dbgs() << *S << "\n";
});
}
/// Splits the SCEV into two vectors of SCEVs representing the subscripts and
/// sizes of an array access. Returns the remainder of the delinearization that
/// is the offset start of the array. The SCEV->delinearize algorithm computes
/// the multiples of SCEV coefficients: that is a pattern matching of sub
/// expressions in the stride and base of a SCEV corresponding to the
/// computation of a GCD (greatest common divisor) of base and stride. When
/// SCEV->delinearize fails, it returns the SCEV unchanged.
///
/// For example: when analyzing the memory access A[i][j][k] in this loop nest
///
/// void foo(long n, long m, long o, double A[n][m][o]) {
///
/// for (long i = 0; i < n; i++)
/// for (long j = 0; j < m; j++)
/// for (long k = 0; k < o; k++)
/// A[i][j][k] = 1.0;
/// }
///
/// the delinearization input is the following AddRec SCEV:
///
/// AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
///
/// From this SCEV, we are able to say that the base offset of the access is %A
/// because it appears as an offset that does not divide any of the strides in
/// the loops:
///
/// CHECK: Base offset: %A
///
/// and then SCEV->delinearize determines the size of some of the dimensions of
/// the array as these are the multiples by which the strides are happening:
///
/// CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double)
/// bytes.
///
/// Note that the outermost dimension remains of UnknownSize because there are
/// no strides that would help identifying the size of the last dimension: when
/// the array has been statically allocated, one could compute the size of that
/// dimension by dividing the overall size of the array by the size of the known
/// dimensions: %m * %o * 8.
///
/// Finally delinearize provides the access functions for the array reference
/// that does correspond to A[i][j][k] of the above C testcase:
///
/// CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
///
/// The testcases are checking the output of a function pass:
/// DelinearizationPass that walks through all loads and stores of a function
/// asking for the SCEV of the memory access with respect to all enclosing
/// loops, calling SCEV->delinearize on that and printing the results.
void llvm::delinearize(ScalarEvolution &SE, const SCEV *Expr,
SmallVectorImpl<const SCEV *> &Subscripts,
SmallVectorImpl<const SCEV *> &Sizes,
const SCEV *ElementSize) {
// First step: collect parametric terms.
SmallVector<const SCEV *, 4> Terms;
collectParametricTerms(SE, Expr, Terms);
if (Terms.empty())
return;
// Second step: find subscript sizes.
findArrayDimensions(SE, Terms, Sizes, ElementSize);
if (Sizes.empty())
return;
// Third step: compute the access functions for each subscript.
computeAccessFunctions(SE, Expr, Subscripts, Sizes);
if (Subscripts.empty())
return;
LLVM_DEBUG({
dbgs() << "succeeded to delinearize " << *Expr << "\n";
dbgs() << "ArrayDecl[UnknownSize]";
for (const SCEV *S : Sizes)
dbgs() << "[" << *S << "]";
dbgs() << "\nArrayRef";
for (const SCEV *S : Subscripts)
dbgs() << "[" << *S << "]";
dbgs() << "\n";
});
}
bool llvm::getIndexExpressionsFromGEP(ScalarEvolution &SE,
const GetElementPtrInst *GEP,
SmallVectorImpl<const SCEV *> &Subscripts,
SmallVectorImpl<int> &Sizes) {
assert(Subscripts.empty() && Sizes.empty() &&
"Expected output lists to be empty on entry to this function.");
assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
Type *Ty = nullptr;
bool DroppedFirstDim = false;
for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
if (i == 1) {
Ty = GEP->getSourceElementType();
if (auto *Const = dyn_cast<SCEVConstant>(Expr))
if (Const->getValue()->isZero()) {
DroppedFirstDim = true;
continue;
}
Subscripts.push_back(Expr);
continue;
}
auto *ArrayTy = dyn_cast<ArrayType>(Ty);
if (!ArrayTy) {
Subscripts.clear();
Sizes.clear();
return false;
}
Subscripts.push_back(Expr);
if (!(DroppedFirstDim && i == 2))
Sizes.push_back(ArrayTy->getNumElements());
Ty = ArrayTy->getElementType();
}
return !Subscripts.empty();
}
namespace {
class Delinearization : public FunctionPass {
Delinearization(const Delinearization &); // do not implement
protected:
Function *F;
LoopInfo *LI;
ScalarEvolution *SE;
public:
static char ID; // Pass identification, replacement for typeid
Delinearization() : FunctionPass(ID) {
initializeDelinearizationPass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &F) override;
void getAnalysisUsage(AnalysisUsage &AU) const override;
void print(raw_ostream &O, const Module *M = nullptr) const override;
};
void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
ScalarEvolution *SE) {
O << "Delinearization on function " << F->getName() << ":\n";
for (Instruction &Inst : instructions(F)) {
// Only analyze loads and stores.
if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
!isa<GetElementPtrInst>(&Inst))
continue;
const BasicBlock *BB = Inst.getParent();
// Delinearize the memory access as analyzed in all the surrounding loops.
// Do not analyze memory accesses outside loops.
for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
const SCEVUnknown *BasePointer =
dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
// Do not delinearize if we cannot find the base pointer.
if (!BasePointer)
break;
AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
O << "\n";
O << "Inst:" << Inst << "\n";
O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
O << "AccessFunction: " << *AccessFn << "\n";
SmallVector<const SCEV *, 3> Subscripts, Sizes;
delinearize(*SE, AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
if (Subscripts.size() == 0 || Sizes.size() == 0 ||
Subscripts.size() != Sizes.size()) {
O << "failed to delinearize\n";
continue;
}
O << "Base offset: " << *BasePointer << "\n";
O << "ArrayDecl[UnknownSize]";
int Size = Subscripts.size();
for (int i = 0; i < Size - 1; i++)
O << "[" << *Sizes[i] << "]";
O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
O << "ArrayRef";
for (int i = 0; i < Size; i++)
O << "[" << *Subscripts[i] << "]";
O << "\n";
}
}
}
} // end anonymous namespace
void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<LoopInfoWrapperPass>();
AU.addRequired<ScalarEvolutionWrapperPass>();
}
bool Delinearization::runOnFunction(Function &F) {
this->F = &F;
SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
return false;
}
void Delinearization::print(raw_ostream &O, const Module *) const {
printDelinearization(O, F, LI, SE);
}
char Delinearization::ID = 0;
static const char delinearization_name[] = "Delinearization";
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
true)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS)
: OS(OS) {}
PreservedAnalyses DelinearizationPrinterPass::run(Function &F,
FunctionAnalysisManager &AM) {
printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
&AM.getResult<ScalarEvolutionAnalysis>(F));
return PreservedAnalyses::all();
}