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/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