1 //===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
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"
37 class Delinearization : public FunctionPass {
38 Delinearization(const Delinearization &); // do not implement
45 static char ID; // Pass identification, replacement for typeid
47 Delinearization() : FunctionPass(ID) {
48 initializeDelinearizationPass(*PassRegistry::getPassRegistry());
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;
55 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
57 AU.addRequired<LoopInfo>();
58 AU.addRequired<ScalarEvolution>();
61 bool Delinearization::runOnFunction(Function &F) {
63 SE = &getAnalysis<ScalarEvolution>();
64 LI = &getAnalysis<LoopInfo>();
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();
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))
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);
95 O << "AddRec: " << *AR << "\n";
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";
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";
111 for (int i = 0; i < Size; i++)
112 O << "[" << *Subscripts[i] << "]";
118 char Delinearization::ID = 0;
119 static const char delinearization_name[] = "Delinearization";
120 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
122 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
123 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
125 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }