160786Sps//===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===//
260786Sps//
360786Sps//                     The LLVM Compiler Infrastructure
460786Sps//
560786Sps// This file is distributed under the University of Illinois Open Source
660786Sps// License. See LICENSE.TXT for details.
789019Sps//
889019Sps//===----------------------------------------------------------------------===//
960786Sps//
1060786Sps// This implements an analysis pass that tries to delinearize all GEP
1160786Sps// instructions in all loops using the SCEV analysis functionality. This pass is
1260786Sps// only used for testing purposes: if your pass needs delinearization, please
1360786Sps// use the on-demand SCEVAddRecExpr::delinearize() function.
1460786Sps//
1560786Sps//===----------------------------------------------------------------------===//
1660786Sps
1760786Sps#define DL_NAME "delinearize"
1860786Sps#define DEBUG_TYPE DL_NAME
1960786Sps#include "llvm/IR/Constants.h"
2060786Sps#include "llvm/IR/DerivedTypes.h"
21195941Sdelphij#include "llvm/IR/Function.h"
22195941Sdelphij#include "llvm/IR/Instructions.h"
23195941Sdelphij#include "llvm/IR/LLVMContext.h"
2460786Sps#include "llvm/Pass.h"
2560786Sps#include "llvm/IR/Type.h"
26195941Sdelphij#include "llvm/Analysis/LoopInfo.h"
2760786Sps#include "llvm/Analysis/Passes.h"
2860786Sps#include "llvm/Analysis/ScalarEvolution.h"
2989019Sps#include "llvm/Analysis/ScalarEvolutionExpressions.h"
3060786Sps#include "llvm/Support/CommandLine.h"
3160786Sps#include "llvm/Support/Debug.h"
3260786Sps#include "llvm/Support/InstIterator.h"
3360786Sps#include "llvm/Support/raw_ostream.h"
3460786Sps
3560786Spsusing namespace llvm;
3660786Sps
3789019Spsnamespace {
3889019Sps
3989019Spsclass Delinearization : public FunctionPass {
4060786Sps  Delinearization(const Delinearization &); // do not implement
4160786Spsprotected:
4260786Sps  Function *F;
4360786Sps  LoopInfo *LI;
44  ScalarEvolution *SE;
45
46public:
47  static char ID; // Pass identification, replacement for typeid
48
49  Delinearization() : FunctionPass(ID) {
50    initializeDelinearizationPass(*PassRegistry::getPassRegistry());
51  }
52  virtual bool runOnFunction(Function &F);
53  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
54  virtual void print(raw_ostream &O, const Module *M = 0) const;
55};
56
57} // end anonymous namespace
58
59void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
60  AU.setPreservesAll();
61  AU.addRequired<LoopInfo>();
62  AU.addRequired<ScalarEvolution>();
63}
64
65bool Delinearization::runOnFunction(Function &F) {
66  this->F = &F;
67  SE = &getAnalysis<ScalarEvolution>();
68  LI = &getAnalysis<LoopInfo>();
69  return false;
70}
71
72static 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 NULL;
80}
81
82void 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 != NULL; L = L->getParentLoop()) {
96      const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
97      const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(AccessFn);
98
99      // Do not try to delinearize memory accesses that are not AddRecs.
100      if (!AR)
101        break;
102
103      O << "AddRec: " << *AR << "\n";
104
105      SmallVector<const SCEV *, 3> Subscripts, Sizes;
106      const SCEV *Res = AR->delinearize(*SE, Subscripts, Sizes);
107      int Size = Subscripts.size();
108      if (Res == AR || Size == 0) {
109        O << "failed to delinearize\n";
110        continue;
111      }
112      O << "Base offset: " << *Res << "\n";
113      O << "ArrayDecl[UnknownSize]";
114      for (int i = 0; i < Size - 1; i++)
115        O << "[" << *Sizes[i] << "]";
116      O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
117
118      O << "ArrayRef";
119      for (int i = 0; i < Size; i++)
120        O << "[" << *Subscripts[i] << "]";
121      O << "\n";
122    }
123  }
124}
125
126char Delinearization::ID = 0;
127static const char delinearization_name[] = "Delinearization";
128INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
129                      true)
130INITIALIZE_PASS_DEPENDENCY(LoopInfo)
131INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
132
133FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
134