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