889 lines · cpp
1//===---- Delinearization.cpp - 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-exception6//7//===----------------------------------------------------------------------===//8//9// This implements an analysis pass that tries to delinearize all GEP10// instructions in all loops using the SCEV analysis functionality. This pass is11// only used for testing purposes: if your pass needs delinearization, please12// use the on-demand SCEVAddRecExpr::delinearize() function.13//14//===----------------------------------------------------------------------===//15 16#include "llvm/Analysis/Delinearization.h"17#include "llvm/Analysis/LoopInfo.h"18#include "llvm/Analysis/ScalarEvolution.h"19#include "llvm/Analysis/ScalarEvolutionDivision.h"20#include "llvm/Analysis/ScalarEvolutionExpressions.h"21#include "llvm/IR/Constants.h"22#include "llvm/IR/DerivedTypes.h"23#include "llvm/IR/Function.h"24#include "llvm/IR/InstIterator.h"25#include "llvm/IR/Instructions.h"26#include "llvm/IR/PassManager.h"27#include "llvm/Support/CommandLine.h"28#include "llvm/Support/Debug.h"29#include "llvm/Support/raw_ostream.h"30 31using namespace llvm;32 33#define DL_NAME "delinearize"34#define DEBUG_TYPE DL_NAME35 36static cl::opt<bool> UseFixedSizeArrayHeuristic(37 "delinearize-use-fixed-size-array-heuristic", cl::init(false), cl::Hidden,38 cl::desc("When printing analysis, use the heuristic for fixed-size arrays "39 "if the default delinearizetion fails."));40 41// Return true when S contains at least an undef value.42static inline bool containsUndefs(const SCEV *S) {43 return SCEVExprContains(S, [](const SCEV *S) {44 if (const auto *SU = dyn_cast<SCEVUnknown>(S))45 return isa<UndefValue>(SU->getValue());46 return false;47 });48}49 50namespace {51 52// Collect all steps of SCEV expressions.53struct SCEVCollectStrides {54 ScalarEvolution &SE;55 SmallVectorImpl<const SCEV *> &Strides;56 57 SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &S)58 : SE(SE), Strides(S) {}59 60 bool follow(const SCEV *S) {61 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))62 Strides.push_back(AR->getStepRecurrence(SE));63 return true;64 }65 66 bool isDone() const { return false; }67};68 69// Collect all SCEVUnknown and SCEVMulExpr expressions.70struct SCEVCollectTerms {71 SmallVectorImpl<const SCEV *> &Terms;72 73 SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T) : Terms(T) {}74 75 bool follow(const SCEV *S) {76 if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S) ||77 isa<SCEVSignExtendExpr>(S)) {78 if (!containsUndefs(S))79 Terms.push_back(S);80 81 // Stop recursion: once we collected a term, do not walk its operands.82 return false;83 }84 85 // Keep looking.86 return true;87 }88 89 bool isDone() const { return false; }90};91 92// Check if a SCEV contains an AddRecExpr.93struct SCEVHasAddRec {94 bool &ContainsAddRec;95 96 SCEVHasAddRec(bool &ContainsAddRec) : ContainsAddRec(ContainsAddRec) {97 ContainsAddRec = false;98 }99 100 bool follow(const SCEV *S) {101 if (isa<SCEVAddRecExpr>(S)) {102 ContainsAddRec = true;103 104 // Stop recursion: once we collected a term, do not walk its operands.105 return false;106 }107 108 // Keep looking.109 return true;110 }111 112 bool isDone() const { return false; }113};114 115// Find factors that are multiplied with an expression that (possibly as a116// subexpression) contains an AddRecExpr. In the expression:117//118// 8 * (100 + %p * %q * (%a + {0, +, 1}_loop))119//120// "%p * %q" are factors multiplied by the expression "(%a + {0, +, 1}_loop)"121// that contains the AddRec {0, +, 1}_loop. %p * %q are likely to be array size122// parameters as they form a product with an induction variable.123//124// This collector expects all array size parameters to be in the same MulExpr.125// It might be necessary to later add support for collecting parameters that are126// spread over different nested MulExpr.127struct SCEVCollectAddRecMultiplies {128 SmallVectorImpl<const SCEV *> &Terms;129 ScalarEvolution &SE;130 131 SCEVCollectAddRecMultiplies(SmallVectorImpl<const SCEV *> &T,132 ScalarEvolution &SE)133 : Terms(T), SE(SE) {}134 135 bool follow(const SCEV *S) {136 if (auto *Mul = dyn_cast<SCEVMulExpr>(S)) {137 bool HasAddRec = false;138 SmallVector<const SCEV *, 0> Operands;139 for (const SCEV *Op : Mul->operands()) {140 const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Op);141 if (Unknown && !isa<CallInst>(Unknown->getValue())) {142 Operands.push_back(Op);143 } else if (Unknown) {144 HasAddRec = true;145 } else {146 bool ContainsAddRec = false;147 SCEVHasAddRec ContiansAddRec(ContainsAddRec);148 visitAll(Op, ContiansAddRec);149 HasAddRec |= ContainsAddRec;150 }151 }152 if (Operands.size() == 0)153 return true;154 155 if (!HasAddRec)156 return false;157 158 Terms.push_back(SE.getMulExpr(Operands));159 // Stop recursion: once we collected a term, do not walk its operands.160 return false;161 }162 163 // Keep looking.164 return true;165 }166 167 bool isDone() const { return false; }168};169 170} // end anonymous namespace171 172/// Find parametric terms in this SCEVAddRecExpr. We first for parameters in173/// two places:174/// 1) The strides of AddRec expressions.175/// 2) Unknowns that are multiplied with AddRec expressions.176void llvm::collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr,177 SmallVectorImpl<const SCEV *> &Terms) {178 SmallVector<const SCEV *, 4> Strides;179 SCEVCollectStrides StrideCollector(SE, Strides);180 visitAll(Expr, StrideCollector);181 182 LLVM_DEBUG({183 dbgs() << "Strides:\n";184 for (const SCEV *S : Strides)185 dbgs().indent(2) << *S << "\n";186 });187 188 for (const SCEV *S : Strides) {189 SCEVCollectTerms TermCollector(Terms);190 visitAll(S, TermCollector);191 }192 193 LLVM_DEBUG({194 dbgs() << "Terms:\n";195 for (const SCEV *T : Terms)196 dbgs().indent(2) << *T << "\n";197 });198 199 SCEVCollectAddRecMultiplies MulCollector(Terms, SE);200 visitAll(Expr, MulCollector);201}202 203static bool findArrayDimensionsRec(ScalarEvolution &SE,204 SmallVectorImpl<const SCEV *> &Terms,205 SmallVectorImpl<const SCEV *> &Sizes) {206 int Last = Terms.size() - 1;207 const SCEV *Step = Terms[Last];208 209 // End of recursion.210 if (Last == 0) {211 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Step)) {212 SmallVector<const SCEV *, 2> Qs;213 for (const SCEV *Op : M->operands())214 if (!isa<SCEVConstant>(Op))215 Qs.push_back(Op);216 217 Step = SE.getMulExpr(Qs);218 }219 220 Sizes.push_back(Step);221 return true;222 }223 224 for (const SCEV *&Term : Terms) {225 // Normalize the terms before the next call to findArrayDimensionsRec.226 const SCEV *Q, *R;227 SCEVDivision::divide(SE, Term, Step, &Q, &R);228 229 // Bail out when GCD does not evenly divide one of the terms.230 if (!R->isZero())231 return false;232 233 Term = Q;234 }235 236 // Remove all SCEVConstants.237 erase_if(Terms, [](const SCEV *E) { return isa<SCEVConstant>(E); });238 239 if (Terms.size() > 0)240 if (!findArrayDimensionsRec(SE, Terms, Sizes))241 return false;242 243 Sizes.push_back(Step);244 return true;245}246 247// Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter.248static inline bool containsParameters(SmallVectorImpl<const SCEV *> &Terms) {249 for (const SCEV *T : Terms)250 if (SCEVExprContains(T, [](const SCEV *S) { return isa<SCEVUnknown>(S); }))251 return true;252 253 return false;254}255 256// Return the number of product terms in S.257static inline int numberOfTerms(const SCEV *S) {258 if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))259 return Expr->getNumOperands();260 return 1;261}262 263static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {264 if (isa<SCEVConstant>(T))265 return nullptr;266 267 if (isa<SCEVUnknown>(T))268 return T;269 270 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(T)) {271 SmallVector<const SCEV *, 2> Factors;272 for (const SCEV *Op : M->operands())273 if (!isa<SCEVConstant>(Op))274 Factors.push_back(Op);275 276 return SE.getMulExpr(Factors);277 }278 279 return T;280}281 282void llvm::findArrayDimensions(ScalarEvolution &SE,283 SmallVectorImpl<const SCEV *> &Terms,284 SmallVectorImpl<const SCEV *> &Sizes,285 const SCEV *ElementSize) {286 if (Terms.size() < 1 || !ElementSize)287 return;288 289 // Early return when Terms do not contain parameters: we do not delinearize290 // non parametric SCEVs.291 if (!containsParameters(Terms))292 return;293 294 LLVM_DEBUG({295 dbgs() << "Terms:\n";296 for (const SCEV *T : Terms)297 dbgs().indent(2) << *T << "\n";298 });299 300 // Remove duplicates.301 array_pod_sort(Terms.begin(), Terms.end());302 Terms.erase(llvm::unique(Terms), Terms.end());303 304 // Put larger terms first.305 llvm::sort(Terms, [](const SCEV *LHS, const SCEV *RHS) {306 return numberOfTerms(LHS) > numberOfTerms(RHS);307 });308 309 // Try to divide all terms by the element size. If term is not divisible by310 // element size, proceed with the original term.311 for (const SCEV *&Term : Terms) {312 const SCEV *Q, *R;313 SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);314 if (!Q->isZero())315 Term = Q;316 }317 318 SmallVector<const SCEV *, 4> NewTerms;319 320 // Remove constant factors.321 for (const SCEV *T : Terms)322 if (const SCEV *NewT = removeConstantFactors(SE, T))323 NewTerms.push_back(NewT);324 325 LLVM_DEBUG({326 dbgs() << "Terms after sorting:\n";327 for (const SCEV *T : NewTerms)328 dbgs().indent(2) << *T << "\n";329 });330 331 if (NewTerms.empty() || !findArrayDimensionsRec(SE, NewTerms, Sizes)) {332 Sizes.clear();333 return;334 }335 336 // The last element to be pushed into Sizes is the size of an element.337 Sizes.push_back(ElementSize);338 339 LLVM_DEBUG({340 dbgs() << "Sizes:\n";341 for (const SCEV *S : Sizes)342 dbgs().indent(2) << *S << "\n";343 });344}345 346void llvm::computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr,347 SmallVectorImpl<const SCEV *> &Subscripts,348 SmallVectorImpl<const SCEV *> &Sizes) {349 // Early exit in case this SCEV is not an affine multivariate function.350 if (Sizes.empty())351 return;352 353 if (auto *AR = dyn_cast<SCEVAddRecExpr>(Expr))354 if (!AR->isAffine())355 return;356 357 LLVM_DEBUG(dbgs() << "\ncomputeAccessFunctions\n"358 << "Memory Access Function: " << *Expr << "\n");359 360 const SCEV *Res = Expr;361 int Last = Sizes.size() - 1;362 363 for (int i = Last; i >= 0; i--) {364 const SCEV *Size = Sizes[i];365 const SCEV *Q, *R;366 367 SCEVDivision::divide(SE, Res, Size, &Q, &R);368 369 LLVM_DEBUG({370 dbgs() << "Computing 'MemAccFn / Sizes[" << i << "]':\n";371 dbgs() << " MemAccFn: " << *Res << "\n";372 dbgs() << " Sizes[" << i << "]: " << *Size << "\n";373 dbgs() << " Quotient (Leftover): " << *Q << "\n";374 dbgs() << " Remainder (Subscript Access Function): " << *R << "\n";375 });376 377 Res = Q;378 379 // Do not record the last subscript corresponding to the size of elements in380 // the array.381 if (i == Last) {382 383 // Bail out if the byte offset is non-zero.384 if (!R->isZero()) {385 Subscripts.clear();386 Sizes.clear();387 return;388 }389 390 continue;391 }392 393 // Record the access function for the current subscript.394 Subscripts.push_back(R);395 }396 397 // Also push in last position the remainder of the last division: it will be398 // the access function of the innermost dimension.399 Subscripts.push_back(Res);400 401 std::reverse(Subscripts.begin(), Subscripts.end());402 403 LLVM_DEBUG({404 dbgs() << "Subscripts:\n";405 for (const SCEV *S : Subscripts)406 dbgs().indent(2) << *S << "\n";407 dbgs() << "\n";408 });409}410 411/// Splits the SCEV into two vectors of SCEVs representing the subscripts and412/// sizes of an array access. Returns the remainder of the delinearization that413/// is the offset start of the array. The SCEV->delinearize algorithm computes414/// the multiples of SCEV coefficients: that is a pattern matching of sub415/// expressions in the stride and base of a SCEV corresponding to the416/// computation of a GCD (greatest common divisor) of base and stride. When417/// SCEV->delinearize fails, it returns the SCEV unchanged.418///419/// For example: when analyzing the memory access A[i][j][k] in this loop nest420///421/// void foo(long n, long m, long o, double A[n][m][o]) {422///423/// for (long i = 0; i < n; i++)424/// for (long j = 0; j < m; j++)425/// for (long k = 0; k < o; k++)426/// A[i][j][k] = 1.0;427/// }428///429/// the delinearization input is the following AddRec SCEV:430///431/// AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>432///433/// From this SCEV, we are able to say that the base offset of the access is %A434/// because it appears as an offset that does not divide any of the strides in435/// the loops:436///437/// CHECK: Base offset: %A438///439/// and then SCEV->delinearize determines the size of some of the dimensions of440/// the array as these are the multiples by which the strides are happening:441///442/// CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double)443/// bytes.444///445/// Note that the outermost dimension remains of UnknownSize because there are446/// no strides that would help identifying the size of the last dimension: when447/// the array has been statically allocated, one could compute the size of that448/// dimension by dividing the overall size of the array by the size of the known449/// dimensions: %m * %o * 8.450///451/// Finally delinearize provides the access functions for the array reference452/// that does correspond to A[i][j][k] of the above C testcase:453///454/// CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]455///456/// The testcases are checking the output of a function pass:457/// DelinearizationPass that walks through all loads and stores of a function458/// asking for the SCEV of the memory access with respect to all enclosing459/// loops, calling SCEV->delinearize on that and printing the results.460void llvm::delinearize(ScalarEvolution &SE, const SCEV *Expr,461 SmallVectorImpl<const SCEV *> &Subscripts,462 SmallVectorImpl<const SCEV *> &Sizes,463 const SCEV *ElementSize) {464 // First step: collect parametric terms.465 SmallVector<const SCEV *, 4> Terms;466 collectParametricTerms(SE, Expr, Terms);467 468 if (Terms.empty())469 return;470 471 // Second step: find subscript sizes.472 findArrayDimensions(SE, Terms, Sizes, ElementSize);473 474 if (Sizes.empty())475 return;476 477 // Third step: compute the access functions for each subscript.478 computeAccessFunctions(SE, Expr, Subscripts, Sizes);479}480 481static std::optional<APInt> tryIntoAPInt(const SCEV *S) {482 if (const auto *Const = dyn_cast<SCEVConstant>(S))483 return Const->getAPInt();484 return std::nullopt;485}486 487/// Collects the absolute values of constant steps for all induction variables.488/// Returns true if we can prove that all step recurrences are constants and \p489/// Expr is divisible by \p ElementSize. Each step recurrence is stored in \p490/// Steps after divided by \p ElementSize.491static bool collectConstantAbsSteps(ScalarEvolution &SE, const SCEV *Expr,492 SmallVectorImpl<uint64_t> &Steps,493 uint64_t ElementSize) {494 // End of recursion. The constant value also must be a multiple of495 // ElementSize.496 if (const auto *Const = dyn_cast<SCEVConstant>(Expr)) {497 const uint64_t Mod = Const->getAPInt().urem(ElementSize);498 return Mod == 0;499 }500 501 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Expr);502 if (!AR || !AR->isAffine())503 return false;504 505 const SCEV *Step = AR->getStepRecurrence(SE);506 std::optional<APInt> StepAPInt = tryIntoAPInt(Step);507 if (!StepAPInt)508 return false;509 510 APInt Q;511 uint64_t R;512 APInt::udivrem(StepAPInt->abs(), ElementSize, Q, R);513 if (R != 0)514 return false;515 516 // Bail out when the step is too large.517 std::optional<uint64_t> StepVal = Q.tryZExtValue();518 if (!StepVal)519 return false;520 521 Steps.push_back(*StepVal);522 return collectConstantAbsSteps(SE, AR->getStart(), Steps, ElementSize);523}524 525bool llvm::findFixedSizeArrayDimensions(ScalarEvolution &SE, const SCEV *Expr,526 SmallVectorImpl<uint64_t> &Sizes,527 const SCEV *ElementSize) {528 if (!ElementSize)529 return false;530 531 std::optional<APInt> ElementSizeAPInt = tryIntoAPInt(ElementSize);532 if (!ElementSizeAPInt || *ElementSizeAPInt == 0)533 return false;534 535 std::optional<uint64_t> ElementSizeConst = ElementSizeAPInt->tryZExtValue();536 537 // Early exit when ElementSize is not a positive constant.538 if (!ElementSizeConst)539 return false;540 541 if (!collectConstantAbsSteps(SE, Expr, Sizes, *ElementSizeConst) ||542 Sizes.empty()) {543 Sizes.clear();544 return false;545 }546 547 // At this point, Sizes contains the absolute step recurrences for all548 // induction variables. Each step recurrence must be a multiple of the size of549 // the array element. Assuming that the each value represents the size of an550 // array for each dimension, attempts to restore the length of each dimension551 // by dividing the step recurrence by the next smaller value. For example, if552 // we have the following AddRec SCEV:553 //554 // AddRec: {{{0,+,2048}<%for.i>,+,256}<%for.j>,+,8}<%for.k> (ElementSize=8)555 //556 // Then Sizes will become [256, 32, 1] after sorted. We don't know the size of557 // the outermost dimension, the next dimension will be computed as 256 / 32 =558 // 8, and the last dimension will be computed as 32 / 1 = 32. Thus it results559 // in like Arr[UnknownSize][8][32] with elements of size 8 bytes, where Arr is560 // a base pointer.561 //562 // TODO: Catch more cases, e.g., when a step recurrence is not divisible by563 // the next smaller one, like A[i][3*j].564 llvm::sort(Sizes.rbegin(), Sizes.rend());565 Sizes.erase(llvm::unique(Sizes), Sizes.end());566 567 // The last element in Sizes should be ElementSize. At this point, all values568 // in Sizes are assumed to be divided by ElementSize, so replace it with 1.569 assert(Sizes.back() != 0 && "Unexpected zero size in Sizes.");570 Sizes.back() = 1;571 572 for (unsigned I = 0; I + 1 < Sizes.size(); I++) {573 uint64_t PrevSize = Sizes[I + 1];574 if (Sizes[I] % PrevSize) {575 Sizes.clear();576 return false;577 }578 Sizes[I] /= PrevSize;579 }580 581 // Finally, the last element in Sizes should be ElementSize.582 Sizes.back() = *ElementSizeConst;583 return true;584}585 586/// Splits the SCEV into two vectors of SCEVs representing the subscripts and587/// sizes of an array access, assuming that the array is a fixed size array.588///589/// E.g., if we have the code like as follows:590///591/// double A[42][8][32];592/// for i593/// for j594/// for k595/// use A[i][j][k]596///597/// The access function will be represented as an AddRec SCEV like:598///599/// AddRec: {{{0,+,2048}<%for.i>,+,256}<%for.j>,+,8}<%for.k> (ElementSize=8)600///601/// Then findFixedSizeArrayDimensions infers the size of each dimension of the602/// array based on the fact that the value of the step recurrence is a multiple603/// of the size of the corresponding array element. In the above example, it604/// results in the following:605///606/// CHECK: ArrayDecl[UnknownSize][8][32] with elements of 8 bytes.607///608/// Finally each subscript will be computed as follows:609///610/// CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]611///612/// Note that this function doesn't check the range of possible values for each613/// subscript, so the caller should perform additional boundary checks if614/// necessary.615///616/// Also note that this function doesn't guarantee that the original array size617/// is restored "correctly". For example, in the following case:618///619/// double A[42][4][64];620/// double B[42][8][32];621/// for i622/// for j623/// for k624/// use A[i][j][k]625/// use B[i][2*j][k]626///627/// The access function for both accesses will be the same:628///629/// AddRec: {{{0,+,2048}<%for.i>,+,512}<%for.j>,+,8}<%for.k> (ElementSize=8)630///631/// The array sizes for both A and B will be computed as632/// ArrayDecl[UnknownSize][4][64], which matches for A, but not for B.633///634/// TODO: At the moment, this function can handle only simple cases. For635/// example, we cannot handle a case where a step recurrence is not divisible636/// by the next smaller step recurrence, e.g., A[i][3*j].637bool llvm::delinearizeFixedSizeArray(ScalarEvolution &SE, const SCEV *Expr,638 SmallVectorImpl<const SCEV *> &Subscripts,639 SmallVectorImpl<const SCEV *> &Sizes,640 const SCEV *ElementSize) {641 642 // First step: find the fixed array size.643 SmallVector<uint64_t, 4> ConstSizes;644 if (!findFixedSizeArrayDimensions(SE, Expr, ConstSizes, ElementSize)) {645 Sizes.clear();646 return false;647 }648 649 // Convert the constant size to SCEV.650 for (uint64_t Size : ConstSizes)651 Sizes.push_back(SE.getConstant(Expr->getType(), Size));652 653 // Second step: compute the access functions for each subscript.654 computeAccessFunctions(SE, Expr, Subscripts, Sizes);655 656 return !Subscripts.empty();657}658 659static bool isKnownNonNegative(ScalarEvolution *SE, const SCEV *S,660 const Value *Ptr) {661 bool Inbounds = false;662 if (auto *SrcGEP = dyn_cast<GetElementPtrInst>(Ptr))663 Inbounds = SrcGEP->isInBounds();664 if (Inbounds) {665 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {666 if (AddRec->isAffine()) {667 // We know S is for Ptr, the operand on a load/store, so doesn't wrap.668 // If both parts are NonNegative, the end result will be NonNegative669 if (SE->isKnownNonNegative(AddRec->getStart()) &&670 SE->isKnownNonNegative(AddRec->getOperand(1)))671 return true;672 }673 }674 }675 676 return SE->isKnownNonNegative(S);677}678 679/// Compare to see if S is less than Size, using680///681/// isKnownNegative(S - Size)682///683/// with some extra checking if S is an AddRec and we can prove less-than using684/// the loop bounds.685static bool isKnownLessThan(ScalarEvolution *SE, const SCEV *S,686 const SCEV *Size) {687 // First unify to the same type688 auto *SType = dyn_cast<IntegerType>(S->getType());689 auto *SizeType = dyn_cast<IntegerType>(Size->getType());690 if (!SType || !SizeType)691 return false;692 Type *MaxType =693 (SType->getBitWidth() >= SizeType->getBitWidth()) ? SType : SizeType;694 S = SE->getTruncateOrZeroExtend(S, MaxType);695 Size = SE->getTruncateOrZeroExtend(Size, MaxType);696 697 auto CollectUpperBound = [&](const Loop *L, Type *T) -> const SCEV * {698 if (SE->hasLoopInvariantBackedgeTakenCount(L)) {699 const SCEV *UB = SE->getBackedgeTakenCount(L);700 return SE->getTruncateOrZeroExtend(UB, T);701 }702 return nullptr;703 };704 705 auto CheckAddRecBECount = [&]() {706 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S);707 if (!AddRec || !AddRec->isAffine() || !AddRec->hasNoSignedWrap())708 return false;709 const SCEV *BECount = CollectUpperBound(AddRec->getLoop(), MaxType);710 // If the BTC cannot be computed, check the base case for S.711 if (!BECount || isa<SCEVCouldNotCompute>(BECount))712 return false;713 const SCEV *Start = AddRec->getStart();714 const SCEV *Step = AddRec->getStepRecurrence(*SE);715 const SCEV *End = AddRec->evaluateAtIteration(BECount, *SE);716 const SCEV *Diff0 = SE->getMinusSCEV(Start, Size);717 const SCEV *Diff1 = SE->getMinusSCEV(End, Size);718 719 // If the value of Step is non-negative and the AddRec is non-wrap, it720 // reaches its maximum at the last iteration. So it's enouth to check721 // whether End - Size is negative.722 if (SE->isKnownNonNegative(Step) && SE->isKnownNegative(Diff1))723 return true;724 725 // If the value of Step is non-positive and the AddRec is non-wrap, the726 // initial value is its maximum.727 if (SE->isKnownNonPositive(Step) && SE->isKnownNegative(Diff0))728 return true;729 730 // Even if we don't know the sign of Step, either Start or End must be731 // the maximum value of the AddRec since it is non-wrap.732 if (SE->isKnownNegative(Diff0) && SE->isKnownNegative(Diff1))733 return true;734 735 return false;736 };737 738 if (CheckAddRecBECount())739 return true;740 741 // Check using normal isKnownNegative742 const SCEV *LimitedBound = SE->getMinusSCEV(S, Size);743 return SE->isKnownNegative(LimitedBound);744}745 746bool llvm::validateDelinearizationResult(ScalarEvolution &SE,747 ArrayRef<const SCEV *> Sizes,748 ArrayRef<const SCEV *> Subscripts,749 const Value *Ptr) {750 for (size_t I = 1; I < Sizes.size(); ++I) {751 const SCEV *Size = Sizes[I - 1];752 const SCEV *Subscript = Subscripts[I];753 if (!isKnownNonNegative(&SE, Subscript, Ptr))754 return false;755 if (!isKnownLessThan(&SE, Subscript, Size))756 return false;757 }758 return true;759}760 761bool llvm::getIndexExpressionsFromGEP(ScalarEvolution &SE,762 const GetElementPtrInst *GEP,763 SmallVectorImpl<const SCEV *> &Subscripts,764 SmallVectorImpl<int> &Sizes) {765 assert(Subscripts.empty() && Sizes.empty() &&766 "Expected output lists to be empty on entry to this function.");767 assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");768 LLVM_DEBUG(dbgs() << "\nGEP to delinearize: " << *GEP << "\n");769 Type *Ty = nullptr;770 bool DroppedFirstDim = false;771 for (unsigned i = 1; i < GEP->getNumOperands(); i++) {772 const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));773 if (i == 1) {774 Ty = GEP->getSourceElementType();775 if (auto *Const = dyn_cast<SCEVConstant>(Expr))776 if (Const->getValue()->isZero()) {777 DroppedFirstDim = true;778 continue;779 }780 Subscripts.push_back(Expr);781 continue;782 }783 784 auto *ArrayTy = dyn_cast<ArrayType>(Ty);785 if (!ArrayTy) {786 LLVM_DEBUG(dbgs() << "GEP delinearize failed: " << *Ty787 << " is not an array type.\n");788 Subscripts.clear();789 Sizes.clear();790 return false;791 }792 793 Subscripts.push_back(Expr);794 if (!(DroppedFirstDim && i == 2))795 Sizes.push_back(ArrayTy->getNumElements());796 797 Ty = ArrayTy->getElementType();798 }799 LLVM_DEBUG({800 dbgs() << "Subscripts:\n";801 for (const SCEV *S : Subscripts)802 dbgs() << *S << "\n";803 dbgs() << "\n";804 });805 806 return !Subscripts.empty();807}808 809namespace {810 811void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,812 ScalarEvolution *SE) {813 O << "Printing analysis 'Delinearization' for function '" << F->getName()814 << "':";815 for (Instruction &Inst : instructions(F)) {816 // Only analyze loads and stores.817 if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst))818 continue;819 820 const BasicBlock *BB = Inst.getParent();821 Loop *L = LI->getLoopFor(BB);822 // Only delinearize the memory access in the innermost loop.823 // Do not analyze memory accesses outside loops.824 if (!L)825 continue;826 827 const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);828 829 const SCEVUnknown *BasePointer =830 dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));831 // Do not delinearize if we cannot find the base pointer.832 if (!BasePointer)833 break;834 AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);835 836 O << "\n";837 O << "Inst:" << Inst << "\n";838 O << "AccessFunction: " << *AccessFn << "\n";839 840 SmallVector<const SCEV *, 3> Subscripts, Sizes;841 842 auto IsDelinearizationFailed = [&]() {843 return Subscripts.size() == 0 || Sizes.size() == 0 ||844 Subscripts.size() != Sizes.size();845 };846 847 delinearize(*SE, AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));848 if (UseFixedSizeArrayHeuristic && IsDelinearizationFailed()) {849 Subscripts.clear();850 Sizes.clear();851 delinearizeFixedSizeArray(*SE, AccessFn, Subscripts, Sizes,852 SE->getElementSize(&Inst));853 }854 855 if (IsDelinearizationFailed()) {856 O << "failed to delinearize\n";857 continue;858 }859 860 O << "Base offset: " << *BasePointer << "\n";861 O << "ArrayDecl[UnknownSize]";862 int Size = Subscripts.size();863 for (int i = 0; i < Size - 1; i++)864 O << "[" << *Sizes[i] << "]";865 O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";866 867 O << "ArrayRef";868 for (int i = 0; i < Size; i++)869 O << "[" << *Subscripts[i] << "]";870 O << "\n";871 872 bool IsValid = validateDelinearizationResult(873 *SE, Sizes, Subscripts, getLoadStorePointerOperand(&Inst));874 O << "Delinearization validation: " << (IsValid ? "Succeeded" : "Failed")875 << "\n";876 }877}878 879} // end anonymous namespace880 881DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS)882 : OS(OS) {}883PreservedAnalyses DelinearizationPrinterPass::run(Function &F,884 FunctionAnalysisManager &AM) {885 printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),886 &AM.getResult<ScalarEvolutionAnalysis>(F));887 return PreservedAnalyses::all();888}889