lib/Analysis/DataStructure/GraphChecker.cpp

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