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/AliasAnalysis.h"
  22 #include "llvm/Analysis/LoopDependenceAnalysis.h"
  23 #include "llvm/Analysis/LoopPass.h"
  24 #include "llvm/Analysis/ScalarEvolution.h"
  25 #include "llvm/Instructions.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28 #include "llvm/Target/TargetData.h"
  29 using namespace llvm;
  30
  31 LoopPass *llvm::createLoopDependenceAnalysisPass() {
  32   return new LoopDependenceAnalysis();
  33 }
  34
  35 static RegisterPass<LoopDependenceAnalysis>
  36 R("lda", "Loop Dependence Analysis", false, true);
  37 char LoopDependenceAnalysis::ID = 0;
  38
  39 //===----------------------------------------------------------------------===//
  40 //                             Utility Functions
  41 //===----------------------------------------------------------------------===//
  42
  43 static inline bool IsMemRefInstr(const Value *V) {
  44   const Instruction *I = dyn_cast<const Instruction>(V);
  45   return I && (I->mayReadFromMemory() || I->mayWriteToMemory());
  46 }
  47
  48 static void GetMemRefInstrs(
  49     const Loop *L, SmallVectorImpl<Instruction*> &memrefs) {
  50   for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
  51       b != be; ++b)
  52     for (BasicBlock::iterator i = (*b)->begin(), ie = (*b)->end();
  53         i != ie; ++i)
  54       if (IsMemRefInstr(i))
  55         memrefs.push_back(i);
  56 }
  57
  58 static bool IsLoadOrStoreInst(Value *I) {
  59   return isa<LoadInst>(I) || isa<StoreInst>(I);
  60 }
  61
  62 static Value *GetPointerOperand(Value *I) {
  63   if (LoadInst *i = dyn_cast<LoadInst>(I))
  64     return i->getPointerOperand();
  65   if (StoreInst *i = dyn_cast<StoreInst>(I))
  66     return i->getPointerOperand();
  67   llvm_unreachable("Value is no load or store instruction!");
  68   // Never reached.
  69   return 0;
  70 }
  71
  72 //===----------------------------------------------------------------------===//
  73 //                             Dependence Testing
  74 //===----------------------------------------------------------------------===//
  75
  76 bool LoopDependenceAnalysis::isDependencePair(const Value *x,
  77                                               const Value *y) const {
  78   return IsMemRefInstr(x) &&
  79          IsMemRefInstr(y) &&
  80          (cast<const Instruction>(x)->mayWriteToMemory() ||
  81           cast<const Instruction>(y)->mayWriteToMemory());
  82 }
  83
  84 bool LoopDependenceAnalysis::depends(Value *src, Value *dst) {
  85   assert(isDependencePair(src, dst) && "Values form no dependence pair!");
  86   DOUT << "== LDA test ==\n" << *src << *dst;
  87
  88   // We only analyse loads and stores; for possible memory accesses by e.g.
  89   // free, call, or invoke instructions we conservatively assume dependence.
  90   if (!IsLoadOrStoreInst(src) || !IsLoadOrStoreInst(dst))
  91     return true;
  92
  93   Value *srcPtr = GetPointerOperand(src);
  94   Value *dstPtr = GetPointerOperand(dst);
  95   const Value *srcObj = srcPtr->getUnderlyingObject();
  96   const Value *dstObj = dstPtr->getUnderlyingObject();
  97   AliasAnalysis::AliasResult alias = AA->alias(
  98       srcObj, AA->getTargetData().getTypeStoreSize(srcObj->getType()),
  99       dstObj, AA->getTargetData().getTypeStoreSize(dstObj->getType()));
 100
 101   // If we don't know whether or not the two objects alias, assume dependence.
 102   if (alias == AliasAnalysis::MayAlias)
 103     return true;
 104
 105   // If the objects noalias, they are distinct, accesses are independent.
 106   if (alias == AliasAnalysis::NoAlias)
 107     return false;
 108
 109   // TODO: the underlying objects MustAlias, test for dependence
 110
 111   // We couldn't establish a more precise result, so we have to conservatively
 112   // assume full dependence.
 113   return true;
 114 }
 115
 116 //===----------------------------------------------------------------------===//
 117 //                   LoopDependenceAnalysis Implementation
 118 //===----------------------------------------------------------------------===//
 119
 120 bool LoopDependenceAnalysis::runOnLoop(Loop *L, LPPassManager &) {
 121   this->L = L;
 122   AA = &getAnalysis<AliasAnalysis>();
 123   SE = &getAnalysis<ScalarEvolution>();
 124   return false;
 125 }
 126
 127 void LoopDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 128   AU.setPreservesAll();
 129   AU.addRequiredTransitive<AliasAnalysis>();
 130   AU.addRequiredTransitive<ScalarEvolution>();
 131 }
 132
 133 static void PrintLoopInfo(
 134     raw_ostream &OS, LoopDependenceAnalysis *LDA, const Loop *L) {
 135   if (!L->empty()) return; // ignore non-innermost loops
 136
 137   SmallVector<Instruction*, 8> memrefs;
 138   GetMemRefInstrs(L, memrefs);
 139
 140   OS << "Loop at depth " << L->getLoopDepth() << ", header block: ";
 141   WriteAsOperand(OS, L->getHeader(), false);
 142   OS << "\n";
 143
 144   OS << "  Load/store instructions: " << memrefs.size() << "\n";
 145   for (SmallVector<Instruction*, 8>::const_iterator x = memrefs.begin(),
 146       end = memrefs.end(); x != end; ++x)
 147     OS << "\t" << (x - memrefs.begin()) << ": " << **x;
 148
 149   OS << "  Pairwise dependence results:\n";
 150   for (SmallVector<Instruction*, 8>::const_iterator x = memrefs.begin(),
 151       end = memrefs.end(); x != end; ++x)
 152     for (SmallVector<Instruction*, 8>::const_iterator y = x + 1;
 153         y != end; ++y)
 154       if (LDA->isDependencePair(*x, *y))
 155         OS << "\t" << (x - memrefs.begin()) << "," << (y - memrefs.begin())
 156            << ": " << (LDA->depends(*x, *y) ? "dependent" : "independent")
 157            << "\n";
 158 }
 159
 160 void LoopDependenceAnalysis::print(raw_ostream &OS, const Module*) const {
 161   // TODO: doc why const_cast is safe
 162   PrintLoopInfo(OS, const_cast<LoopDependenceAnalysis*>(this), this->L);
 163 }
 164
 165 void LoopDependenceAnalysis::print(std::ostream &OS, const Module *M) const {
 166   raw_os_ostream os(OS);
 167   print(os, M);
 168 }