Delinearization.cpp revision 5230ad61fd35d3006e7764c3152d28e2e68c288f 
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
35using namespace llvm;
36
37class Delinearization : public FunctionPass {
38  Delinearization(const Delinearization &); // do not implement
39protected:
40  Function *F;
41  LoopInfo *LI;
42  ScalarEvolution *SE;
43
44public:
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
55void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
56  AU.setPreservesAll();
57  AU.addRequired<LoopInfo>();
58  AU.addRequired<ScalarEvolution>();
59}
60
61bool Delinearization::runOnFunction(Function &F) {
62  this->F = &F;
63  SE = &getAnalysis<ScalarEvolution>();
64  LI = &getAnalysis<LoopInfo>();
65  return false;
66}
67
68static 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
78void 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
118char Delinearization::ID = 0;
119static const char delinearization_name[] = "Delinearization";
120INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
121                      true)
122INITIALIZE_PASS_DEPENDENCY(LoopInfo)
123INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
124
125FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
126