Home | History | Annotate | Download | only in Analysis 
      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/Assembly/Writer.h"
     17 #include "llvm/IR/LLVMContext.h"
     18 #include "llvm/Support/CallSite.h"
     19 #include "llvm/Support/ErrorHandling.h"
     20 #include "llvm/Support/InstIterator.h"
     21 #include "llvm/Support/raw_ostream.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 *const 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 *const 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 (!SI->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