1 //===- LoopDependenceAnalysis.cpp - LDA Implementation ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
13 // Please note that this is work in progress and the interface is subject to
16 // TODO: adapt as implementation progresses.
18 //===----------------------------------------------------------------------===//
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"
30 LoopPass *llvm::createLoopDependenceAnalysisPass() {
31 return new LoopDependenceAnalysis();
34 static RegisterPass<LoopDependenceAnalysis>
35 R("lda", "Loop Dependence Analysis", false, true);
36 char LoopDependenceAnalysis::ID = 0;
38 //===----------------------------------------------------------------------===//
40 //===----------------------------------------------------------------------===//
42 static inline bool IsMemRefInstr(const Value *V) {
43 const Instruction *I = dyn_cast<const Instruction>(V);
44 return I && (I->mayReadFromMemory() || I->mayWriteToMemory());
47 static void GetMemRefInstrs(
48 const Loop *L, SmallVectorImpl<Instruction*> &memrefs) {
49 for (Loop::block_iterator b = L->block_begin(), be = L->block_end();
51 for (BasicBlock::iterator i = (*b)->begin(), ie = (*b)->end();
57 static bool IsLoadOrStoreInst(Value *I) {
58 return isa<LoadInst>(I) || isa<StoreInst>(I);
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!");
71 //===----------------------------------------------------------------------===//
73 //===----------------------------------------------------------------------===//
75 bool LoopDependenceAnalysis::isDependencePair(const Value *x,
76 const Value *y) const {
77 return IsMemRefInstr(x) &&
79 (cast<const Instruction>(x)->mayWriteToMemory() ||
80 cast<const Instruction>(y)->mayWriteToMemory());
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;
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))
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()));
100 // If we don't know whether or not the two objects alias, assume dependence.
101 if (alias == AliasAnalysis::MayAlias)
104 // If the objects noalias, they are distinct, accesses are independent.
105 if (alias == AliasAnalysis::NoAlias)
108 // TODO: the underlying objects MustAlias, test for dependence
110 // We couldn't establish a more precise result, so we have to conservatively
111 // assume full dependence.
115 //===----------------------------------------------------------------------===//
116 // LoopDependenceAnalysis Implementation
117 //===----------------------------------------------------------------------===//
119 bool LoopDependenceAnalysis::runOnLoop(Loop *L, LPPassManager &) {
121 AA = &getAnalysis<AliasAnalysis>();
122 SE = &getAnalysis<ScalarEvolution>();
126 void LoopDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
127 AU.setPreservesAll();
128 AU.addRequiredTransitive<AliasAnalysis>();
129 AU.addRequiredTransitive<ScalarEvolution>();
132 static void PrintLoopInfo(
133 raw_ostream &OS, LoopDependenceAnalysis *LDA, const Loop *L) {
134 if (!L->empty()) return; // ignore non-innermost loops
136 OS << "Loop at depth " << L->getLoopDepth() << ", header block: ";
137 WriteAsOperand(OS, L->getHeader(), false);
140 SmallVector<Instruction*, 8> memrefs;
141 GetMemRefInstrs(L, memrefs);
142 OS << " Load/store instructions: " << memrefs.size() << "\n";
143 OS << " Pairwise dependence results:\n";
144 for (SmallVector<Instruction*, 8>::const_iterator x = memrefs.begin(),
145 end = memrefs.end(); x != end; ++x)
146 for (SmallVector<Instruction*, 8>::const_iterator y = x + 1;
148 if (LDA->isDependencePair(*x, *y))
149 OS << "\t" << (x - memrefs.begin()) << "," << (y - memrefs.begin())
150 << ": " << (LDA->depends(*x, *y) ? "dependent" : "independent")
154 void LoopDependenceAnalysis::print(raw_ostream &OS, const Module*) const {
155 // TODO: doc why const_cast is safe
156 PrintLoopInfo(OS, const_cast<LoopDependenceAnalysis*>(this), this->L);
159 void LoopDependenceAnalysis::print(std::ostream &OS, const Module *M) const {
160 raw_os_ostream os(OS);