lib/Analysis/DataStructure/GraphChecker.cpp

   1 //===- GraphChecker.cpp - Assert that various graph properties hold -------===//
   2 //
   3 // This pass is used to test DSA with regression tests.  It can be used to check
   4 // that certain graph properties hold, such as two nodes being disjoint, whether
   5 // or not a node is collapsed, etc.  These are the command line arguments that
   6 // it supports:
   7 //
   8 //   --dsgc-dsapass={local,bu,td}     - Specify what flavor of graph to check
   9 //   --dsgc-abort-if-any-collapsed    - Abort if any collapsed nodes are found
  10 //   --dsgc-abort-if-collapsed=<list> - Abort if a node pointed to by an SSA
  11 //                                      value with name in <list> is collapsed
  12 //   --dsgc-abort-if-merged=<list>    - Abort if any of the named SSA values
  13 //                                      point to the same node.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/DataStructure.h"
  18 #include "llvm/Analysis/DSGraph.h"
  19 #include "Support/CommandLine.h"
  20 #include "llvm/Value.h"
  21 #include <set>
  22
  23 namespace {
  24   enum DSPass { local, bu, td };
  25   cl::opt<DSPass>
  26   DSPass("dsgc-dspass", cl::Hidden,
  27        cl::desc("Specify which DSA pass the -datastructure-gc pass should use"),
  28          cl::values(clEnumVal(local, "Local pass"),
  29                     clEnumVal(bu,    "Bottom-up pass"),
  30                     clEnumVal(td,    "Top-down pass"), 0), cl::init(local));
  31
  32   cl::opt<bool>
  33   AbortIfAnyCollapsed("dsgc-abort-if-any-collapsed", cl::Hidden,
  34                       cl::desc("Abort if any collapsed nodes are found"));
  35   cl::list<std::string>
  36   AbortIfCollapsed("dsgc-abort-if-collapsed", cl::Hidden, cl::CommaSeparated,
  37                    cl::desc("Abort if any of the named symbols is collapsed"));
  38   cl::list<std::string>
  39   AbortIfMerged("dsgc-abort-if-merged", cl::Hidden, cl::CommaSeparated,
  40              cl::desc("Abort if any of the named symbols are merged together"));
  41
  42   struct DSGC : public FunctionPass {
  43     DSGC();
  44     bool doFinalization(Module &M);
  45     bool runOnFunction(Function &F);
  46
  47     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  48       switch (DSPass) {
  49       case local: AU.addRequired<LocalDataStructures>(); break;
  50       case bu:    AU.addRequired<BUDataStructures>(); break;
  51       case td:    AU.addRequired<TDDataStructures>(); break;
  52       }
  53       AU.setPreservesAll();
  54     }
  55     void print(std::ostream &O, const Module *M) const {}
  56
  57   private:
  58     void verify(const DSGraph &G);
  59   };
  60
  61   RegisterAnalysis<DSGC> X("datastructure-gc", "DSA Graph Checking Pass");
  62 }
  63
  64 DSGC::DSGC() {
  65   if (!AbortIfAnyCollapsed && AbortIfCollapsed.empty() &&
  66       AbortIfMerged.empty()) {
  67     std::cerr << "The -datastructure-gc is useless if you don't specify any"
  68                  " -dsgc-* options.  See the -help-hidden output for a list.\n";
  69     abort();
  70   }
  71 }
  72
  73
  74 /// doFinalization - Verify that the globals graph is in good shape...
  75 ///
  76 bool DSGC::doFinalization(Module &M) {
  77   switch (DSPass) {
  78   case local:verify(getAnalysis<LocalDataStructures>().getGlobalsGraph());break;
  79   case bu:   verify(getAnalysis<BUDataStructures>().getGlobalsGraph()); break;
  80   case td:   verify(getAnalysis<TDDataStructures>().getGlobalsGraph()); break;
  81   }
  82   return false;
  83 }
  84
  85 /// runOnFunction - Get the DSGraph for this function and verify that it is ok.
  86 ///
  87 bool DSGC::runOnFunction(Function &F) {
  88   switch (DSPass) {
  89   case local: verify(getAnalysis<LocalDataStructures>().getDSGraph(F)); break;
  90   case bu:    verify(getAnalysis<BUDataStructures>().getDSGraph(F)); break;
  91   case td:    verify(getAnalysis<TDDataStructures>().getDSGraph(F)); break;
  92   }
  93
  94   return false;
  95 }
  96
  97 /// verify - This is the function which checks to make sure that all of the
  98 /// invariants established on the command line are true.
  99 ///
 100 void DSGC::verify(const DSGraph &G) {
 101   // Loop over all of the nodes, checking to see if any are collapsed...
 102   if (AbortIfAnyCollapsed) {
 103     const std::vector<DSNode*> &Nodes = G.getNodes();
 104     for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 105       if (Nodes[i]->isNodeCompletelyFolded()) {
 106         std::cerr << "Node is collapsed: ";
 107         Nodes[i]->print(std::cerr, &G);
 108         abort();
 109       }
 110   }
 111
 112   if (!AbortIfCollapsed.empty() || !AbortIfMerged.empty()) {
 113     // Convert from a list to a set, because we don't have cl::set's yet.  FIXME
 114     std::set<std::string> AbortIfCollapsedS(AbortIfCollapsed.begin(),
 115                                             AbortIfCollapsed.end());
 116     std::set<std::string> AbortIfMerged(AbortIfMerged.begin(),
 117                                         AbortIfMerged.end());
 118
 119
 120     // Now we loop over all of the scalars, checking to see if any are collapsed
 121     // that are not supposed to be, or if any are merged together.
 122     const DSGraph::ScalarMapTy &SM = G.getScalarMap();
 123     std::map<DSNode*, std::string> AbortIfMergedNodes;
 124
 125     for (DSGraph::ScalarMapTy::const_iterator I = SM.begin(), E = SM.end();
 126          I != E; ++I)
 127       if (I->first->hasName() && I->second.getNode()) {
 128         DSNode *N = I->second.getNode();
 129
 130         // Verify it is not collapsed if it is not supposed to be...
 131         if (N->isNodeCompletelyFolded() &&
 132             AbortIfCollapsedS.count(I->first->getName())) {
 133           std::cerr << "Node for value '%" << I->first->getName()
 134                     << "' is collapsed: ";
 135           N->print(std::cerr, &G);
 136           abort();
 137         }
 138
 139         // Verify that it is not merged if it is not supposed to be...
 140         if (AbortIfMerged.count(I->first->getName())) {
 141           if (AbortIfMergedNodes.count(N)) {
 142             std::cerr << "Nodes for values '%" << I->first->getName()
 143                       << "' and '%" << AbortIfMergedNodes[N] << "' is merged: ";
 144             N->print(std::cerr, &G);
 145             abort();
 146           }
 147           AbortIfMergedNodes[N] = I->first->getName();
 148         }
 149       }
 150   }
 151 }