LLVM  6.0.0svn
Delinearization.cpp
Go to the documentation of this file.
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/Analysis/LoopInfo.h"
18 #include "llvm/Analysis/Passes.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/Type.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/Debug.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) {
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();
63 }
64 
66  this->F = &F;
67  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
68  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
69  return false;
70 }
71 
73  if (LoadInst *Load = dyn_cast<LoadInst>(&Inst))
74  return Load->getPointerOperand();
75  else if (StoreInst *Store = dyn_cast<StoreInst>(&Inst))
76  return Store->getPointerOperand();
77  else if (GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(&Inst))
78  return Gep->getPointerOperand();
79  return nullptr;
80 }
81 
82 void Delinearization::print(raw_ostream &O, const Module *) const {
83  O << "Delinearization on function " << F->getName() << ":\n";
84  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
85  Instruction *Inst = &(*I);
86 
87  // Only analyze loads and stores.
88  if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) &&
89  !isa<GetElementPtrInst>(Inst))
90  continue;
91 
92  const BasicBlock *BB = Inst->getParent();
93  // Delinearize the memory access as analyzed in all the surrounding loops.
94  // Do not analyze memory accesses outside loops.
95  for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
96  const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
97 
98  const SCEVUnknown *BasePointer =
99  dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
100  // Do not delinearize if we cannot find the base pointer.
101  if (!BasePointer)
102  break;
103  AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
104 
105  O << "\n";
106  O << "Inst:" << *Inst << "\n";
107  O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
108  O << "AccessFunction: " << *AccessFn << "\n";
109 
110  SmallVector<const SCEV *, 3> Subscripts, Sizes;
111  SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(Inst));
112  if (Subscripts.size() == 0 || Sizes.size() == 0 ||
113  Subscripts.size() != Sizes.size()) {
114  O << "failed to delinearize\n";
115  continue;
116  }
117 
118  O << "Base offset: " << *BasePointer << "\n";
119  O << "ArrayDecl[UnknownSize]";
120  int Size = Subscripts.size();
121  for (int i = 0; i < Size - 1; i++)
122  O << "[" << *Sizes[i] << "]";
123  O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
124 
125  O << "ArrayRef";
126  for (int i = 0; i < Size; i++)
127  O << "[" << *Subscripts[i] << "]";
128  O << "\n";
129  }
130  }
131 }
132 
133 char Delinearization::ID = 0;
134 static const char delinearization_name[] = "Delinearization";
135 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
136  true)
138 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
139 
140 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
The main scalar evolution driver.
F(f)
An instruction for reading from memory.
Definition: Instructions.h:164
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static Value * getPointerOperand(Instruction &Inst)
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:132
An instruction for storing to memory.
Definition: Instructions.h:306
void initializeDelinearizationPass(PassRegistry &)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:837
static bool runOnFunction(Function &F, bool PostInlining)
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
FunctionPass * createDelinearizationPass()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
Basic Alias true
static const char delinearization_name[]
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, true) FunctionPass *llvm
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
LLVM Value Representation.
Definition: Value.h:73
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:958
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:133
#define DL_NAME
const BasicBlock * getParent() const
Definition: Instruction.h:66