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