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 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 80 char MemDepPrinter::ID = 0; 81 INITIALIZE_PASS_BEGIN(MemDepPrinter, "print-memdeps", 82 "Print MemDeps of function", false, true) 83 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 84 INITIALIZE_PASS_END(MemDepPrinter, "print-memdeps", 85 "Print MemDeps of function", false, true) 86 87 FunctionPass *llvm::createMemDepPrinter() { 88 return new MemDepPrinter(); 89 } 90 91 const char* MemDepPrinter::DepTypeStr[] 92 = {"Clobber", "Def", "NonFuncLocal", "Unknown"}; 93 94 bool 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 160 void 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
