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/IR/Constants.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/Passes.h"
20 #include "llvm/Analysis/ScalarEvolution.h"
21 #include "llvm/Analysis/ScalarEvolutionExpressions.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/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
32
33 using namespace llvm;
34
35 #define DL_NAME "delinearize"
36 #define DEBUG_TYPE DL_NAME
37
38 namespace {
39
40 class Delinearization : public FunctionPass {
41 Delinearization(const Delinearization &); // do not implement
42 protected:
43 Function *F;
44 LoopInfo *LI;
45 ScalarEvolution *SE;
46
47 public:
48 static char ID; // Pass identification, replacement for typeid
49
Delinearization()50 Delinearization() : FunctionPass(ID) {
51 initializeDelinearizationPass(*PassRegistry::getPassRegistry());
52 }
53 bool runOnFunction(Function &F) override;
54 void getAnalysisUsage(AnalysisUsage &AU) const override;
55 void print(raw_ostream &O, const Module *M = nullptr) const override;
56 };
57
58 } // end anonymous namespace
59
getAnalysisUsage(AnalysisUsage & AU) const60 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
61 AU.setPreservesAll();
62 AU.addRequired<LoopInfo>();
63 AU.addRequired<ScalarEvolution>();
64 }
65
runOnFunction(Function & F)66 bool Delinearization::runOnFunction(Function &F) {
67 this->F = &F;
68 SE = &getAnalysis<ScalarEvolution>();
69 LI = &getAnalysis<LoopInfo>();
70 return false;
71 }
72
getPointerOperand(Instruction & Inst)73 static Value *getPointerOperand(Instruction &Inst) {
74 if (LoadInst *Load = dyn_cast<LoadInst>(&Inst))
75 return Load->getPointerOperand();
76 else if (StoreInst *Store = dyn_cast<StoreInst>(&Inst))
77 return Store->getPointerOperand();
78 else if (GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(&Inst))
79 return Gep->getPointerOperand();
80 return nullptr;
81 }
82
print(raw_ostream & O,const Module *) const83 void Delinearization::print(raw_ostream &O, const Module *) const {
84 O << "Delinearization on function " << F->getName() << ":\n";
85 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
86 Instruction *Inst = &(*I);
87
88 // Only analyze loads and stores.
89 if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) &&
90 !isa<GetElementPtrInst>(Inst))
91 continue;
92
93 const BasicBlock *BB = Inst->getParent();
94 // Delinearize the memory access as analyzed in all the surrounding loops.
95 // Do not analyze memory accesses outside loops.
96 for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
97 const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
98
99 const SCEVUnknown *BasePointer =
100 dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
101 // Do not delinearize if we cannot find the base pointer.
102 if (!BasePointer)
103 break;
104 AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
105 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(AccessFn);
106
107 // Do not try to delinearize memory accesses that are not AddRecs.
108 if (!AR)
109 break;
110
111
112 O << "\n";
113 O << "Inst:" << *Inst << "\n";
114 O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
115 O << "AddRec: " << *AR << "\n";
116
117 SmallVector<const SCEV *, 3> Subscripts, Sizes;
118 AR->delinearize(*SE, Subscripts, Sizes, SE->getElementSize(Inst));
119 if (Subscripts.size() == 0 || Sizes.size() == 0 ||
120 Subscripts.size() != Sizes.size()) {
121 O << "failed to delinearize\n";
122 continue;
123 }
124
125 O << "Base offset: " << *BasePointer << "\n";
126 O << "ArrayDecl[UnknownSize]";
127 int Size = Subscripts.size();
128 for (int i = 0; i < Size - 1; i++)
129 O << "[" << *Sizes[i] << "]";
130 O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
131
132 O << "ArrayRef";
133 for (int i = 0; i < Size; i++)
134 O << "[" << *Subscripts[i] << "]";
135 O << "\n";
136 }
137 }
138 }
139
140 char Delinearization::ID = 0;
141 static const char delinearization_name[] = "Delinearization";
INITIALIZE_PASS_BEGIN(Delinearization,DL_NAME,delinearization_name,true,true)142 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
143 true)
144 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
145 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
146
147 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
148