MemDepPrinter.cpp revision b414142036012dd9432c4e8c5fef09d4d49fcc22 
1//===- MemDepPrinter.cpp - Printer for MemoryDependenceAnalysis -----------===//
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//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/MemoryDependenceAnalysis.h"
14#include "llvm/LLVMContext.h"
15#include "llvm/Analysis/Passes.h"
16#include "llvm/Assembly/Writer.h"
17#include "llvm/Support/CallSite.h"
18#include "llvm/Support/InstIterator.h"
19#include "llvm/Support/ErrorHandling.h"
20#include "llvm/Support/raw_ostream.h"
21#include "llvm/ADT/SetVector.h"
22using namespace llvm;
23
24namespace {
25  struct MemDepPrinter : public FunctionPass {
26    const Function *F;
27
28    enum DepType {
29      Clobber = 0,
30      Def,
31      NonFuncLocal,
32      Unknown
33    };
34
35    static const char* DepTypeStr[];
36
37    typedef PointerIntPair<const Instruction *, 2, DepType> InstTypePair;
38    typedef std::pair<InstTypePair, const BasicBlock *> Dep;
39    typedef SmallSetVector<Dep, 4> DepSet;
40    typedef DenseMap<const Instruction *, DepSet> DepSetMap;
41    DepSetMap Deps;
42
43    static char ID; // Pass identifcation, replacement for typeid
44    MemDepPrinter() : FunctionPass(ID) {
45      initializeMemDepPrinterPass(*PassRegistry::getPassRegistry());
46    }
47
48    virtual bool runOnFunction(Function &F);
49
50    void print(raw_ostream &OS, const Module * = 0) const;
51
52    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
53      AU.addRequiredTransitive<AliasAnalysis>();
54      AU.addRequiredTransitive<MemoryDependenceAnalysis>();
55      AU.setPreservesAll();
56    }
57
58    virtual void releaseMemory() {
59      Deps.clear();
60      F = 0;
61    }
62
63  private:
64    static InstTypePair getInstTypePair(MemDepResult dep) {
65      if (dep.isClobber())
66        return InstTypePair(dep.getInst(), Clobber);
67      if (dep.isDef())
68        return InstTypePair(dep.getInst(), Def);
69      if (dep.isNonFuncLocal())
70        return InstTypePair(dep.getInst(), NonFuncLocal);
71      assert(dep.isUnknown() && "unexptected dependence type");
72      return InstTypePair(dep.getInst(), Unknown);
73    }
74    static InstTypePair getInstTypePair(const Instruction* inst, DepType type) {
75      return InstTypePair(inst, type);
76    }
77  };
78}
79
80char MemDepPrinter::ID = 0;
81INITIALIZE_PASS_BEGIN(MemDepPrinter, "print-memdeps",
82                      "Print MemDeps of function", false, true)
83INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
84INITIALIZE_PASS_END(MemDepPrinter, "print-memdeps",
85                      "Print MemDeps of function", false, true)
86
87FunctionPass *llvm::createMemDepPrinter() {
88  return new MemDepPrinter();
89}
90
91const char* MemDepPrinter::DepTypeStr[]
92  = {"Clobber", "Def", "NonFuncLocal", "Unknown"};
93
94bool MemDepPrinter::runOnFunction(Function &F) {
95  this->F = &F;
96  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
97  MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>();
98
99  // All this code uses non-const interfaces because MemDep is not
100  // const-friendly, though nothing is actually modified.
101  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
102    Instruction *Inst = &*I;
103
104    if (!Inst->mayReadFromMemory() && !Inst->mayWriteToMemory())
105      continue;
106
107    MemDepResult Res = MDA.getDependency(Inst);
108    if (!Res.isNonLocal()) {
109      Deps[Inst].insert(std::make_pair(getInstTypePair(Res),
110                                       static_cast<BasicBlock *>(0)));
111    } else if (CallSite CS = cast<Value>(Inst)) {
112      const MemoryDependenceAnalysis::NonLocalDepInfo &NLDI =
113        MDA.getNonLocalCallDependency(CS);
114
115      DepSet &InstDeps = Deps[Inst];
116      for (MemoryDependenceAnalysis::NonLocalDepInfo::const_iterator
117           I = NLDI.begin(), E = NLDI.end(); I != E; ++I) {
118        const MemDepResult &Res = I->getResult();
119        InstDeps.insert(std::make_pair(getInstTypePair(Res), I->getBB()));
120      }
121    } else {
122      SmallVector<NonLocalDepResult, 4> NLDI;
123      if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
124        if (!LI->isUnordered()) {
125          // FIXME: Handle atomic/volatile loads.
126          Deps[Inst].insert(std::make_pair(getInstTypePair(0, Unknown),
127                                           static_cast<BasicBlock *>(0)));
128          continue;
129        }
130        AliasAnalysis::Location Loc = AA.getLocation(LI);
131        MDA.getNonLocalPointerDependency(Loc, true, LI->getParent(), NLDI);
132      } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
133        if (!LI->isUnordered()) {
134          // FIXME: Handle atomic/volatile stores.
135          Deps[Inst].insert(std::make_pair(getInstTypePair(0, Unknown),
136                                           static_cast<BasicBlock *>(0)));
137          continue;
138        }
139        AliasAnalysis::Location Loc = AA.getLocation(SI);
140        MDA.getNonLocalPointerDependency(Loc, false, SI->getParent(), NLDI);
141      } else if (VAArgInst *VI = dyn_cast<VAArgInst>(Inst)) {
142        AliasAnalysis::Location Loc = AA.getLocation(VI);
143        MDA.getNonLocalPointerDependency(Loc, false, VI->getParent(), NLDI);
144      } else {
145        llvm_unreachable("Unknown memory instruction!");
146      }
147
148      DepSet &InstDeps = Deps[Inst];
149      for (SmallVectorImpl<NonLocalDepResult>::const_iterator
150           I = NLDI.begin(), E = NLDI.end(); I != E; ++I) {
151        const MemDepResult &Res = I->getResult();
152        InstDeps.insert(std::make_pair(getInstTypePair(Res), I->getBB()));
153      }
154    }
155  }
156
157  return false;
158}
159
160void MemDepPrinter::print(raw_ostream &OS, const Module *M) const {
161  for (const_inst_iterator I = inst_begin(*F), E = inst_end(*F); I != E; ++I) {
162    const Instruction *Inst = &*I;
163
164    DepSetMap::const_iterator DI = Deps.find(Inst);
165    if (DI == Deps.end())
166      continue;
167
168    const DepSet &InstDeps = DI->second;
169
170    for (DepSet::const_iterator I = InstDeps.begin(), E = InstDeps.end();
171         I != E; ++I) {
172      const Instruction *DepInst = I->first.getPointer();
173      DepType type = I->first.getInt();
174      const BasicBlock *DepBB = I->second;
175
176      OS << "    ";
177      OS << DepTypeStr[type];
178      if (DepBB) {
179        OS << " in block ";
180        WriteAsOperand(OS, DepBB, /*PrintType=*/false, M);
181      }
182      if (DepInst) {
183        OS << " from: ";
184        DepInst->print(OS);
185      }
186      OS << "\n";
187    }
188
189    Inst->print(OS);
190    OS << "\n\n";
191  }
192}
193