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 #define DL_NAME "delinearize"
  18 #define DEBUG_TYPE DL_NAME
  19 #include "llvm/IR/Constants.h"
  20 #include "llvm/IR/DerivedTypes.h"
  21 #include "llvm/IR/Function.h"
  22 #include "llvm/IR/Instructions.h"
  23 #include "llvm/IR/LLVMContext.h"
  24 #include "llvm/Pass.h"
  25 #include "llvm/IR/Type.h"
  26 #include "llvm/Analysis/LoopInfo.h"
  27 #include "llvm/Analysis/Passes.h"
  28 #include "llvm/Analysis/ScalarEvolution.h"
  29 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/InstIterator.h"
  33 #include "llvm/Support/raw_ostream.h"
  34
  35 using namespace llvm;
  36
  37 class Delinearization : public FunctionPass {
  38   Delinearization(const Delinearization &); // do not implement
  39 protected:
  40   Function *F;
  41   LoopInfo *LI;
  42   ScalarEvolution *SE;
  43
  44 public:
  45   static char ID; // Pass identification, replacement for typeid
  46
  47   Delinearization() : FunctionPass(ID) {
  48     initializeDelinearizationPass(*PassRegistry::getPassRegistry());
  49   }
  50   virtual bool runOnFunction(Function &F);
  51   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  52   virtual void print(raw_ostream &O, const Module *M = 0) const;
  53 };
  54
  55 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
  56   AU.setPreservesAll();
  57   AU.addRequired<LoopInfo>();
  58   AU.addRequired<ScalarEvolution>();
  59 }
  60
  61 bool Delinearization::runOnFunction(Function &F) {
  62   this->F = &F;
  63   SE = &getAnalysis<ScalarEvolution>();
  64   LI = &getAnalysis<LoopInfo>();
  65   return false;
  66 }
  67
  68 static Value *getPointerOperand(Instruction &Inst) {
  69   if (LoadInst *Load = dyn_cast<LoadInst>(&Inst))
  70     return Load->getPointerOperand();
  71   else if (StoreInst *Store = dyn_cast<StoreInst>(&Inst))
  72     return Store->getPointerOperand();
  73   else if (GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(&Inst))
  74     return Gep->getPointerOperand();
  75   return NULL;
  76 }
  77
  78 void Delinearization::print(raw_ostream &O, const Module *) const {
  79   O << "Delinearization on function " << F->getName() << ":\n";
  80   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
  81     Instruction *Inst = &(*I);
  82     if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) &&
  83         !isa<GetElementPtrInst>(Inst))
  84       continue;
  85
  86     const BasicBlock *BB = Inst->getParent();
  87     // Delinearize the memory access as analyzed in all the surrounding loops.
  88     // Do not analyze memory accesses outside loops.
  89     for (Loop *L = LI->getLoopFor(BB); L != NULL; L = L->getParentLoop()) {
  90       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
  91       const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(AccessFn);
  92       if (!AR)
  93         break;
  94
  95       O << "AddRec: " << *AR << "\n";
  96
  97       SmallVector<const SCEV *, 3> Subscripts, Sizes;
  98       const SCEV *Res = AR->delinearize(*SE, Subscripts, Sizes);
  99       int Size = Subscripts.size();
 100       if (Res == AR || Size == 0) {
 101         O << "failed to delinearize\n";
 102         continue;
 103       }
 104       O << "Base offset: " << *Res << "\n";
 105       O << "ArrayDecl[UnknownSize]";
 106       for (int i = 0; i < Size - 1; i++)
 107         O << "[" << *Sizes[i] << "]";
 108       O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
 109
 110       O << "ArrayRef";
 111       for (int i = 0; i < Size; i++)
 112         O << "[" << *Subscripts[i] << "]";
 113       O << "\n";
 114     }
 115   }
 116 }
 117
 118 char Delinearization::ID = 0;
 119 static const char delinearization_name[] = "Delinearization";
 120 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
 121                       true)
 122 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 123 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
 124
 125 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }