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/Delinearization.h" 17 #include "llvm/Analysis/LoopInfo.h" 18 #include "llvm/Analysis/Passes.h" 19 #include "llvm/Analysis/ScalarEvolution.h" 20 #include "llvm/Analysis/ScalarEvolutionExpressions.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/PassManager.h" 28 #include "llvm/IR/Type.h" 29 #include "llvm/InitializePasses.h" 30 #include "llvm/Pass.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/raw_ostream.h" 33 34 using namespace llvm; 35 36 #define DL_NAME "delinearize" 37 #define DEBUG_TYPE DL_NAME 38 39 namespace { 40 41 class Delinearization : public FunctionPass { 42 Delinearization(const Delinearization &); // do not implement 43 protected: 44 Function *F; 45 LoopInfo *LI; 46 ScalarEvolution *SE; 47 48 public: 49 static char ID; // Pass identification, replacement for typeid 50 51 Delinearization() : FunctionPass(ID) { 52 initializeDelinearizationPass(*PassRegistry::getPassRegistry()); 53 } 54 bool runOnFunction(Function &F) override; 55 void getAnalysisUsage(AnalysisUsage &AU) const override; 56 void print(raw_ostream &O, const Module *M = nullptr) const override; 57 }; 58 59 void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI, 60 ScalarEvolution *SE) { 61 O << "Delinearization on function " << F->getName() << ":\n"; 62 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 63 Instruction *Inst = &(*I); 64 65 // Only analyze loads and stores. 66 if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) && 67 !isa<GetElementPtrInst>(Inst)) 68 continue; 69 70 const BasicBlock *BB = Inst->getParent(); 71 // Delinearize the memory access as analyzed in all the surrounding loops. 72 // Do not analyze memory accesses outside loops. 73 for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) { 74 const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(Inst), L); 75 76 const SCEVUnknown *BasePointer = 77 dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn)); 78 // Do not delinearize if we cannot find the base pointer. 79 if (!BasePointer) 80 break; 81 AccessFn = SE->getMinusSCEV(AccessFn, BasePointer); 82 83 O << "\n"; 84 O << "Inst:" << *Inst << "\n"; 85 O << "In Loop with Header: " << L->getHeader()->getName() << "\n"; 86 O << "AccessFunction: " << *AccessFn << "\n"; 87 88 SmallVector<const SCEV *, 3> Subscripts, Sizes; 89 SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(Inst)); 90 if (Subscripts.size() == 0 || Sizes.size() == 0 || 91 Subscripts.size() != Sizes.size()) { 92 O << "failed to delinearize\n"; 93 continue; 94 } 95 96 O << "Base offset: " << *BasePointer << "\n"; 97 O << "ArrayDecl[UnknownSize]"; 98 int Size = Subscripts.size(); 99 for (int i = 0; i < Size - 1; i++) 100 O << "[" << *Sizes[i] << "]"; 101 O << " with elements of " << *Sizes[Size - 1] << " bytes.\n"; 102 103 O << "ArrayRef"; 104 for (int i = 0; i < Size; i++) 105 O << "[" << *Subscripts[i] << "]"; 106 O << "\n"; 107 } 108 } 109 } 110 111 } // end anonymous namespace 112 113 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const { 114 AU.setPreservesAll(); 115 AU.addRequired<LoopInfoWrapperPass>(); 116 AU.addRequired<ScalarEvolutionWrapperPass>(); 117 } 118 119 bool Delinearization::runOnFunction(Function &F) { 120 this->F = &F; 121 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 122 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 123 return false; 124 } 125 126 void Delinearization::print(raw_ostream &O, const Module *) const { 127 printDelinearization(O, F, LI, SE); 128 } 129 130 char Delinearization::ID = 0; 131 static const char delinearization_name[] = "Delinearization"; 132 INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, 133 true) 134 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 135 INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true) 136 137 FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; } 138 139 DelinearizationPrinterPass::DelinearizationPrinterPass(raw_ostream &OS) 140 : OS(OS) {} 141 PreservedAnalyses DelinearizationPrinterPass::run(Function &F, 142 FunctionAnalysisManager &AM) { 143 printDelinearization(OS, &F, &AM.getResult<LoopAnalysis>(F), 144 &AM.getResult<ScalarEvolutionAnalysis>(F)); 145 return PreservedAnalyses::all(); 146 } 147