contrib/llvm/lib/Analysis/Delinearization.cpp

   1 //===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements an analysis pass that tries to delinearize all GEP
  11 // instructions in all loops using the SCEV analysis functionality. This pass is
  12 // only used for testing purposes: if your pass needs delinearization, please
  13 // use the on-demand SCEVAddRecExpr::delinearize() function.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  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/Type.h"
  28 #include "llvm/Pass.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/raw_ostream.h"
  31
  32 using namespace llvm;
  33
  34 #define DL_NAME "delinearize"
  35 #define DEBUG_TYPE DL_NAME
  36
  37 namespace {
  38
  39 class Delinearization : public FunctionPass {
  40   Delinearization(const Delinearization &); // do not implement
  41 protected:
  42   Function *F;
  43   LoopInfo *LI;
  44   ScalarEvolution *SE;
  45
  46 public:
  47   static char ID; // Pass identification, replacement for typeid
  48
  49   Delinearization() : FunctionPass(ID) {
  50     initializeDelinearizationPass(*PassRegistry::getPassRegistry());
  51   }
  52   bool runOnFunction(Function &F) override;
  53   void getAnalysisUsage(AnalysisUsage &AU) const override;
  54   void print(raw_ostream &O, const Module *M = nullptr) const override;
  55 };
  56
  57 } // end anonymous namespace
  58
  59 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
  60   AU.setPreservesAll();
  61   AU.addRequired<LoopInfoWrapperPass>();
  62   AU.addRequired<ScalarEvolutionWrapperPass>();
  63 }
  64
  65 bool Delinearization::runOnFunction(Function &F) {
  66   this->F = &F;
  67   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
  68   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  69   return false;
  70 }
  71
  72 static Value *getPointerOperand(Instruction &Inst) {
  73   if (LoadInst *Load = dyn_cast<LoadInst>(&Inst))
  74     return Load->getPointerOperand();
  75   else if (StoreInst *Store = dyn_cast<StoreInst>(&Inst))
  76     return Store->getPointerOperand();
  77   else if (GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(&Inst))
  78     return Gep->getPointerOperand();
  79   return nullptr;
  80 }
  81
  82 void Delinearization::print(raw_ostream &O, const Module *) const {
  83   O << "Delinearization on function " << F->getName() << ":\n";
  84   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
  85     Instruction *Inst = &(*I);
  86
  87     // Only analyze loads and stores.
  88     if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) &&
  89         !isa<GetElementPtrInst>(Inst))
  90       continue;
  91
  92     const BasicBlock *BB = Inst->getParent();
  93     // Delinearize the memory access as analyzed in all the surrounding loops.
  94     // Do not analyze memory accesses outside loops.
  95     for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
  96       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
  97
  98       const SCEVUnknown *BasePointer =
  99           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
 100       // Do not delinearize if we cannot find the base pointer.
 101       if (!BasePointer)
 102         break;
 103       AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
 104
 105       O << "\n";
 106       O << "Inst:" << *Inst << "\n";
 107       O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
 108       O << "AccessFunction: " << *AccessFn << "\n";
 109
 110       SmallVector<const SCEV *, 3> Subscripts, Sizes;
 111       SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(Inst));
 112       if (Subscripts.size() == 0 || Sizes.size() == 0 ||
 113           Subscripts.size() != Sizes.size()) {
 114         O << "failed to delinearize\n";
 115         continue;
 116       }
 117
 118       O << "Base offset: " << *BasePointer << "\n";
 119       O << "ArrayDecl[UnknownSize]";
 120       int Size = Subscripts.size();
 121       for (int i = 0; i < Size - 1; i++)
 122         O << "[" << *Sizes[i] << "]";
 123       O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
 124
 125       O << "ArrayRef";
 126       for (int i = 0; i < Size; i++)
 127         O << "[" << *Subscripts[i] << "]";
 128       O << "\n";
 129     }
 130   }
 131 }
 132
 133 char Delinearization::ID = 0;
 134 static const char delinearization_name[] = "Delinearization";
 135 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
 136                       true)
 137 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 138 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
 139
 140 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }