LCOV - code coverage report
Current view: top level - lib/Analysis - Delinearization.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 54 55 98.2 %
Date: 2017-09-14 15:23:50 Functions: 7 9 77.8 %
Legend: Lines: hit not hit

          Line data    Source code
       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          32 : 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          32 :   Delinearization() : FunctionPass(ID) {
      50          16 :     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          16 : void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
      60          32 :   AU.setPreservesAll();
      61          16 :   AU.addRequired<LoopInfoWrapperPass>();
      62          16 :   AU.addRequired<ScalarEvolutionWrapperPass>();
      63          16 : }
      64             : 
      65          16 : bool Delinearization::runOnFunction(Function &F) {
      66          16 :   this->F = &F;
      67          32 :   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
      68          32 :   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
      69          16 :   return false;
      70             : }
      71             : 
      72         165 : static Value *getPointerOperand(Instruction &Inst) {
      73         165 :   if (LoadInst *Load = dyn_cast<LoadInst>(&Inst))
      74             :     return Load->getPointerOperand();
      75         134 :   else if (StoreInst *Store = dyn_cast<StoreInst>(&Inst))
      76             :     return Store->getPointerOperand();
      77          61 :   else if (GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(&Inst))
      78             :     return Gep->getPointerOperand();
      79             :   return nullptr;
      80             : }
      81             : 
      82          16 : void Delinearization::print(raw_ostream &O, const Module *) const {
      83          16 :   O << "Delinearization on function " << F->getName() << ":\n";
      84         549 :   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
      85         517 :     Instruction *Inst = &(*I);
      86             : 
      87             :     // Only analyze loads and stores.
      88        2381 :     if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) &&
      89         451 :         !isa<GetElementPtrInst>(Inst))
      90         412 :       continue;
      91             : 
      92         105 :     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         375 :     for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
      96         165 :       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
      97             : 
      98             :       const SCEVUnknown *BasePointer =
      99         330 :           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
     100             :       // Do not delinearize if we cannot find the base pointer.
     101         165 :       if (!BasePointer)
     102             :         break;
     103         165 :       AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
     104             : 
     105         165 :       O << "\n";
     106         330 :       O << "Inst:" << *Inst << "\n";
     107         330 :       O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
     108         330 :       O << "AccessFunction: " << *AccessFn << "\n";
     109             : 
     110         412 :       SmallVector<const SCEV *, 3> Subscripts, Sizes;
     111         165 :       SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(Inst));
     112         371 :       if (Subscripts.size() == 0 || Sizes.size() == 0 ||
     113          82 :           Subscripts.size() != Sizes.size()) {
     114         124 :         O << "failed to delinearize\n";
     115         124 :         continue;
     116             :       }
     117             : 
     118          82 :       O << "Base offset: " << *BasePointer << "\n";
     119          41 :       O << "ArrayDecl[UnknownSize]";
     120          41 :       int Size = Subscripts.size();
     121         196 :       for (int i = 0; i < Size - 1; i++)
     122         171 :         O << "[" << *Sizes[i] << "]";
     123         123 :       O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
     124             : 
     125          41 :       O << "ArrayRef";
     126         139 :       for (int i = 0; i < Size; i++)
     127         294 :         O << "[" << *Subscripts[i] << "]";
     128          41 :       O << "\n";
     129             :     }
     130             :   }
     131          16 : }
     132             : 
     133             : char Delinearization::ID = 0;
     134             : static const char delinearization_name[] = "Delinearization";
     135        9158 : INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
     136             :                       true)
     137        9158 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
     138       45838 : INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
     139             : 
     140           0 : FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }

Generated by: LCOV version 1.13