Line data    Source code

       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"
      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/Type.h"
      28             : #include "llvm/Pass.h"
      29             : #include "llvm/Support/Debug.h"
      30             : #include "llvm/Support/raw_ostream.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          16 :   Delinearization() : FunctionPass(ID) {
      50          16 :     initializeDelinearizationPass(*PassRegistry::getPassRegistry());
      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          16 : void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {
      60             :   AU.setPreservesAll();
      61             :   AU.addRequired<LoopInfoWrapperPass>();
      62             :   AU.addRequired<ScalarEvolutionWrapperPass>();
      63          16 : }
      64             : 
      65          16 : bool Delinearization::runOnFunction(Function &F) {
      66          16 :   this->F = &F;
      67          16 :   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
      68          16 :   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
      69          16 :   return false;
      70             : }
      71             : 
      72          16 : void Delinearization::print(raw_ostream &O, const Module *) const {
      73          16 :   O << "Delinearization on function " << F->getName() << ":\n";
      74         533 :   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         517 :     if (!isa<StoreInst>(Inst) && !isa<LoadInst>(Inst) &&
      79             :         !isa<GetElementPtrInst>(Inst))
      80             :       continue;
      81             : 
      82         105 :     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         375 :     for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
      86         165 :       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(Inst), L);
      87             : 
      88             :       const SCEVUnknown *BasePointer =
      89         165 :           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
      90             :       // Do not delinearize if we cannot find the base pointer.
      91         165 :       if (!BasePointer)
      92             :         break;
      93         165 :       AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
      94             : 
      95         165 :       O << "\n";
      96         165 :       O << "Inst:" << *Inst << "\n";
      97         165 :       O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
      98         330 :       O << "AccessFunction: " << *AccessFn << "\n";
      99             : 
     100             :       SmallVector<const SCEV *, 3> Subscripts, Sizes;
     101         165 :       SE->delinearize(AccessFn, Subscripts, Sizes, SE->getElementSize(Inst));
     102         330 :       if (Subscripts.size() == 0 || Sizes.size() == 0 ||
     103             :           Subscripts.size() != Sizes.size()) {
     104         124 :         O << "failed to delinearize\n";
     105             :         continue;
     106             :       }
     107             : 
     108          41 :       O << "Base offset: " << *BasePointer << "\n";
     109          41 :       O << "ArrayDecl[UnknownSize]";
     110          41 :       int Size = Subscripts.size();
     111          98 :       for (int i = 0; i < Size - 1; i++)
     112          57 :         O << "[" << *Sizes[i] << "]";
     113          41 :       O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
     114             : 
     115          41 :       O << "ArrayRef";
     116         139 :       for (int i = 0; i < Size; i++)
     117          98 :         O << "[" << *Subscripts[i] << "]";
     118          41 :       O << "\n";
     119             :     }
     120             :   }
     121          16 : }
     122             : 
     123             : char Delinearization::ID = 0;
     124             : static const char delinearization_name[] = "Delinearization";
     125       10756 : INITIALIZE_PASS_BEGIN(Delinearization, DL_NAME, delinearization_name, true,
     126             :                       true)
     127       10756 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
     128       21528 : INITIALIZE_PASS_END(Delinearization, DL_NAME, delinearization_name, true, true)
     129             : 
     130           0 : FunctionPass *llvm::createDelinearizationPass() { return new Delinearization; }