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/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/LLVMContext.h"
  27 #include "llvm/IR/PassManager.h"
  28 #include "llvm/IR/Type.h"
  29 #include "llvm/InitializePasses.h"
  30 #include "llvm/Pass.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33
  34 using namespace llvm;
  35
  36 #define DL_NAME "delinearize"
  37 #define DEBUG_TYPE DL_NAME
  38
  39 namespace {
  40
  41 class Delinearization : public FunctionPass {
  42   Delinearization(const Delinearization &); // do not implement
  43 protected:
  44   Function *F;
  45   LoopInfo *LI;
  46   ScalarEvolution *SE;
  47
  48 public:
  49   static char ID; // Pass identification, replacement for typeid
  50
  51   Delinearization() : FunctionPass(ID) {
  52     initializeDelinearizationPass(*PassRegistry::getPassRegistry());
  53   }
  54   bool runOnFunction(Function &F) override;
  55   void getAnalysisUsage(AnalysisUsage &AU) const override;
  56   void print(raw_ostream &O, const Module *M = nullptr) const override;
  57 };
  58
  59 void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
  60                           ScalarEvolution *SE) {
  61   O << "Delinearization on function " << F->getName() << ":\n";
  62   for (Instruction &Inst : instructions(F)) {
  63     // Only analyze loads and stores.
  64     if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
  65         !isa<GetElementPtrInst>(&Inst))
  66       continue;
  67
  68     const BasicBlock *BB = Inst.getParent();
  69     // Delinearize the memory access as analyzed in all the surrounding loops.
  70     // Do not analyze memory accesses outside loops.
  71     for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
  72       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
  73
  74       const SCEVUnknown *BasePointer =
  75           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
  76       // Do not delinearize if we cannot find the base pointer.
  77       if (!BasePointer)
  78         break;
  79       AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
  80
  81       O << "\n";
  82       O << "Inst:" << Inst << "\n";
  83       O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
  84       O << "AccessFunction: " << *AccessFn << "\n";
  85
  86       SmallVector<const SCEV *, 3> Subscripts, Sizes;
  87       SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
  88       if (Subscripts.size() == 0 || Sizes.size() == 0 ||
  89           Subscripts.size() != Sizes.size()) {
  90         O << "failed to delinearize\n";
  91         continue;
  92       }
  93
  94       O << "Base offset: " << *BasePointer << "\n";
  95       O << "ArrayDecl[UnknownSize]";
  96       int Size = Subscripts.size();
  97       for (int i = 0; i < Size - 1; i++)
  98         O << "[" << *Sizes[i] << "]";
  99       O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
 100
 101       O << "ArrayRef";
 102       for (int i = 0; i < Size; i++)
 103         O << "[" << *Subscripts[i] << "]";
 104       O << "\n";
 105     }
 106   }
 107 }
 108
 109 } // end anonymous namespace
 110
 111 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
 112   AU.setPreservesAll();
 113   AU.addRequired<LoopInfoWrapperPass>();
 114   AU.addRequired<ScalarEvolutionWrapperPass>();
 115 }
 116
 117 bool Delinearization::runOnFunction(Function &F) {
 118   this->F = &F;
 119   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 120   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 121   return false;
 122 }
 123
 124 void Delinearization::print(raw_ostream &O, const Module *) const {
 125   printDelinearization(O, F, LI, SE);
 126 }
 127
 128 char Delinearization::ID = 0;
 129 static const char delinearization_name[] = "Delinearization";
 130 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
 131                       true)
 132 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 133 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
 134
 135 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
 136
 137 DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS)
 138     : OS(OS) {}
 139 PreservedAnalyses DelinearizationPrinterPass::run(Function &F,
 140                                                   FunctionAnalysisManager &AM) {
 141   printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
 142                        &AM.getResult<ScalarEvolutionAnalysis>(F));
 143   return PreservedAnalyses::all();
 144 }