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