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