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-check-flags=<list>        - Abort if the specified nodes have flags
  13 //                                      that are not specified.
  14 //   --dsgc-abort-if-merged=<list>    - Abort if any of the named SSA values
  15 //                                      point to the same node.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/Analysis/DataStructure.h"
  20 #include "llvm/Analysis/DSGraph.h"
  21 #include "Support/CommandLine.h"
  22 #include "llvm/Value.h"
  23 #include <set>
  24
  25 namespace {
  26   enum DSPass { local, bu, td };
  27   cl::opt<DSPass>
  28   DSPass("dsgc-dspass", cl::Hidden,
  29        cl::desc("Specify which DSA pass the -datastructure-gc pass should use"),
  30          cl::values(clEnumVal(local, "Local pass"),
  31                     clEnumVal(bu,    "Bottom-up pass"),
  32                     clEnumVal(td,    "Top-down pass"), 0), cl::init(local));
  33
  34   cl::opt<bool>
  35   AbortIfAnyCollapsed("dsgc-abort-if-any-collapsed", cl::Hidden,
  36                       cl::desc("Abort if any collapsed nodes are found"));
  37   cl::list<std::string>
  38   AbortIfCollapsed("dsgc-abort-if-collapsed", cl::Hidden, cl::CommaSeparated,
  39                    cl::desc("Abort if any of the named symbols is collapsed"));
  40   cl::list<std::string>
  41   CheckFlags("dsgc-check-flags", cl::Hidden, cl::CommaSeparated,
  42              cl::desc("Check that flags are specified for nodes"));
  43   cl::list<std::string>
  44   AbortIfMerged("dsgc-abort-if-merged", cl::Hidden, cl::CommaSeparated,
  45              cl::desc("Abort if any of the named symbols are merged together"));
  46
  47   struct DSGC : public FunctionPass {
  48     DSGC();
  49     bool doFinalization(Module &M);
  50     bool runOnFunction(Function &F);
  51
  52     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  53       switch (DSPass) {
  54       case local: AU.addRequired<LocalDataStructures>(); break;
  55       case bu:    AU.addRequired<BUDataStructures>(); break;
  56       case td:    AU.addRequired<TDDataStructures>(); break;
  57       }
  58       AU.setPreservesAll();
  59     }
  60     void print(std::ostream &O, const Module *M) const {}
  61
  62   private:
  63     void verify(const DSGraph &G);
  64   };
  65
  66   RegisterAnalysis<DSGC> X("datastructure-gc", "DSA Graph Checking Pass");
  67 }
  68
  69 DSGC::DSGC() {
  70   if (!AbortIfAnyCollapsed && AbortIfCollapsed.empty() &&
  71       CheckFlags.empty() && AbortIfMerged.empty()) {
  72     std::cerr << "The -datastructure-gc is useless if you don't specify any"
  73                  " -dsgc-* options.  See the -help-hidden output for a list.\n";
  74     abort();
  75   }
  76 }
  77
  78
  79 /// doFinalization - Verify that the globals graph is in good shape...
  80 ///
  81 bool DSGC::doFinalization(Module &M) {
  82   switch (DSPass) {
  83   case local:verify(getAnalysis<LocalDataStructures>().getGlobalsGraph());break;
  84   case bu:   verify(getAnalysis<BUDataStructures>().getGlobalsGraph()); break;
  85   case td:   verify(getAnalysis<TDDataStructures>().getGlobalsGraph()); break;
  86   }
  87   return false;
  88 }
  89
  90 /// runOnFunction - Get the DSGraph for this function and verify that it is ok.
  91 ///
  92 bool DSGC::runOnFunction(Function &F) {
  93   switch (DSPass) {
  94   case local: verify(getAnalysis<LocalDataStructures>().getDSGraph(F)); break;
  95   case bu:    verify(getAnalysis<BUDataStructures>().getDSGraph(F)); break;
  96   case td:    verify(getAnalysis<TDDataStructures>().getDSGraph(F)); break;
  97   }
  98
  99   return false;
 100 }
 101
 102 /// verify - This is the function which checks to make sure that all of the
 103 /// invariants established on the command line are true.
 104 ///
 105 void DSGC::verify(const DSGraph &G) {
 106   // Loop over all of the nodes, checking to see if any are collapsed...
 107   if (AbortIfAnyCollapsed) {
 108     const std::vector<DSNode*> &Nodes = G.getNodes();
 109     for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 110       if (Nodes[i]->isNodeCompletelyFolded()) {
 111         std::cerr << "Node is collapsed: ";
 112         Nodes[i]->print(std::cerr, &G);
 113         abort();
 114       }
 115   }
 116
 117   if (!AbortIfCollapsed.empty() || !CheckFlags.empty() ||
 118       !AbortIfMerged.empty()) {
 119     // Convert from a list to a set, because we don't have cl::set's yet.  FIXME
 120     std::set<std::string> AbortIfCollapsedS(AbortIfCollapsed.begin(),
 121                                             AbortIfCollapsed.end());
 122     std::set<std::string> AbortIfMergedS(AbortIfMerged.begin(),
 123                                          AbortIfMerged.end());
 124     std::map<std::string, unsigned> CheckFlagsM;
 125
 126     for (cl::list<std::string>::iterator I = CheckFlags.begin(),
 127            E = CheckFlags.end(); I != E; ++I) {
 128       unsigned ColonPos = I->rfind(':');
 129       if (ColonPos == std::string::npos) {
 130         std::cerr << "Error: '" << *I
 131                << "' is an invalid value for the --dsgc-check-flags option!\n";
 132         abort();
 133       }
 134
 135       unsigned Flags = 0;
 136       for (unsigned C = ColonPos+1; C != I->size(); ++C)
 137         switch ((*I)[C]) {
 138         case 'S': Flags |= DSNode::AllocaNode;  break;
 139         case 'H': Flags |= DSNode::HeapNode;    break;
 140         case 'G': Flags |= DSNode::GlobalNode;  break;
 141         case 'U': Flags |= DSNode::UnknownNode; break;
 142         case 'I': Flags |= DSNode::Incomplete;  break;
 143         case 'M': Flags |= DSNode::Modified;    break;
 144         case 'R': Flags |= DSNode::Read;        break;
 145         case 'A': Flags |= DSNode::Array;       break;
 146         default: std::cerr << "Invalid DSNode flag!\n"; abort();
 147         }
 148       CheckFlagsM[std::string(I->begin(), I->begin()+ColonPos)] = Flags;
 149     }
 150
 151     // Now we loop over all of the scalars, checking to see if any are collapsed
 152     // that are not supposed to be, or if any are merged together.
 153     const DSGraph::ScalarMapTy &SM = G.getScalarMap();
 154     std::map<DSNode*, std::string> AbortIfMergedNodes;
 155
 156     for (DSGraph::ScalarMapTy::const_iterator I = SM.begin(), E = SM.end();
 157          I != E; ++I)
 158       if (I->first->hasName() && I->second.getNode()) {
 159         const std::string &Name = I->first->getName();
 160         DSNode *N = I->second.getNode();
 161
 162         // Verify it is not collapsed if it is not supposed to be...
 163         if (N->isNodeCompletelyFolded() && AbortIfCollapsedS.count(Name)) {
 164           std::cerr << "Node for value '%" << Name << "' is collapsed: ";
 165           N->print(std::cerr, &G);
 166           abort();
 167         }
 168
 169         if (CheckFlagsM.count(Name) && CheckFlagsM[Name] != N->getNodeFlags()) {
 170           std::cerr << "Node flags are not as expected for node: " << Name
 171                     << "\n";
 172           N->print(std::cerr, &G);
 173           abort();
 174         }
 175
 176         // Verify that it is not merged if it is not supposed to be...
 177         if (AbortIfMergedS.count(Name)) {
 178           if (AbortIfMergedNodes.count(N)) {
 179             std::cerr << "Nodes for values '%" << Name << "' and '%"
 180                       << AbortIfMergedNodes[N] << "' is merged: ";
 181             N->print(std::cerr, &G);
 182             abort();
 183           }
 184           AbortIfMergedNodes[N] = Name;
 185         }
 186       }
 187   }
 188 }