← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/Analysis/Delinearization.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/Analysis/Delinearization.cpp
 
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
 
 
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
 
 
60
void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
 
61
  AU.setPreservesAll();
 
62
  AU.addRequired<LoopInfoWrapperPass>();
 
63
  AU.addRequired<ScalarEvolution>();
 
64
}
 
65
 
 
66
bool Delinearization::runOnFunction(Function &F) {
 
67
  this->F = &F;
 
68
  SE = &getAnalysis<ScalarEvolution>();
 
69
  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
70
  return false;
 
71
}
 
72
 
 
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
 
 
83
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
      SE->delinearize(AR, 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";
 
142
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
 
143
                      true)
 
144
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 
145
INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
 
146
 
 
147
FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }