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