LLVM  12.0.0git
Delinearization.cpp
Go to the documentation of this file.
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"
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"
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 
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)
128 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
129 
130 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:67
The main scalar evolution driver.
F(f)
AnalysisUsage & addRequired()
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:131
void initializeDelinearizationPass(PassRegistry &)
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:58
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:284
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:883
FunctionPass * createDelinearizationPass()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
basic 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:516
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:270
INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, true) FunctionPass *llvm
#define I(x, y, z)
Definition: MD5.cpp:59
uint32_t Size
Definition: Profile.cpp:46
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:1233
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:132
#define DL_NAME
const BasicBlock * getParent() const
Definition: Instruction.h:94
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)