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