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