X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FProfileVerifierPass.cpp;h=a01751849c519d16eeeba7064b79e1a2fc052b61;hb=83a8031336a1155e6b0c3e9a84164324e08d1c8b;hp=e0ef6cee4fec325a81c2d3ac5ac140468a86d9f1;hpb=e8d372e48d6aff0b79d1d5d707964d1a0b9e12aa;p=oota-llvm.git

diff --git a/lib/Analysis/ProfileVerifierPass.cpp b/lib/Analysis/ProfileVerifierPass.cpp
index e0ef6cee4fe..a01751849c5 100644
--- a/lib/Analysis/ProfileVerifierPass.cpp
+++ b/lib/Analysis/ProfileVerifierPass.cpp
@@ -12,53 +12,65 @@
 //
 //===----------------------------------------------------------------------===//
 #define DEBUG_TYPE "profile-verifier"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Analysis/ProfileInfo.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/CallSite.h"
 #include "llvm/Support/CFG.h"
+#include "llvm/Support/InstIterator.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Format.h"
 #include "llvm/Support/Debug.h"
 #include <set>
 using namespace llvm;
 
-static cl::opt<bool,true>
+static cl::opt<bool,false>
 ProfileVerifierDisableAssertions("profile-verifier-noassert",
      cl::desc("Disable assertions"));
 
-namespace {
-  class VISIBILITY_HIDDEN ProfileVerifierPass : public FunctionPass {
+namespace llvm {
+  template<class FType, class BType>
+  class ProfileVerifierPassT : public FunctionPass {
 
     struct DetailedBlockInfo {
-      const BasicBlock *BB;
-      double            BBWeight;
-      double            inWeight;
-      int               inCount;
-      double            outWeight;
-      int               outCount;
+      const BType *BB;
+      double      BBWeight;
+      double      inWeight;
+      int         inCount;
+      double      outWeight;
+      int         outCount;
     };
 
-    ProfileInfo *PI;
-    std::set<const BasicBlock*> BBisVisited;
+    ProfileInfoT<FType, BType> *PI;
+    std::set<const BType*> BBisVisited;
+    std::set<const FType*>   FisVisited;
     bool DisableAssertions;
 
     // When debugging is enabled, the verifier prints a whole slew of debug
     // information, otherwise its just the assert. These are all the helper
     // functions.
     bool PrintedDebugTree;
-    std::set<const BasicBlock*> BBisPrinted;
+    std::set<const BType*> BBisPrinted;
     void debugEntry(DetailedBlockInfo*);
-    void printDebugInfo(const BasicBlock *BB);
+    void printDebugInfo(const BType *BB);
 
   public:
     static char ID; // Class identification, replacement for typeinfo
 
-    explicit ProfileVerifierPass (bool da = false) : FunctionPass(&ID), 
-                                                     DisableAssertions(da) {
+    explicit ProfileVerifierPassT () : FunctionPass(ID) {
+      initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
+      DisableAssertions = ProfileVerifierDisableAssertions;
+    }
+    explicit ProfileVerifierPassT (bool da) : FunctionPass(ID), 
+                                              DisableAssertions(da) {
+      initializeProfileVerifierPassPass(*PassRegistry::getPassRegistry());
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.setPreservesAll();
-      AU.addRequired<ProfileInfo>();
+      AU.addRequired<ProfileInfoT<FType, BType> >();
     }
 
     const char *getPassName() const {
@@ -66,184 +78,305 @@ namespace {
     }
 
     /// run - Verify the profile information.
-    bool runOnFunction(Function &F);
-    void recurseBasicBlock(const BasicBlock *BB);
+    bool runOnFunction(FType &F);
+    void recurseBasicBlock(const BType*);
 
-    double ReadOrAssert(ProfileInfo::Edge);
+    bool   exitReachable(const FType*);
+    double ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge);
     void   CheckValue(bool, const char*, DetailedBlockInfo*);
   };
-}  // End of anonymous namespace
-
-char ProfileVerifierPass::ID = 0;
-static RegisterPass<ProfileVerifierPass>
-X("profile-verifier", "Verify profiling information", false, true);
-
-namespace llvm {
-  FunctionPass *createProfileVerifierPass() {
-    return new ProfileVerifierPass(ProfileVerifierDisableAssertions); 
-  }
-}
 
-void ProfileVerifierPass::printDebugInfo(const BasicBlock *BB) {
-
-  if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
-
-  double BBWeight = PI->getExecutionCount(BB);
-  if (BBWeight == ProfileInfo::MissingValue) { BBWeight = 0; }
-  double inWeight = 0;
-  int inCount = 0;
-  std::set<const BasicBlock*> ProcessedPreds;
-  for ( pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
-        bbi != bbe; ++bbi ) {
-    if (ProcessedPreds.insert(*bbi).second) {
-      double EdgeWeight = PI->getEdgeWeight(PI->getEdge(*bbi,BB));
-      if (EdgeWeight == ProfileInfo::MissingValue) { EdgeWeight = 0; }
-      errs()<<"calculated in-edge ("<<(*bbi)->getNameStr()<<","<<BB->getNameStr()
-            <<"): "<<EdgeWeight<<"\n";
-      inWeight += EdgeWeight;
-      inCount++;
+  typedef ProfileVerifierPassT<Function, BasicBlock> ProfileVerifierPass;
+
+  template<class FType, class BType>
+  void ProfileVerifierPassT<FType, BType>::printDebugInfo(const BType *BB) {
+
+    if (BBisPrinted.find(BB) != BBisPrinted.end()) return;
+
+    double BBWeight = PI->getExecutionCount(BB);
+    if (BBWeight == ProfileInfoT<FType, BType>::MissingValue) { BBWeight = 0; }
+    double inWeight = 0;
+    int inCount = 0;
+    std::set<const BType*> ProcessedPreds;
+    for (const_pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
+         bbi != bbe; ++bbi ) {
+      if (ProcessedPreds.insert(*bbi).second) {
+        typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(*bbi,BB);
+        double EdgeWeight = PI->getEdgeWeight(E);
+        if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
+        dbgs() << "calculated in-edge " << E << ": " 
+               << format("%20.20g",EdgeWeight) << "\n";
+        inWeight += EdgeWeight;
+        inCount++;
+      }
     }
-  }
-  double outWeight = 0;
-  int outCount = 0;
-  std::set<const BasicBlock*> ProcessedSuccs;
-  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
-        bbi != bbe; ++bbi ) {
-    if (ProcessedSuccs.insert(*bbi).second) {
-      double EdgeWeight = PI->getEdgeWeight(PI->getEdge(BB,*bbi));
-      if (EdgeWeight == ProfileInfo::MissingValue) { EdgeWeight = 0; }
-      errs()<<"calculated out-edge ("<<BB->getNameStr()<<","<<(*bbi)->getNameStr()
-            <<"): "<<EdgeWeight<<"\n";
-      outWeight += EdgeWeight;
-      outCount++;
+    double outWeight = 0;
+    int outCount = 0;
+    std::set<const BType*> ProcessedSuccs;
+    for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
+          bbi != bbe; ++bbi ) {
+      if (ProcessedSuccs.insert(*bbi).second) {
+        typename ProfileInfoT<FType, BType>::Edge E = PI->getEdge(BB,*bbi);
+        double EdgeWeight = PI->getEdgeWeight(E);
+        if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) { EdgeWeight = 0; }
+        dbgs() << "calculated out-edge " << E << ": " 
+               << format("%20.20g",EdgeWeight) << "\n";
+        outWeight += EdgeWeight;
+        outCount++;
+      }
+    }
+    dbgs() << "Block " << BB->getNameStr()                << " in " 
+           << BB->getParent()->getNameStr()               << ":"
+           << "BBWeight="  << format("%20.20g",BBWeight)  << ","
+           << "inWeight="  << format("%20.20g",inWeight)  << ","
+           << "inCount="   << inCount                     << ","
+           << "outWeight=" << format("%20.20g",outWeight) << ","
+           << "outCount"   << outCount                    << "\n";
+
+    // mark as visited and recurse into subnodes
+    BBisPrinted.insert(BB);
+    for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 
+          bbi != bbe; ++bbi ) {
+      printDebugInfo(*bbi);
     }
   }
-  errs()<<"Block "<<BB->getNameStr()<<" in "<<BB->getParent()->getNameStr()
-        <<",BBWeight="<<BBWeight<<",inWeight="<<inWeight<<",inCount="<<inCount
-        <<",outWeight="<<outWeight<<",outCount"<<outCount<<"\n";
-
-  // mark as visited and recurse into subnodes
-  BBisPrinted.insert(BB);
-  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 
-        bbi != bbe; ++bbi ) {
-    printDebugInfo(*bbi);
+
+  template<class FType, class BType>
+  void ProfileVerifierPassT<FType, BType>::debugEntry (DetailedBlockInfo *DI) {
+    dbgs() << "TROUBLE: Block " << DI->BB->getNameStr()       << " in "
+           << DI->BB->getParent()->getNameStr()               << ":"
+           << "BBWeight="  << format("%20.20g",DI->BBWeight)  << ","
+           << "inWeight="  << format("%20.20g",DI->inWeight)  << ","
+           << "inCount="   << DI->inCount                     << ","
+           << "outWeight=" << format("%20.20g",DI->outWeight) << ","
+           << "outCount="  << DI->outCount                    << "\n";
+    if (!PrintedDebugTree) {
+      PrintedDebugTree = true;
+      printDebugInfo(&(DI->BB->getParent()->getEntryBlock()));
+    }
   }
-}
 
-void ProfileVerifierPass::debugEntry (DetailedBlockInfo *DI) {
-  errs() << "TROUBLE: Block " << DI->BB->getNameStr() << " in "
-         << DI->BB->getParent()->getNameStr()  << ":";
-  errs() << "BBWeight="  << DI->BBWeight   << ",";
-  errs() << "inWeight="  << DI->inWeight   << ",";
-  errs() << "inCount="   << DI->inCount    << ",";
-  errs() << "outWeight=" << DI->outWeight  << ",";
-  errs() << "outCount="  << DI->outCount   << ",";
-  if (!PrintedDebugTree) {
-    PrintedDebugTree = true;
-    printDebugInfo(&(DI->BB->getParent()->getEntryBlock()));
+  // This compares A and B for equality.
+  static bool Equals(double A, double B) {
+    return A == B;
   }
-}
 
-// compare with relative error
-static bool Equals(double A, double B) { 
-  double maxRelativeError = 0.0000001;
-  if (A == B)
-    return true;
-  double relativeError;
-  if (fabs(B) > fabs(A)) 
-    relativeError = fabs((A - B) / B);
-  else 
-    relativeError = fabs((A - B) / A);
-  if (relativeError <= maxRelativeError) return true; 
-  return false; 
-}
+  // This checks if the function "exit" is reachable from an given function
+  // via calls, this is necessary to check if a profile is valid despite the
+  // counts not fitting exactly.
+  template<class FType, class BType>
+  bool ProfileVerifierPassT<FType, BType>::exitReachable(const FType *F) {
+    if (!F) return false;
 
-double ProfileVerifierPass::ReadOrAssert(ProfileInfo::Edge E) {
-  const char *Message = "ASSERT:Edge has missing value";
-  double EdgeWeight = PI->getEdgeWeight(E);
-  if (EdgeWeight == ProfileInfo::MissingValue) {
-    if (DisableAssertions) {
-      errs() << Message << "\n";
-      return 0;
-    } else { 
-      assert(0 && Message);
+    if (FisVisited.count(F)) return false;
+
+    FType *Exit = F->getParent()->getFunction("exit");
+    if (Exit == F) {
+      return true;
     }
-  } else {
-    return EdgeWeight;
-  }
-}
 
-void ProfileVerifierPass::CheckValue(bool Error, const char *Message, DetailedBlockInfo *DI) {
-  if (Error) {
-    DEBUG(debugEntry(DI));
-    if (DisableAssertions) {
-      errs() << Message << "\n";
-    } else { 
-      assert(0 && Message);
+    FisVisited.insert(F);
+    bool exits = false;
+    for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
+      if (const CallInst *CI = dyn_cast<CallInst>(&*I)) {
+        FType *F = CI->getCalledFunction();
+        if (F) {
+          exits |= exitReachable(F);
+        } else {
+          // This is a call to a pointer, all bets are off...
+          exits = true;
+        }
+        if (exits) break;
+      }
     }
+    return exits;
   }
-  return;
-}
 
-void ProfileVerifierPass::recurseBasicBlock(const BasicBlock *BB) {
+  #define ASSERTMESSAGE(M) \
+    { dbgs() << "ASSERT:" << (M) << "\n"; \
+      if (!DisableAssertions) assert(0 && (M)); }
+
+  template<class FType, class BType>
+  double ProfileVerifierPassT<FType, BType>::ReadOrAssert(typename ProfileInfoT<FType, BType>::Edge E) {
+    double EdgeWeight = PI->getEdgeWeight(E);
+    if (EdgeWeight == ProfileInfoT<FType, BType>::MissingValue) {
+      dbgs() << "Edge " << E << " in Function " 
+             << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
+      ASSERTMESSAGE("Edge has missing value");
+      return 0;
+    } else {
+      if (EdgeWeight < 0) {
+        dbgs() << "Edge " << E << " in Function " 
+               << ProfileInfoT<FType, BType>::getFunction(E)->getNameStr() << ": ";
+        ASSERTMESSAGE("Edge has negative value");
+      }
+      return EdgeWeight;
+    }
+  }
 
-  if (BBisVisited.find(BB) != BBisVisited.end()) return;
+  template<class FType, class BType>
+  void ProfileVerifierPassT<FType, BType>::CheckValue(bool Error, 
+                                                      const char *Message,
+                                                      DetailedBlockInfo *DI) {
+    if (Error) {
+      DEBUG(debugEntry(DI));
+      dbgs() << "Block " << DI->BB->getNameStr() << " in Function " 
+             << DI->BB->getParent()->getNameStr() << ": ";
+      ASSERTMESSAGE(Message);
+    }
+    return;
+  }
 
-  DetailedBlockInfo DI;
-  DI.BB = BB;
-  DI.outCount = DI.inCount = DI.inWeight = DI.outWeight = 0;
-  std::set<const BasicBlock*> ProcessedPreds;
-  for ( pred_const_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
-        bbi != bbe; ++bbi ) {
-    if (ProcessedPreds.insert(*bbi).second) {
-      DI.inWeight += ReadOrAssert(PI->getEdge(*bbi,BB));
+  // This calculates the Information for a block and then recurses into the
+  // successors.
+  template<class FType, class BType>
+  void ProfileVerifierPassT<FType, BType>::recurseBasicBlock(const BType *BB) {
+
+    // Break the recursion by remembering all visited blocks.
+    if (BBisVisited.find(BB) != BBisVisited.end()) return;
+
+    // Use a data structure to store all the information, this can then be handed
+    // to debug printers.
+    DetailedBlockInfo DI;
+    DI.BB = BB;
+    DI.outCount = DI.inCount = 0;
+    DI.inWeight = DI.outWeight = 0;
+
+    // Read predecessors.
+    std::set<const BType*> ProcessedPreds;
+    const_pred_iterator bpi = pred_begin(BB), bpe = pred_end(BB);
+    // If there are none, check for (0,BB) edge.
+    if (bpi == bpe) {
+      DI.inWeight += ReadOrAssert(PI->getEdge(0,BB));
       DI.inCount++;
     }
-  }
+    for (;bpi != bpe; ++bpi) {
+      if (ProcessedPreds.insert(*bpi).second) {
+        DI.inWeight += ReadOrAssert(PI->getEdge(*bpi,BB));
+        DI.inCount++;
+      }
+    }
 
-  std::set<const BasicBlock*> ProcessedSuccs;
-  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
-        bbi != bbe; ++bbi ) {
-    if (ProcessedSuccs.insert(*bbi).second) {
-      DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
+    // Read successors.
+    std::set<const BType*> ProcessedSuccs;
+    succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
+    // If there is an (0,BB) edge, consider it too. (This is done not only when
+    // there are no successors, but every time; not every function contains
+    // return blocks with no successors (think loop latch as return block)).
+    double w = PI->getEdgeWeight(PI->getEdge(BB,0));
+    if (w != ProfileInfoT<FType, BType>::MissingValue) {
+      DI.outWeight += w;
       DI.outCount++;
     }
-  }
+    for (;bbi != bbe; ++bbi) {
+      if (ProcessedSuccs.insert(*bbi).second) {
+        DI.outWeight += ReadOrAssert(PI->getEdge(BB,*bbi));
+        DI.outCount++;
+      }
+    }
 
-  DI.BBWeight = PI->getExecutionCount(BB);
-  CheckValue(DI.BBWeight == ProfileInfo::MissingValue, "ASSERT:BasicBlock has missing value", &DI);
+    // Read block weight.
+    DI.BBWeight = PI->getExecutionCount(BB);
+    CheckValue(DI.BBWeight == ProfileInfoT<FType, BType>::MissingValue,
+               "BasicBlock has missing value", &DI);
+    CheckValue(DI.BBWeight < 0,
+               "BasicBlock has negative value", &DI);
+
+    // Check if this block is a setjmp target.
+    bool isSetJmpTarget = false;
+    if (DI.outWeight > DI.inWeight) {
+      for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
+           i != ie; ++i) {
+        if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
+          FType *F = CI->getCalledFunction();
+          if (F && (F->getName() == "_setjmp")) {
+            isSetJmpTarget = true; break;
+          }
+        }
+      }
+    }
+    // Check if this block is eventually reaching exit.
+    bool isExitReachable = false;
+    if (DI.inWeight > DI.outWeight) {
+      for (typename BType::const_iterator i = BB->begin(), ie = BB->end();
+           i != ie; ++i) {
+        if (const CallInst *CI = dyn_cast<CallInst>(&*i)) {
+          FType *F = CI->getCalledFunction();
+          if (F) {
+            FisVisited.clear();
+            isExitReachable |= exitReachable(F);
+          } else {
+            // This is a call to a pointer, all bets are off...
+            isExitReachable = true;
+          }
+          if (isExitReachable) break;
+        }
+      }
+    }
+
+    if (DI.inCount > 0 && DI.outCount == 0) {
+       // If this is a block with no successors.
+      if (!isSetJmpTarget) {
+        CheckValue(!Equals(DI.inWeight,DI.BBWeight), 
+                   "inWeight and BBWeight do not match", &DI);
+      }
+    } else if (DI.inCount == 0 && DI.outCount > 0) {
+      // If this is a block with no predecessors.
+      if (!isExitReachable)
+        CheckValue(!Equals(DI.BBWeight,DI.outWeight), 
+                   "BBWeight and outWeight do not match", &DI);
+    } else {
+      // If this block has successors and predecessors.
+      if (DI.inWeight > DI.outWeight && !isExitReachable)
+        CheckValue(!Equals(DI.inWeight,DI.outWeight), 
+                   "inWeight and outWeight do not match", &DI);
+      if (DI.inWeight < DI.outWeight && !isSetJmpTarget)
+        CheckValue(!Equals(DI.inWeight,DI.outWeight), 
+                   "inWeight and outWeight do not match", &DI);
+    }
 
-  if (DI.inCount > 0) {
-    CheckValue(!Equals(DI.inWeight,DI.BBWeight), "ASSERT:inWeight and BBWeight do not match", &DI);
-  }
-  if (DI.outCount > 0) {
-    CheckValue(!Equals(DI.outWeight,DI.BBWeight), "ASSERT:outWeight and BBWeight do not match", &DI);
-  }
 
-  // mark as visited and recurse into subnodes
-  BBisVisited.insert(BB);
-  for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 
-        bbi != bbe; ++bbi ) {
-    recurseBasicBlock(*bbi);
+    // Mark this block as visited, rescurse into successors.
+    BBisVisited.insert(BB);
+    for ( succ_const_iterator bbi = succ_begin(BB), bbe = succ_end(BB); 
+          bbi != bbe; ++bbi ) {
+      recurseBasicBlock(*bbi);
+    }
   }
-}
 
-bool ProfileVerifierPass::runOnFunction(Function &F) {
-  PI = &getAnalysis<ProfileInfo>();
+  template<class FType, class BType>
+  bool ProfileVerifierPassT<FType, BType>::runOnFunction(FType &F) {
+    PI = getAnalysisIfAvailable<ProfileInfoT<FType, BType> >();
+    if (!PI)
+      ASSERTMESSAGE("No ProfileInfo available");
+
+    // Prepare global variables.
+    PrintedDebugTree = false;
+    BBisVisited.clear();
+
+    // Fetch entry block and recurse into it.
+    const BType *entry = &F.getEntryBlock();
+    recurseBasicBlock(entry);
+
+    if (PI->getExecutionCount(&F) != PI->getExecutionCount(entry))
+      ASSERTMESSAGE("Function count and entry block count do not match");
 
-  if (PI->getExecutionCount(&F) == ProfileInfo::MissingValue) {
-    DEBUG(errs()<<"Function "<<F.getNameStr()<<" has no profile\n");
     return false;
   }
 
-  PrintedDebugTree = false;
-  BBisVisited.clear();
+  template<class FType, class BType>
+  char ProfileVerifierPassT<FType, BType>::ID = 0;
+}
 
-  const BasicBlock *entry = &F.getEntryBlock();
-  recurseBasicBlock(entry);
+INITIALIZE_PASS_BEGIN(ProfileVerifierPass, "profile-verifier",
+                "Verify profiling information", false, true)
+INITIALIZE_AG_DEPENDENCY(ProfileInfo)
+INITIALIZE_PASS_END(ProfileVerifierPass, "profile-verifier",
+                "Verify profiling information", false, true)
 
-  if (!DisableAssertions)
-    assert((PI->getExecutionCount(&F)==PI->getExecutionCount(entry)) &&
-           "Function count and entry block count do not match");
-  return false;
+namespace llvm {
+  FunctionPass *createProfileVerifierPass() {
+    return new ProfileVerifierPass(ProfileVerifierDisableAssertions); 
+  }
 }
+