1ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman//===- MemDepPrinter.cpp - Printer for MemoryDependenceAnalysis -----------===// 2ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// 3ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// The LLVM Compiler Infrastructure 4ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// 5ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// This file is distributed under the University of Illinois Open Source 6ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// License. See LICENSE.TXT for details. 7ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// 8ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman//===----------------------------------------------------------------------===// 9ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// 10ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman// 11ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman//===----------------------------------------------------------------------===// 12ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 13ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman#include "llvm/Analysis/MemoryDependenceAnalysis.h" 14075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman#include "llvm/LLVMContext.h" 15ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman#include "llvm/Analysis/Passes.h" 16ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman#include "llvm/Assembly/Writer.h" 17ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman#include "llvm/Support/CallSite.h" 18ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman#include "llvm/Support/InstIterator.h" 19ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman#include "llvm/Support/ErrorHandling.h" 208945db73d198f912d6821975d9960ab1deb0a45fDan Gohman#include "llvm/Support/raw_ostream.h" 21ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman#include "llvm/ADT/SetVector.h" 22ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohmanusing namespace llvm; 23ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 24ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohmannamespace { 25ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman struct MemDepPrinter : public FunctionPass { 26ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman const Function *F; 27ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 28b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman enum DepType { 29b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Clobber = 0, 30b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Def, 31b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman NonFuncLocal, 32b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Unknown 33b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman }; 34b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman 35b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman static const char* DepTypeStr[]; 36b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman 37b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman typedef PointerIntPair<const Instruction *, 2, DepType> InstTypePair; 38b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman typedef std::pair<InstTypePair, const BasicBlock *> Dep; 39ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman typedef SmallSetVector<Dep, 4> DepSet; 40ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman typedef DenseMap<const Instruction *, DepSet> DepSetMap; 41ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman DepSetMap Deps; 42ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 43ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman static char ID; // Pass identifcation, replacement for typeid 44081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MemDepPrinter() : FunctionPass(ID) { 45081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMemDepPrinterPass(*PassRegistry::getPassRegistry()); 46081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 47ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 48ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman virtual bool runOnFunction(Function &F); 49ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 50ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman void print(raw_ostream &OS, const Module * = 0) const; 51ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 52ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 53075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman AU.addRequiredTransitive<AliasAnalysis>(); 54075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman AU.addRequiredTransitive<MemoryDependenceAnalysis>(); 55ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman AU.setPreservesAll(); 56ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 57ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 58ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman virtual void releaseMemory() { 59ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman Deps.clear(); 60ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman F = 0; 61ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 62b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman 63b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman private: 64b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman static InstTypePair getInstTypePair(MemDepResult dep) { 65b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (dep.isClobber()) 66b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return InstTypePair(dep.getInst(), Clobber); 67b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (dep.isDef()) 68b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return InstTypePair(dep.getInst(), Def); 69b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (dep.isNonFuncLocal()) 70b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return InstTypePair(dep.getInst(), NonFuncLocal); 71b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman assert(dep.isUnknown() && "unexptected dependence type"); 72b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return InstTypePair(dep.getInst(), Unknown); 73b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman } 74b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman static InstTypePair getInstTypePair(const Instruction* inst, DepType type) { 75b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return InstTypePair(inst, type); 76b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman } 77ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman }; 78ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman} 79ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 80ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohmanchar MemDepPrinter::ID = 0; 812ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MemDepPrinter, "print-memdeps", 822ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Print MemDeps of function", false, true) 832ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 842ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MemDepPrinter, "print-memdeps", 852ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Print MemDeps of function", false, true) 86ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 87ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan GohmanFunctionPass *llvm::createMemDepPrinter() { 88ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman return new MemDepPrinter(); 89ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman} 90ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 91b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedmanconst char* MemDepPrinter::DepTypeStr[] 92b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman = {"Clobber", "Def", "NonFuncLocal", "Unknown"}; 93b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman 94ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohmanbool MemDepPrinter::runOnFunction(Function &F) { 95ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman this->F = &F; 96075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 97ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 98ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 99ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman // All this code uses non-const interfaces because MemDep is not 100ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman // const-friendly, though nothing is actually modified. 101ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 102ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman Instruction *Inst = &*I; 103ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 104ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman if (!Inst->mayReadFromMemory() && !Inst->mayWriteToMemory()) 105ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman continue; 106ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 107ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman MemDepResult Res = MDA.getDependency(Inst); 108ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman if (!Res.isNonLocal()) { 109b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Deps[Inst].insert(std::make_pair(getInstTypePair(Res), 110ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman static_cast<BasicBlock *>(0))); 111ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } else if (CallSite CS = cast<Value>(Inst)) { 112ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman const MemoryDependenceAnalysis::NonLocalDepInfo &NLDI = 113ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman MDA.getNonLocalCallDependency(CS); 114ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 115ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman DepSet &InstDeps = Deps[Inst]; 116ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman for (MemoryDependenceAnalysis::NonLocalDepInfo::const_iterator 117ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman I = NLDI.begin(), E = NLDI.end(); I != E; ++I) { 118ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman const MemDepResult &Res = I->getResult(); 119b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman InstDeps.insert(std::make_pair(getInstTypePair(Res), I->getBB())); 120ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 121ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } else { 122ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman SmallVector<NonLocalDepResult, 4> NLDI; 123ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 124667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!LI->isUnordered()) { 125667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // FIXME: Handle atomic/volatile loads. 126b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Deps[Inst].insert(std::make_pair(getInstTypePair(0, Unknown), 127667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman static_cast<BasicBlock *>(0))); 128667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman continue; 129667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman } 1306d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location Loc = AA.getLocation(LI); 131667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman MDA.getNonLocalPointerDependency(Loc, true, LI->getParent(), NLDI); 132ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 133e6109828d795d4dd060200aede9c991735b8e5f3Eli Friedman if (!SI->isUnordered()) { 134667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // FIXME: Handle atomic/volatile stores. 135b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Deps[Inst].insert(std::make_pair(getInstTypePair(0, Unknown), 136667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman static_cast<BasicBlock *>(0))); 137667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman continue; 138667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman } 1396d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location Loc = AA.getLocation(SI); 140075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman MDA.getNonLocalPointerDependency(Loc, false, SI->getParent(), NLDI); 141ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } else if (VAArgInst *VI = dyn_cast<VAArgInst>(Inst)) { 1426d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location Loc = AA.getLocation(VI); 143075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman MDA.getNonLocalPointerDependency(Loc, false, VI->getParent(), NLDI); 144ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } else { 145ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman llvm_unreachable("Unknown memory instruction!"); 146ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 147ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 148ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman DepSet &InstDeps = Deps[Inst]; 149ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman for (SmallVectorImpl<NonLocalDepResult>::const_iterator 150ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman I = NLDI.begin(), E = NLDI.end(); I != E; ++I) { 151ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman const MemDepResult &Res = I->getResult(); 152b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman InstDeps.insert(std::make_pair(getInstTypePair(Res), I->getBB())); 153ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 154ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 155ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 156ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 157ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman return false; 158ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman} 159ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 160ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohmanvoid MemDepPrinter::print(raw_ostream &OS, const Module *M) const { 161ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman for (const_inst_iterator I = inst_begin(*F), E = inst_end(*F); I != E; ++I) { 162ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman const Instruction *Inst = &*I; 163ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 164a627e9bfcdd40454c6942228ab9614dc4154d974Dan Gohman DepSetMap::const_iterator DI = Deps.find(Inst); 165a627e9bfcdd40454c6942228ab9614dc4154d974Dan Gohman if (DI == Deps.end()) 166ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman continue; 167ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 168a627e9bfcdd40454c6942228ab9614dc4154d974Dan Gohman const DepSet &InstDeps = DI->second; 169ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 170ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman for (DepSet::const_iterator I = InstDeps.begin(), E = InstDeps.end(); 171ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman I != E; ++I) { 172ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman const Instruction *DepInst = I->first.getPointer(); 173b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman DepType type = I->first.getInt(); 174ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman const BasicBlock *DepBB = I->second; 175ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 176a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman OS << " "; 177b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman OS << DepTypeStr[type]; 178ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman if (DepBB) { 179ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman OS << " in block "; 180ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman WriteAsOperand(OS, DepBB, /*PrintType=*/false, M); 181ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 182a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman if (DepInst) { 183a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman OS << " from: "; 184b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman DepInst->print(OS); 185a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman } 186ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman OS << "\n"; 187ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 188ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman 189ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman Inst->print(OS); 190ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman OS << "\n\n"; 191ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman } 192ead0109f5bc010af837d0fa7c9bb2401b34fb29dDan Gohman} 193