llvm/lib/Analysis/Delinearization.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-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 #include "llvm/Analysis/Delinearization.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/Analysis/Passes.h"
  19 #include "llvm/Analysis/ScalarEvolution.h"
  20 #include "llvm/Analysis/ScalarEvolutionDivision.h"
  21 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DerivedTypes.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/IR/InstIterator.h"
  26 #include "llvm/IR/Instructions.h"
  27 #include "llvm/IR/PassManager.h"
  28 #include "llvm/InitializePasses.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/raw_ostream.h"
  32
  33 using namespace llvm;
  34
  35 #define DL_NAME "delinearize"
  36 #define DEBUG_TYPE DL_NAME
  37
  38 // Return true when S contains at least an undef value.
  39 static inline bool containsUndefs(const SCEV *S) {
  40   return SCEVExprContains(S, [](const SCEV *S) {
  41     if (const auto *SU = dyn_cast<SCEVUnknown>(S))
  42       return isa<UndefValue>(SU->getValue());
  43     return false;
  44   });
  45 }
  46
  47 namespace {
  48
  49 // Collect all steps of SCEV expressions.
  50 struct SCEVCollectStrides {
  51   ScalarEvolution &SE;
  52   SmallVectorImpl<const SCEV *> &Strides;
  53
  54   SCEVCollectStrides(ScalarEvolution &SE, SmallVectorImpl<const SCEV *> &S)
  55       : SE(SE), Strides(S) {}
  56
  57   bool follow(const SCEV *S) {
  58     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
  59       Strides.push_back(AR->getStepRecurrence(SE));
  60     return true;
  61   }
  62
  63   bool isDone() const { return false; }
  64 };
  65
  66 // Collect all SCEVUnknown and SCEVMulExpr expressions.
  67 struct SCEVCollectTerms {
  68   SmallVectorImpl<const SCEV *> &Terms;
  69
  70   SCEVCollectTerms(SmallVectorImpl<const SCEV *> &T) : Terms(T) {}
  71
  72   bool follow(const SCEV *S) {
  73     if (isa<SCEVUnknown>(S) || isa<SCEVMulExpr>(S) ||
  74         isa<SCEVSignExtendExpr>(S)) {
  75       if (!containsUndefs(S))
  76         Terms.push_back(S);
  77
  78       // Stop recursion: once we collected a term, do not walk its operands.
  79       return false;
  80     }
  81
  82     // Keep looking.
  83     return true;
  84   }
  85
  86   bool isDone() const { return false; }
  87 };
  88
  89 // Check if a SCEV contains an AddRecExpr.
  90 struct SCEVHasAddRec {
  91   bool &ContainsAddRec;
  92
  93   SCEVHasAddRec(bool &ContainsAddRec) : ContainsAddRec(ContainsAddRec) {
  94     ContainsAddRec = false;
  95   }
  96
  97   bool follow(const SCEV *S) {
  98     if (isa<SCEVAddRecExpr>(S)) {
  99       ContainsAddRec = true;
 100
 101       // Stop recursion: once we collected a term, do not walk its operands.
 102       return false;
 103     }
 104
 105     // Keep looking.
 106     return true;
 107   }
 108
 109   bool isDone() const { return false; }
 110 };
 111
 112 // Find factors that are multiplied with an expression that (possibly as a
 113 // subexpression) contains an AddRecExpr. In the expression:
 114 //
 115 //  8 * (100 +  %p * %q * (%a + {0, +, 1}_loop))
 116 //
 117 // "%p * %q" are factors multiplied by the expression "(%a + {0, +, 1}_loop)"
 118 // that contains the AddRec {0, +, 1}_loop. %p * %q are likely to be array size
 119 // parameters as they form a product with an induction variable.
 120 //
 121 // This collector expects all array size parameters to be in the same MulExpr.
 122 // It might be necessary to later add support for collecting parameters that are
 123 // spread over different nested MulExpr.
 124 struct SCEVCollectAddRecMultiplies {
 125   SmallVectorImpl<const SCEV *> &Terms;
 126   ScalarEvolution &SE;
 127
 128   SCEVCollectAddRecMultiplies(SmallVectorImpl<const SCEV *> &T,
 129                               ScalarEvolution &SE)
 130       : Terms(T), SE(SE) {}
 131
 132   bool follow(const SCEV *S) {
 133     if (auto *Mul = dyn_cast<SCEVMulExpr>(S)) {
 134       bool HasAddRec = false;
 135       SmallVector<const SCEV *, 0> Operands;
 136       for (const auto *Op : Mul->operands()) {
 137         const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(Op);
 138         if (Unknown && !isa<CallInst>(Unknown->getValue())) {
 139           Operands.push_back(Op);
 140         } else if (Unknown) {
 141           HasAddRec = true;
 142         } else {
 143           bool ContainsAddRec = false;
 144           SCEVHasAddRec ContiansAddRec(ContainsAddRec);
 145           visitAll(Op, ContiansAddRec);
 146           HasAddRec |= ContainsAddRec;
 147         }
 148       }
 149       if (Operands.size() == 0)
 150         return true;
 151
 152       if (!HasAddRec)
 153         return false;
 154
 155       Terms.push_back(SE.getMulExpr(Operands));
 156       // Stop recursion: once we collected a term, do not walk its operands.
 157       return false;
 158     }
 159
 160     // Keep looking.
 161     return true;
 162   }
 163
 164   bool isDone() const { return false; }
 165 };
 166
 167 } // end anonymous namespace
 168
 169 /// Find parametric terms in this SCEVAddRecExpr. We first for parameters in
 170 /// two places:
 171 ///   1) The strides of AddRec expressions.
 172 ///   2) Unknowns that are multiplied with AddRec expressions.
 173 void llvm::collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr,
 174                                   SmallVectorImpl<const SCEV *> &Terms) {
 175   SmallVector<const SCEV *, 4> Strides;
 176   SCEVCollectStrides StrideCollector(SE, Strides);
 177   visitAll(Expr, StrideCollector);
 178
 179   LLVM_DEBUG({
 180     dbgs() << "Strides:\n";
 181     for (const SCEV *S : Strides)
 182       dbgs() << *S << "\n";
 183   });
 184
 185   for (const SCEV *S : Strides) {
 186     SCEVCollectTerms TermCollector(Terms);
 187     visitAll(S, TermCollector);
 188   }
 189
 190   LLVM_DEBUG({
 191     dbgs() << "Terms:\n";
 192     for (const SCEV *T : Terms)
 193       dbgs() << *T << "\n";
 194   });
 195
 196   SCEVCollectAddRecMultiplies MulCollector(Terms, SE);
 197   visitAll(Expr, MulCollector);
 198 }
 199
 200 static bool findArrayDimensionsRec(ScalarEvolution &SE,
 201                                    SmallVectorImpl<const SCEV *> &Terms,
 202                                    SmallVectorImpl<const SCEV *> &Sizes) {
 203   int Last = Terms.size() - 1;
 204   const SCEV *Step = Terms[Last];
 205
 206   // End of recursion.
 207   if (Last == 0) {
 208     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Step)) {
 209       SmallVector<const SCEV *, 2> Qs;
 210       for (const SCEV *Op : M->operands())
 211         if (!isa<SCEVConstant>(Op))
 212           Qs.push_back(Op);
 213
 214       Step = SE.getMulExpr(Qs);
 215     }
 216
 217     Sizes.push_back(Step);
 218     return true;
 219   }
 220
 221   for (const SCEV *&Term : Terms) {
 222     // Normalize the terms before the next call to findArrayDimensionsRec.
 223     const SCEV *Q, *R;
 224     SCEVDivision::divide(SE, Term, Step, &Q, &R);
 225
 226     // Bail out when GCD does not evenly divide one of the terms.
 227     if (!R->isZero())
 228       return false;
 229
 230     Term = Q;
 231   }
 232
 233   // Remove all SCEVConstants.
 234   erase_if(Terms, [](const SCEV *E) { return isa<SCEVConstant>(E); });
 235
 236   if (Terms.size() > 0)
 237     if (!findArrayDimensionsRec(SE, Terms, Sizes))
 238       return false;
 239
 240   Sizes.push_back(Step);
 241   return true;
 242 }
 243
 244 // Returns true when one of the SCEVs of Terms contains a SCEVUnknown parameter.
 245 static inline bool containsParameters(SmallVectorImpl<const SCEV *> &Terms) {
 246   for (const SCEV *T : Terms)
 247     if (SCEVExprContains(T, [](const SCEV *S) { return isa<SCEVUnknown>(S); }))
 248       return true;
 249
 250   return false;
 251 }
 252
 253 // Return the number of product terms in S.
 254 static inline int numberOfTerms(const SCEV *S) {
 255   if (const SCEVMulExpr *Expr = dyn_cast<SCEVMulExpr>(S))
 256     return Expr->getNumOperands();
 257   return 1;
 258 }
 259
 260 static const SCEV *removeConstantFactors(ScalarEvolution &SE, const SCEV *T) {
 261   if (isa<SCEVConstant>(T))
 262     return nullptr;
 263
 264   if (isa<SCEVUnknown>(T))
 265     return T;
 266
 267   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(T)) {
 268     SmallVector<const SCEV *, 2> Factors;
 269     for (const SCEV *Op : M->operands())
 270       if (!isa<SCEVConstant>(Op))
 271         Factors.push_back(Op);
 272
 273     return SE.getMulExpr(Factors);
 274   }
 275
 276   return T;
 277 }
 278
 279 void llvm::findArrayDimensions(ScalarEvolution &SE,
 280                                SmallVectorImpl<const SCEV *> &Terms,
 281                                SmallVectorImpl<const SCEV *> &Sizes,
 282                                const SCEV *ElementSize) {
 283   if (Terms.size() < 1 || !ElementSize)
 284     return;
 285
 286   // Early return when Terms do not contain parameters: we do not delinearize
 287   // non parametric SCEVs.
 288   if (!containsParameters(Terms))
 289     return;
 290
 291   LLVM_DEBUG({
 292     dbgs() << "Terms:\n";
 293     for (const SCEV *T : Terms)
 294       dbgs() << *T << "\n";
 295   });
 296
 297   // Remove duplicates.
 298   array_pod_sort(Terms.begin(), Terms.end());
 299   Terms.erase(std::unique(Terms.begin(), Terms.end()), Terms.end());
 300
 301   // Put larger terms first.
 302   llvm::sort(Terms, [](const SCEV *LHS, const SCEV *RHS) {
 303     return numberOfTerms(LHS) > numberOfTerms(RHS);
 304   });
 305
 306   // Try to divide all terms by the element size. If term is not divisible by
 307   // element size, proceed with the original term.
 308   for (const SCEV *&Term : Terms) {
 309     const SCEV *Q, *R;
 310     SCEVDivision::divide(SE, Term, ElementSize, &Q, &R);
 311     if (!Q->isZero())
 312       Term = Q;
 313   }
 314
 315   SmallVector<const SCEV *, 4> NewTerms;
 316
 317   // Remove constant factors.
 318   for (const SCEV *T : Terms)
 319     if (const SCEV *NewT = removeConstantFactors(SE, T))
 320       NewTerms.push_back(NewT);
 321
 322   LLVM_DEBUG({
 323     dbgs() << "Terms after sorting:\n";
 324     for (const SCEV *T : NewTerms)
 325       dbgs() << *T << "\n";
 326   });
 327
 328   if (NewTerms.empty() || !findArrayDimensionsRec(SE, NewTerms, Sizes)) {
 329     Sizes.clear();
 330     return;
 331   }
 332
 333   // The last element to be pushed into Sizes is the size of an element.
 334   Sizes.push_back(ElementSize);
 335
 336   LLVM_DEBUG({
 337     dbgs() << "Sizes:\n";
 338     for (const SCEV *S : Sizes)
 339       dbgs() << *S << "\n";
 340   });
 341 }
 342
 343 void llvm::computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr,
 344                                   SmallVectorImpl<const SCEV *> &Subscripts,
 345                                   SmallVectorImpl<const SCEV *> &Sizes) {
 346   // Early exit in case this SCEV is not an affine multivariate function.
 347   if (Sizes.empty())
 348     return;
 349
 350   if (auto *AR = dyn_cast<SCEVAddRecExpr>(Expr))
 351     if (!AR->isAffine())
 352       return;
 353
 354   const SCEV *Res = Expr;
 355   int Last = Sizes.size() - 1;
 356   for (int i = Last; i >= 0; i--) {
 357     const SCEV *Q, *R;
 358     SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R);
 359
 360     LLVM_DEBUG({
 361       dbgs() << "Res: " << *Res << "\n";
 362       dbgs() << "Sizes[i]: " << *Sizes[i] << "\n";
 363       dbgs() << "Res divided by Sizes[i]:\n";
 364       dbgs() << "Quotient: " << *Q << "\n";
 365       dbgs() << "Remainder: " << *R << "\n";
 366     });
 367
 368     Res = Q;
 369
 370     // Do not record the last subscript corresponding to the size of elements in
 371     // the array.
 372     if (i == Last) {
 373
 374       // Bail out if the byte offset is non-zero.
 375       if (!R->isZero()) {
 376         Subscripts.clear();
 377         Sizes.clear();
 378         return;
 379       }
 380
 381       continue;
 382     }
 383
 384     // Record the access function for the current subscript.
 385     Subscripts.push_back(R);
 386   }
 387
 388   // Also push in last position the remainder of the last division: it will be
 389   // the access function of the innermost dimension.
 390   Subscripts.push_back(Res);
 391
 392   std::reverse(Subscripts.begin(), Subscripts.end());
 393
 394   LLVM_DEBUG({
 395     dbgs() << "Subscripts:\n";
 396     for (const SCEV *S : Subscripts)
 397       dbgs() << *S << "\n";
 398   });
 399 }
 400
 401 /// Splits the SCEV into two vectors of SCEVs representing the subscripts and
 402 /// sizes of an array access. Returns the remainder of the delinearization that
 403 /// is the offset start of the array.  The SCEV->delinearize algorithm computes
 404 /// the multiples of SCEV coefficients: that is a pattern matching of sub
 405 /// expressions in the stride and base of a SCEV corresponding to the
 406 /// computation of a GCD (greatest common divisor) of base and stride.  When
 407 /// SCEV->delinearize fails, it returns the SCEV unchanged.
 408 ///
 409 /// For example: when analyzing the memory access A[i][j][k] in this loop nest
 410 ///
 411 ///  void foo(long n, long m, long o, double A[n][m][o]) {
 412 ///
 413 ///    for (long i = 0; i < n; i++)
 414 ///      for (long j = 0; j < m; j++)
 415 ///        for (long k = 0; k < o; k++)
 416 ///          A[i][j][k] = 1.0;
 417 ///  }
 418 ///
 419 /// the delinearization input is the following AddRec SCEV:
 420 ///
 421 ///  AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 422 ///
 423 /// From this SCEV, we are able to say that the base offset of the access is %A
 424 /// because it appears as an offset that does not divide any of the strides in
 425 /// the loops:
 426 ///
 427 ///  CHECK: Base offset: %A
 428 ///
 429 /// and then SCEV->delinearize determines the size of some of the dimensions of
 430 /// the array as these are the multiples by which the strides are happening:
 431 ///
 432 ///  CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double)
 433 ///  bytes.
 434 ///
 435 /// Note that the outermost dimension remains of UnknownSize because there are
 436 /// no strides that would help identifying the size of the last dimension: when
 437 /// the array has been statically allocated, one could compute the size of that
 438 /// dimension by dividing the overall size of the array by the size of the known
 439 /// dimensions: %m * %o * 8.
 440 ///
 441 /// Finally delinearize provides the access functions for the array reference
 442 /// that does correspond to A[i][j][k] of the above C testcase:
 443 ///
 444 ///  CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
 445 ///
 446 /// The testcases are checking the output of a function pass:
 447 /// DelinearizationPass that walks through all loads and stores of a function
 448 /// asking for the SCEV of the memory access with respect to all enclosing
 449 /// loops, calling SCEV->delinearize on that and printing the results.
 450 void llvm::delinearize(ScalarEvolution &SE, const SCEV *Expr,
 451                        SmallVectorImpl<const SCEV *> &Subscripts,
 452                        SmallVectorImpl<const SCEV *> &Sizes,
 453                        const SCEV *ElementSize) {
 454   // First step: collect parametric terms.
 455   SmallVector<const SCEV *, 4> Terms;
 456   collectParametricTerms(SE, Expr, Terms);
 457
 458   if (Terms.empty())
 459     return;
 460
 461   // Second step: find subscript sizes.
 462   findArrayDimensions(SE, Terms, Sizes, ElementSize);
 463
 464   if (Sizes.empty())
 465     return;
 466
 467   // Third step: compute the access functions for each subscript.
 468   computeAccessFunctions(SE, Expr, Subscripts, Sizes);
 469
 470   if (Subscripts.empty())
 471     return;
 472
 473   LLVM_DEBUG({
 474     dbgs() << "succeeded to delinearize " << *Expr << "\n";
 475     dbgs() << "ArrayDecl[UnknownSize]";
 476     for (const SCEV *S : Sizes)
 477       dbgs() << "[" << *S << "]";
 478
 479     dbgs() << "\nArrayRef";
 480     for (const SCEV *S : Subscripts)
 481       dbgs() << "[" << *S << "]";
 482     dbgs() << "\n";
 483   });
 484 }
 485
 486 bool llvm::getIndexExpressionsFromGEP(ScalarEvolution &SE,
 487                                       const GetElementPtrInst *GEP,
 488                                       SmallVectorImpl<const SCEV *> &Subscripts,
 489                                       SmallVectorImpl<int> &Sizes) {
 490   assert(Subscripts.empty() && Sizes.empty() &&
 491          "Expected output lists to be empty on entry to this function.");
 492   assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
 493   Type *Ty = nullptr;
 494   bool DroppedFirstDim = false;
 495   for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
 496     const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
 497     if (i == 1) {
 498       Ty = GEP->getSourceElementType();
 499       if (auto *Const = dyn_cast<SCEVConstant>(Expr))
 500         if (Const->getValue()->isZero()) {
 501           DroppedFirstDim = true;
 502           continue;
 503         }
 504       Subscripts.push_back(Expr);
 505       continue;
 506     }
 507
 508     auto *ArrayTy = dyn_cast<ArrayType>(Ty);
 509     if (!ArrayTy) {
 510       Subscripts.clear();
 511       Sizes.clear();
 512       return false;
 513     }
 514
 515     Subscripts.push_back(Expr);
 516     if (!(DroppedFirstDim && i == 2))
 517       Sizes.push_back(ArrayTy->getNumElements());
 518
 519     Ty = ArrayTy->getElementType();
 520   }
 521   return !Subscripts.empty();
 522 }
 523
 524 bool llvm::tryDelinearizeFixedSizeImpl(
 525     ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn,
 526     SmallVectorImpl<const SCEV *> &Subscripts, SmallVectorImpl<int> &Sizes) {
 527   Value *SrcPtr = getLoadStorePointerOperand(Inst);
 528
 529   // Check the simple case where the array dimensions are fixed size.
 530   auto *SrcGEP = dyn_cast<GetElementPtrInst>(SrcPtr);
 531   if (!SrcGEP)
 532     return false;
 533
 534   getIndexExpressionsFromGEP(*SE, SrcGEP, Subscripts, Sizes);
 535
 536   // Check that the two size arrays are non-empty and equal in length and
 537   // value.
 538   // TODO: it would be better to let the caller to clear Subscripts, similar
 539   // to how we handle Sizes.
 540   if (Sizes.empty() || Subscripts.size() <= 1) {
 541     Subscripts.clear();
 542     return false;
 543   }
 544
 545   // Check that for identical base pointers we do not miss index offsets
 546   // that have been added before this GEP is applied.
 547   Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts();
 548   const SCEVUnknown *SrcBase =
 549       dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
 550   if (!SrcBase || SrcBasePtr != SrcBase->getValue()) {
 551     Subscripts.clear();
 552     return false;
 553   }
 554
 555   assert(Subscripts.size() == Sizes.size() + 1 &&
 556          "Expected equal number of entries in the list of size and "
 557          "subscript.");
 558
 559   return true;
 560 }
 561
 562 namespace {
 563
 564 class Delinearization : public FunctionPass {
 565   Delinearization(const Delinearization &); // do not implement
 566 protected:
 567   Function *F;
 568   LoopInfo *LI;
 569   ScalarEvolution *SE;
 570
 571 public:
 572   static char ID; // Pass identification, replacement for typeid
 573
 574   Delinearization() : FunctionPass(ID) {
 575     initializeDelinearizationPass(*PassRegistry::getPassRegistry());
 576   }
 577   bool runOnFunction(Function &F) override;
 578   void getAnalysisUsage(AnalysisUsage &AU) const override;
 579   void print(raw_ostream &O, const Module *M = nullptr) const override;
 580 };
 581
 582 void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
 583                           ScalarEvolution *SE) {
 584   O << "Delinearization on function " << F->getName() << ":\n";
 585   for (Instruction &Inst : instructions(F)) {
 586     // Only analyze loads and stores.
 587     if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
 588         !isa<GetElementPtrInst>(&Inst))
 589       continue;
 590
 591     const BasicBlock *BB = Inst.getParent();
 592     // Delinearize the memory access as analyzed in all the surrounding loops.
 593     // Do not analyze memory accesses outside loops.
 594     for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
 595       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
 596
 597       const SCEVUnknown *BasePointer =
 598           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
 599       // Do not delinearize if we cannot find the base pointer.
 600       if (!BasePointer)
 601         break;
 602       AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
 603
 604       O << "\n";
 605       O << "Inst:" << Inst << "\n";
 606       O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
 607       O << "AccessFunction: " << *AccessFn << "\n";
 608
 609       SmallVector<const SCEV *, 3> Subscripts, Sizes;
 610       delinearize(*SE, AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
 611       if (Subscripts.size() == 0 || Sizes.size() == 0 ||
 612           Subscripts.size() != Sizes.size()) {
 613         O << "failed to delinearize\n";
 614         continue;
 615       }
 616
 617       O << "Base offset: " << *BasePointer << "\n";
 618       O << "ArrayDecl[UnknownSize]";
 619       int Size = Subscripts.size();
 620       for (int i = 0; i < Size - 1; i++)
 621         O << "[" << *Sizes[i] << "]";
 622       O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
 623
 624       O << "ArrayRef";
 625       for (int i = 0; i < Size; i++)
 626         O << "[" << *Subscripts[i] << "]";
 627       O << "\n";
 628     }
 629   }
 630 }
 631
 632 } // end anonymous namespace
 633
 634 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
 635   AU.setPreservesAll();
 636   AU.addRequired<LoopInfoWrapperPass>();
 637   AU.addRequired<ScalarEvolutionWrapperPass>();
 638 }
 639
 640 bool Delinearization::runOnFunction(Function &F) {
 641   this->F = &F;
 642   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 643   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 644   return false;
 645 }
 646
 647 void Delinearization::print(raw_ostream &O, const Module *) const {
 648   printDelinearization(O, F, LI, SE);
 649 }
 650
 651 char Delinearization::ID = 0;
 652 static const char delinearization_name[] = "Delinearization";
 653 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
 654                       true)
 655 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 656 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
 657
 658 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
 659
 660 DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS)
 661     : OS(OS) {}
 662 PreservedAnalyses DelinearizationPrinterPass::run(Function &F,
 663                                                   FunctionAnalysisManager &AM) {
 664   printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
 665                        &AM.getResult<ScalarEvolutionAnalysis>(F));
 666   return PreservedAnalyses::all();
 667 }