1 //===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This implements an analysis pass that tries to delinearize all GEP
10 // instructions in all loops using the SCEV analysis functionality. This pass is
11 // only used for testing purposes: if your pass needs delinearization, please
12 // use the on-demand SCEVAddRecExpr::delinearize() function.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "llvm/Analysis/Delinearization.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/Analysis/Passes.h"
19 #include "llvm/Analysis/ScalarEvolution.h"
20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
21 #include "llvm/IR/Constants.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/PassManager.h"
28 #include "llvm/IR/Type.h"
29 #include "llvm/InitializePasses.h"
30 #include "llvm/Pass.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
33
34 using namespace llvm;
35
36 #define DL_NAME "delinearize"
37 #define DEBUG_TYPE DL_NAME
38
39 namespace {
40
41 class Delinearization : public FunctionPass {
42 Delinearization(const Delinearization &); // do not implement
43 protected:
44 Function *F;
45 LoopInfo *LI;
46 ScalarEvolution *SE;
47
48 public:
49 static char ID; // Pass identification, replacement for typeid
50
Delinearization()51 Delinearization() : FunctionPass(ID) {
52 initializeDelinearizationPass(*PassRegistry::getPassRegistry());
53 }
54 bool runOnFunction(Function &F) override;
55 void getAnalysisUsage(AnalysisUsage &AU) const override;
56 void print(raw_ostream &O, const Module *M = nullptr) const override;
57 };
58
printDelinearization(raw_ostream & O,Function * F,LoopInfo * LI,ScalarEvolution * SE)59 void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
60 ScalarEvolution *SE) {
61 O << "Delinearization on function " << F->getName() << ":\n";
62 for (Instruction &Inst : instructions(F)) {
63 // Only analyze loads and stores.
64 if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
65 !isa<GetElementPtrInst>(&Inst))
66 continue;
67
68 const BasicBlock *BB = Inst.getParent();
69 // Delinearize the memory access as analyzed in all the surrounding loops.
70 // Do not analyze memory accesses outside loops.
71 for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
72 const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
73
74 const SCEVUnknown *BasePointer =
75 dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
76 // Do not delinearize if we cannot find the base pointer.
77 if (!BasePointer)
78 break;
79 AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
80
81 O << "\n";
82 O << "Inst:" << Inst << "\n";
83 O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
84 O << "AccessFunction: " << *AccessFn << "\n";
85
86 SmallVector<const SCEV *, 3> Subscripts, Sizes;
87 SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
88 if (Subscripts.size() == 0 || Sizes.size() == 0 ||
89 Subscripts.size() != Sizes.size()) {
90 O << "failed to delinearize\n";
91 continue;
92 }
93
94 O << "Base offset: " << *BasePointer << "\n";
95 O << "ArrayDecl[UnknownSize]";
96 int Size = Subscripts.size();
97 for (int i = 0; i < Size - 1; i++)
98 O << "[" << *Sizes[i] << "]";
99 O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
100
101 O << "ArrayRef";
102 for (int i = 0; i < Size; i++)
103 O << "[" << *Subscripts[i] << "]";
104 O << "\n";
105 }
106 }
107 }
108
109 } // end anonymous namespace
110
getAnalysisUsage(AnalysisUsage & AU) const111 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
112 AU.setPreservesAll();
113 AU.addRequired<LoopInfoWrapperPass>();
114 AU.addRequired<ScalarEvolutionWrapperPass>();
115 }
116
runOnFunction(Function & F)117 bool Delinearization::runOnFunction(Function &F) {
118 this->F = &F;
119 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
120 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
121 return false;
122 }
123
print(raw_ostream & O,const Module *) const124 void Delinearization::print(raw_ostream &O, const Module *) const {
125 printDelinearization(O, F, LI, SE);
126 }
127
128 char Delinearization::ID = 0;
129 static const char delinearization_name[] = "Delinearization";
INITIALIZE_PASS_BEGIN(Delinearization,DL_NAME,delinearization_name,true,true)130 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
131 true)
132 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
133 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
134
135 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
136
DelinearizationPrinterPass(raw_ostream & OS)137 DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS)
138 : OS(OS) {}
run(Function & F,FunctionAnalysisManager & AM)139 PreservedAnalyses DelinearizationPrinterPass::run(Function &F,
140 FunctionAnalysisManager &AM) {
141 printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F),
142 &AM.getResult<ScalarEvolutionAnalysis>(F));
143 return PreservedAnalyses::all();
144 }
145