15230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop//===---- Delinearization.cpp - MultiDimensional Index Delinearization ----===// 25230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// 35230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// The LLVM Compiler Infrastructure 45230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// 55230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// This file is distributed under the University of Illinois Open Source 65230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// License. See LICENSE.TXT for details. 75230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// 85230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop//===----------------------------------------------------------------------===// 95230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// 105230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// This implements an analysis pass that tries to delinearize all GEP 115230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// instructions in all loops using the SCEV analysis functionality. This pass is 125230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// only used for testing purposes: if your pass needs delinearization, please 135230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// use the on-demand SCEVAddRecExpr::delinearize() function. 145230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop// 155230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop//===----------------------------------------------------------------------===// 165230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 175230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/IR/Constants.h" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/LoopInfo.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/Passes.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/ScalarEvolution.h" 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/ScalarEvolutionExpressions.h" 225230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/IR/DerivedTypes.h" 235230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/IR/Function.h" 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/InstIterator.h" 255230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/IR/Instructions.h" 265230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/IR/LLVMContext.h" 275230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/IR/Type.h" 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Pass.h" 295230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/Support/CommandLine.h" 305230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/Support/Debug.h" 315230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop#include "llvm/Support/raw_ostream.h" 325230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 335230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popusing namespace llvm; 345230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DL_NAME "delinearize" 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE DL_NAME 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 381a362619f8f74267776a93f101ef32b69b53f5b3Benjamin Kramernamespace { 391a362619f8f74267776a93f101ef32b69b53f5b3Benjamin Kramer 405230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popclass Delinearization : public FunctionPass { 415230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop Delinearization(const Delinearization &); // do not implement 425230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popprotected: 435230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop Function *F; 445230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop LoopInfo *LI; 455230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop ScalarEvolution *SE; 465230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 475230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Poppublic: 485230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop static char ID; // Pass identification, replacement for typeid 495230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 505230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop Delinearization() : FunctionPass(ID) { 515230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop initializeDelinearizationPass(*PassRegistry::getPassRegistry()); 525230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop } 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &O, const Module *M = nullptr) const override; 565230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop}; 575230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 581a362619f8f74267776a93f101ef32b69b53f5b3Benjamin Kramer} // end anonymous namespace 591a362619f8f74267776a93f101ef32b69b53f5b3Benjamin Kramer 605230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popvoid Delinearization::getAnalysisUsage(AnalysisUsage &AU) const { 615230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop AU.setPreservesAll(); 625230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop AU.addRequired<LoopInfo>(); 635230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop AU.addRequired<ScalarEvolution>(); 645230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop} 655230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 665230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popbool Delinearization::runOnFunction(Function &F) { 675230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop this->F = &F; 685230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop SE = &getAnalysis<ScalarEvolution>(); 695230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop LI = &getAnalysis<LoopInfo>(); 705230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop return false; 715230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop} 725230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 735230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popstatic Value *getPointerOperand(Instruction &Inst) { 745230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop if (LoadInst *Load = dyn_cast<LoadInst>(&Inst)) 755230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop return Load->getPointerOperand(); 765230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop else if (StoreInst *Store = dyn_cast<StoreInst>(&Inst)) 775230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop return Store->getPointerOperand(); 785230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop else if (GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(&Inst)) 795230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop return Gep->getPointerOperand(); 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 815230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop} 825230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 835230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popvoid Delinearization::print(raw_ostream &O, const Module *) const { 845230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "Delinearization on function " << F->getName() << ":\n"; 855230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 865230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop Instruction *Inst = &(*I); 87f44941d81dc30cfd357c12292059721c9644a27fSebastian Pop 88f44941d81dc30cfd357c12292059721c9644a27fSebastian Pop // Only analyze loads and stores. 895230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) && 905230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop !isa<GetElementPtrInst>(Inst)) 915230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop continue; 925230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 935230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop const BasicBlock *BB = Inst->getParent(); 945230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop // Delinearize the memory access as analyzed in all the surrounding loops. 955230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop // Do not analyze memory accesses outside loops. 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) { 975230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(*Inst), L); 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 99dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const SCEVUnknown *BasePointer = 100dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn)); 101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Do not delinearize if we cannot find the base pointer. 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!BasePointer) 103dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AccessFn = SE->getMinusSCEV(AccessFn, BasePointer); 1055230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(AccessFn); 106f44941d81dc30cfd357c12292059721c9644a27fSebastian Pop 107f44941d81dc30cfd357c12292059721c9644a27fSebastian Pop // Do not try to delinearize memory accesses that are not AddRecs. 1085230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop if (!AR) 1095230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop break; 1105230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 111dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines O << "\n"; 113dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines O << "Inst:" << *Inst << "\n"; 114dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines O << "In Loop with Header: " << L->getHeader()->getName() << "\n"; 1155230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "AddRec: " << *AR << "\n"; 1165230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 1175230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop SmallVector<const SCEV *, 3> Subscripts, Sizes; 118dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AR->delinearize(*SE, Subscripts, Sizes, SE->getElementSize(Inst)); 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Subscripts.size() == 0 || Sizes.size() == 0 || 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Subscripts.size() != Sizes.size()) { 1215230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "failed to delinearize\n"; 1225230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop continue; 1235230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop } 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 125dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines O << "Base offset: " << *BasePointer << "\n"; 1265230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "ArrayDecl[UnknownSize]"; 127dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines int Size = Subscripts.size(); 1285230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop for (int i = 0; i < Size - 1; i++) 1295230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "[" << *Sizes[i] << "]"; 1305230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << " with elements of " << *Sizes[Size - 1] << " bytes.\n"; 1315230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 1325230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "ArrayRef"; 1335230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop for (int i = 0; i < Size; i++) 1345230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "[" << *Subscripts[i] << "]"; 1355230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop O << "\n"; 1365230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop } 1375230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop } 1385230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop} 1395230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 1405230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popchar Delinearization::ID = 0; 1415230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Popstatic const char delinearization_name[] = "Delinearization"; 1425230ad61fd35d3006e7764c3152d28e2e68c288fSebastian PopINITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true, 1435230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop true) 1445230ad61fd35d3006e7764c3152d28e2e68c288fSebastian PopINITIALIZE_PASS_DEPENDENCY(LoopInfo) 1455230ad61fd35d3006e7764c3152d28e2e68c288fSebastian PopINITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true) 1465230ad61fd35d3006e7764c3152d28e2e68c288fSebastian Pop 1475230ad61fd35d3006e7764c3152d28e2e68c288fSebastian PopFunctionPass *llvm::createDelinearizationPass() { return new Delinearization; } 148