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
32using namespace llvm;
33
34#define DL_NAME "delinearize"
35#define DEBUG_TYPE DL_NAME
36
37namespace {
38
39class Delinearization : public FunctionPass {
40  Delinearization(const Delinearization &); // do not implement
41protected:
42  Function *F;
43  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  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
59void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
60  AU.setPreservesAll();
61  AU.addRequired<LoopInfoWrapperPass>();
62  AU.addRequired<ScalarEvolutionWrapperPass>();
63}
64
65bool Delinearization::runOnFunction(Function &F) {
66  this->F = &F;
67  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
68  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
69  return false;
70}
71
72void 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
123char Delinearization::ID = 0;
124static const char delinearization_name[] = "Delinearization";
125INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
126                      true)
127INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
128INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
129
130FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
131