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
33using namespace llvm;
34
35#define DL_NAME "delinearize"
36#define DEBUG_TYPE DL_NAME
37
38namespace {
39
40class Delinearization : public FunctionPass {
41  Delinearization(const Delinearization &); // do not implement
42protected:
43  Function *F;
44  LoopInfo *LI;
45  ScalarEvolution *SE;
46
47public:
48  static char ID; // Pass identification, replacement for typeid
49
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
60void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
61  AU.setPreservesAll();
62  AU.addRequired<LoopInfoWrapperPass>();
63  AU.addRequired<ScalarEvolutionWrapperPass>();
64}
65
66bool Delinearization::runOnFunction(Function &F) {
67  this->F = &F;
68  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
69  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
70  return false;
71}
72
73static 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
83void 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
106      O << "\n";
107      O << "Inst:" << *Inst << "\n";
108      O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
109      O << "AccessFunction: " << *AccessFn << "\n";
110
111      SmallVector<const SCEV *, 3> Subscripts, Sizes;
112      SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(Inst));
113      if (Subscripts.size() == 0 || Sizes.size() == 0 ||
114          Subscripts.size() != Sizes.size()) {
115        O << "failed to delinearize\n";
116        continue;
117      }
118
119      O << "Base offset: " << *BasePointer << "\n";
120      O << "ArrayDecl[UnknownSize]";
121      int Size = Subscripts.size();
122      for (int i = 0; i < Size - 1; i++)
123        O << "[" << *Sizes[i] << "]";
124      O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
125
126      O << "ArrayRef";
127      for (int i = 0; i < Size; i++)
128        O << "[" << *Subscripts[i] << "]";
129      O << "\n";
130    }
131  }
132}
133
134char Delinearization::ID = 0;
135static const char delinearization_name[] = "Delinearization";
136INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
137                      true)
138INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
139INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
140
141FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
142