1218885Sdim//===- MemDepPrinter.cpp - Printer for MemoryDependenceAnalysis -----------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// 11218885Sdim//===----------------------------------------------------------------------===// 12218885Sdim 13252723Sdim#include "llvm/Analysis/Passes.h" 14252723Sdim#include "llvm/ADT/SetVector.h" 15218885Sdim#include "llvm/Analysis/MemoryDependenceAnalysis.h" 16218885Sdim#include "llvm/Assembly/Writer.h" 17252723Sdim#include "llvm/IR/LLVMContext.h" 18218885Sdim#include "llvm/Support/CallSite.h" 19252723Sdim#include "llvm/Support/ErrorHandling.h" 20218885Sdim#include "llvm/Support/InstIterator.h" 21218885Sdim#include "llvm/Support/raw_ostream.h" 22218885Sdimusing namespace llvm; 23218885Sdim 24218885Sdimnamespace { 25218885Sdim struct MemDepPrinter : public FunctionPass { 26218885Sdim const Function *F; 27218885Sdim 28226890Sdim enum DepType { 29226890Sdim Clobber = 0, 30226890Sdim Def, 31226890Sdim NonFuncLocal, 32226890Sdim Unknown 33226890Sdim }; 34226890Sdim 35245431Sdim static const char *const DepTypeStr[]; 36226890Sdim 37226890Sdim typedef PointerIntPair<const Instruction *, 2, DepType> InstTypePair; 38226890Sdim typedef std::pair<InstTypePair, const BasicBlock *> Dep; 39218885Sdim typedef SmallSetVector<Dep, 4> DepSet; 40218885Sdim typedef DenseMap<const Instruction *, DepSet> DepSetMap; 41218885Sdim DepSetMap Deps; 42218885Sdim 43218885Sdim static char ID; // Pass identifcation, replacement for typeid 44218885Sdim MemDepPrinter() : FunctionPass(ID) { 45218885Sdim initializeMemDepPrinterPass(*PassRegistry::getPassRegistry()); 46218885Sdim } 47218885Sdim 48218885Sdim virtual bool runOnFunction(Function &F); 49218885Sdim 50218885Sdim void print(raw_ostream &OS, const Module * = 0) const; 51218885Sdim 52218885Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 53218885Sdim AU.addRequiredTransitive<AliasAnalysis>(); 54218885Sdim AU.addRequiredTransitive<MemoryDependenceAnalysis>(); 55218885Sdim AU.setPreservesAll(); 56218885Sdim } 57218885Sdim 58218885Sdim virtual void releaseMemory() { 59218885Sdim Deps.clear(); 60218885Sdim F = 0; 61218885Sdim } 62226890Sdim 63226890Sdim private: 64226890Sdim static InstTypePair getInstTypePair(MemDepResult dep) { 65226890Sdim if (dep.isClobber()) 66226890Sdim return InstTypePair(dep.getInst(), Clobber); 67226890Sdim if (dep.isDef()) 68226890Sdim return InstTypePair(dep.getInst(), Def); 69226890Sdim if (dep.isNonFuncLocal()) 70226890Sdim return InstTypePair(dep.getInst(), NonFuncLocal); 71226890Sdim assert(dep.isUnknown() && "unexptected dependence type"); 72226890Sdim return InstTypePair(dep.getInst(), Unknown); 73226890Sdim } 74226890Sdim static InstTypePair getInstTypePair(const Instruction* inst, DepType type) { 75226890Sdim return InstTypePair(inst, type); 76226890Sdim } 77218885Sdim }; 78218885Sdim} 79218885Sdim 80218885Sdimchar MemDepPrinter::ID = 0; 81218885SdimINITIALIZE_PASS_BEGIN(MemDepPrinter, "print-memdeps", 82218885Sdim "Print MemDeps of function", false, true) 83218885SdimINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 84218885SdimINITIALIZE_PASS_END(MemDepPrinter, "print-memdeps", 85218885Sdim "Print MemDeps of function", false, true) 86218885Sdim 87218885SdimFunctionPass *llvm::createMemDepPrinter() { 88218885Sdim return new MemDepPrinter(); 89218885Sdim} 90218885Sdim 91245431Sdimconst char *const MemDepPrinter::DepTypeStr[] 92226890Sdim = {"Clobber", "Def", "NonFuncLocal", "Unknown"}; 93226890Sdim 94218885Sdimbool MemDepPrinter::runOnFunction(Function &F) { 95218885Sdim this->F = &F; 96218885Sdim AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 97218885Sdim MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 98218885Sdim 99218885Sdim // All this code uses non-const interfaces because MemDep is not 100218885Sdim // const-friendly, though nothing is actually modified. 101218885Sdim for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 102218885Sdim Instruction *Inst = &*I; 103218885Sdim 104218885Sdim if (!Inst->mayReadFromMemory() && !Inst->mayWriteToMemory()) 105218885Sdim continue; 106218885Sdim 107218885Sdim MemDepResult Res = MDA.getDependency(Inst); 108218885Sdim if (!Res.isNonLocal()) { 109226890Sdim Deps[Inst].insert(std::make_pair(getInstTypePair(Res), 110218885Sdim static_cast<BasicBlock *>(0))); 111218885Sdim } else if (CallSite CS = cast<Value>(Inst)) { 112218885Sdim const MemoryDependenceAnalysis::NonLocalDepInfo &NLDI = 113218885Sdim MDA.getNonLocalCallDependency(CS); 114218885Sdim 115218885Sdim DepSet &InstDeps = Deps[Inst]; 116218885Sdim for (MemoryDependenceAnalysis::NonLocalDepInfo::const_iterator 117218885Sdim I = NLDI.begin(), E = NLDI.end(); I != E; ++I) { 118218885Sdim const MemDepResult &Res = I->getResult(); 119226890Sdim InstDeps.insert(std::make_pair(getInstTypePair(Res), I->getBB())); 120218885Sdim } 121218885Sdim } else { 122218885Sdim SmallVector<NonLocalDepResult, 4> NLDI; 123218885Sdim if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 124226890Sdim if (!LI->isUnordered()) { 125226890Sdim // FIXME: Handle atomic/volatile loads. 126226890Sdim Deps[Inst].insert(std::make_pair(getInstTypePair(0, Unknown), 127226890Sdim static_cast<BasicBlock *>(0))); 128226890Sdim continue; 129226890Sdim } 130218885Sdim AliasAnalysis::Location Loc = AA.getLocation(LI); 131226890Sdim MDA.getNonLocalPointerDependency(Loc, true, LI->getParent(), NLDI); 132218885Sdim } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 133235633Sdim if (!SI->isUnordered()) { 134226890Sdim // FIXME: Handle atomic/volatile stores. 135226890Sdim Deps[Inst].insert(std::make_pair(getInstTypePair(0, Unknown), 136226890Sdim static_cast<BasicBlock *>(0))); 137226890Sdim continue; 138226890Sdim } 139218885Sdim AliasAnalysis::Location Loc = AA.getLocation(SI); 140218885Sdim MDA.getNonLocalPointerDependency(Loc, false, SI->getParent(), NLDI); 141218885Sdim } else if (VAArgInst *VI = dyn_cast<VAArgInst>(Inst)) { 142218885Sdim AliasAnalysis::Location Loc = AA.getLocation(VI); 143218885Sdim MDA.getNonLocalPointerDependency(Loc, false, VI->getParent(), NLDI); 144218885Sdim } else { 145218885Sdim llvm_unreachable("Unknown memory instruction!"); 146218885Sdim } 147218885Sdim 148218885Sdim DepSet &InstDeps = Deps[Inst]; 149218885Sdim for (SmallVectorImpl<NonLocalDepResult>::const_iterator 150218885Sdim I = NLDI.begin(), E = NLDI.end(); I != E; ++I) { 151218885Sdim const MemDepResult &Res = I->getResult(); 152226890Sdim InstDeps.insert(std::make_pair(getInstTypePair(Res), I->getBB())); 153218885Sdim } 154218885Sdim } 155218885Sdim } 156218885Sdim 157218885Sdim return false; 158218885Sdim} 159218885Sdim 160218885Sdimvoid MemDepPrinter::print(raw_ostream &OS, const Module *M) const { 161218885Sdim for (const_inst_iterator I = inst_begin(*F), E = inst_end(*F); I != E; ++I) { 162218885Sdim const Instruction *Inst = &*I; 163218885Sdim 164218885Sdim DepSetMap::const_iterator DI = Deps.find(Inst); 165218885Sdim if (DI == Deps.end()) 166218885Sdim continue; 167218885Sdim 168218885Sdim const DepSet &InstDeps = DI->second; 169218885Sdim 170218885Sdim for (DepSet::const_iterator I = InstDeps.begin(), E = InstDeps.end(); 171218885Sdim I != E; ++I) { 172218885Sdim const Instruction *DepInst = I->first.getPointer(); 173226890Sdim DepType type = I->first.getInt(); 174218885Sdim const BasicBlock *DepBB = I->second; 175218885Sdim 176224145Sdim OS << " "; 177226890Sdim OS << DepTypeStr[type]; 178218885Sdim if (DepBB) { 179218885Sdim OS << " in block "; 180218885Sdim WriteAsOperand(OS, DepBB, /*PrintType=*/false, M); 181218885Sdim } 182224145Sdim if (DepInst) { 183224145Sdim OS << " from: "; 184226890Sdim DepInst->print(OS); 185224145Sdim } 186218885Sdim OS << "\n"; 187218885Sdim } 188218885Sdim 189218885Sdim Inst->print(OS); 190218885Sdim OS << "\n\n"; 191218885Sdim } 192218885Sdim} 193