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