lib/Analysis/LoopDependenceAnalysis.cpp

   1 //===- LoopDependenceAnalysis.cpp - LDA Implementation ----------*- C++ -*-===//
   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 is the (beginning) of an implementation of a loop dependence analysis
  11 // framework, which is used to detect dependences in memory accesses in loops.
  12 //
  13 // Please note that this is work in progress and the interface is subject to
  14 // change.
  15 //
  16 // TODO: adapt as implementation progresses.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "lda"
  21 #include "llvm/Analysis/LoopDependenceAnalysis.h"
  22 #include "llvm/Analysis/LoopPass.h"
  23 #include "llvm/Analysis/ScalarEvolution.h"
  24 #include "llvm/Instructions.h"
  25 using namespace llvm;
  26
  27 LoopPass *llvm::createLoopDependenceAnalysisPass() {
  28   return new LoopDependenceAnalysis();
  29 }
  30
  31 static RegisterPass<LoopDependenceAnalysis>
  32 R("lda", "Loop Dependence Analysis", false, true);
  33 char LoopDependenceAnalysis::ID = 0;
  34
  35 //===----------------------------------------------------------------------===//
  36 //                             Utility Functions
  37 //===----------------------------------------------------------------------===//
  38
  39 static inline bool isMemRefInstr(const Value *I) {
  40   return isa<LoadInst>(I) || isa<StoreInst>(I);
  41 }
  42
  43 static void getMemRefInstrs(
  44     const Loop *L, SmallVectorImpl<Instruction*> &memrefs) {
  45   for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
  46       b != be; ++b)
  47     for (BasicBlock::iterator i = (*b)->begin(), ie = (*b)->end();
  48         i != ie; ++i)
  49       if (isMemRefInstr(i))
  50         memrefs.push_back(i);
  51 }
  52
  53 //===----------------------------------------------------------------------===//
  54 //                             Dependence Testing
  55 //===----------------------------------------------------------------------===//
  56
  57 bool LoopDependenceAnalysis::isDependencePair(const Value *x,
  58                                               const Value *y) const {
  59   return isMemRefInstr(x) && isMemRefInstr(y)
  60       && (isa<StoreInst>(x) || isa<StoreInst>(y));
  61 }
  62
  63 bool LoopDependenceAnalysis::depends(Value *src, Value *dst) {
  64   assert(isDependencePair(src, dst) && "Values form no dependence pair!");
  65   return true;
  66 }
  67
  68 //===----------------------------------------------------------------------===//
  69 //                   LoopDependenceAnalysis Implementation
  70 //===----------------------------------------------------------------------===//
  71
  72 bool LoopDependenceAnalysis::runOnLoop(Loop *L, LPPassManager &) {
  73   this->L = L;
  74   SE = &getAnalysis<ScalarEvolution>();
  75   return false;
  76 }
  77
  78 void LoopDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  79   AU.setPreservesAll();
  80   AU.addRequiredTransitive<ScalarEvolution>();
  81 }
  82
  83 static void PrintLoopInfo(
  84     raw_ostream &OS, LoopDependenceAnalysis *LDA, const Loop *L) {
  85   if (!L->empty()) return; // ignore non-innermost loops
  86
  87   OS << "Loop at depth " << L->getLoopDepth() << ", header block: ";
  88   WriteAsOperand(OS, L->getHeader(), false);
  89   OS << "\n";
  90
  91   SmallVector<Instruction*, 8> memrefs;
  92   getMemRefInstrs(L, memrefs);
  93   OS << "  Load/store instructions: " << memrefs.size() << "\n";
  94   OS << "  Pairwise dependence results:\n";
  95   for (SmallVector<Instruction*, 8>::const_iterator x = memrefs.begin(),
  96       end = memrefs.end(); x != end; ++x)
  97     for (SmallVector<Instruction*, 8>::const_iterator y = x + 1;
  98         y != end; ++y)
  99       if (LDA->isDependencePair(*x, *y))
 100         OS << "\t" << (x - memrefs.begin()) << "," << (y - memrefs.begin())
 101            << ": " << (LDA->depends(*x, *y) ? "dependent" : "independent")
 102            << "\n";
 103 }
 104
 105 void LoopDependenceAnalysis::print(raw_ostream &OS, const Module*) const {
 106   // TODO: doc why const_cast is safe
 107   PrintLoopInfo(OS, const_cast<LoopDependenceAnalysis*>(this), this->L);
 108 }
 109
 110 void LoopDependenceAnalysis::print(std::ostream &OS, const Module *M) const {
 111   raw_os_ostream os(OS);
 112   print(os, M);
 113 }