Home | History | Annotate | Download | only in Analysis 
      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; }
    141