LLVM API Documentation

GraphChecker.cpp

Go to the documentation of this file.
00001 //===- GraphChecker.cpp - Assert that various graph properties hold -------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass is used to test DSA with regression tests.  It can be used to check
00011 // that certain graph properties hold, such as two nodes being disjoint, whether
00012 // or not a node is collapsed, etc.  These are the command line arguments that
00013 // it supports:
00014 //
00015 //   --dsgc-dspass={local,bu,td}      - Specify what flavor of graph to check
00016 //   --dsgc-abort-if-any-collapsed    - Abort if any collapsed nodes are found
00017 //   --dsgc-abort-if-collapsed=<list> - Abort if a node pointed to by an SSA
00018 //                                      value with name in <list> is collapsed
00019 //   --dsgc-check-flags=<list>        - Abort if the specified nodes have flags
00020 //                                      that are not specified.
00021 //   --dsgc-abort-if-merged=<list>    - Abort if any of the named SSA values
00022 //                                      point to the same node.
00023 //
00024 //===----------------------------------------------------------------------===//
00025 
00026 #include "llvm/Analysis/DataStructure/DataStructure.h"
00027 #include "llvm/Analysis/DataStructure/DSGraph.h"
00028 #include "llvm/Support/CommandLine.h"
00029 #include "llvm/Value.h"
00030 #include <iostream>
00031 #include <set>
00032 
00033 using namespace llvm;
00034 
00035 namespace {
00036   enum DSPass { local, bu, td };
00037   cl::opt<DSPass>
00038   DSPass("dsgc-dspass", cl::Hidden,
00039        cl::desc("Specify which DSA pass the -datastructure-gc pass should use"),
00040          cl::values(clEnumVal(local, "Local pass"),
00041                     clEnumVal(bu,    "Bottom-up pass"),
00042                     clEnumVal(td,    "Top-down pass"),
00043                     clEnumValEnd), cl::init(local));
00044 
00045   cl::opt<bool>
00046   AbortIfAnyCollapsed("dsgc-abort-if-any-collapsed", cl::Hidden,
00047                       cl::desc("Abort if any collapsed nodes are found"));
00048   cl::list<std::string>
00049   AbortIfCollapsed("dsgc-abort-if-collapsed", cl::Hidden, cl::CommaSeparated,
00050                    cl::desc("Abort if any of the named symbols is collapsed"));
00051   cl::list<std::string>
00052   CheckFlags("dsgc-check-flags", cl::Hidden, cl::CommaSeparated,
00053              cl::desc("Check that flags are specified for nodes"));
00054   cl::list<std::string>
00055   AbortIfMerged("dsgc-abort-if-merged", cl::Hidden, cl::CommaSeparated,
00056              cl::desc("Abort if any of the named symbols are merged together"));
00057 
00058   struct DSGC : public FunctionPass {
00059     DSGC();
00060     bool doFinalization(Module &M);
00061     bool runOnFunction(Function &F);
00062 
00063     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00064       switch (DSPass) {
00065       case local: AU.addRequired<LocalDataStructures>(); break;
00066       case bu:    AU.addRequired<BUDataStructures>(); break;
00067       case td:    AU.addRequired<TDDataStructures>(); break;
00068       }
00069       AU.setPreservesAll();
00070     }
00071     void print(std::ostream &O, const Module *M) const {}
00072 
00073   private:
00074     void verify(const DSGraph &G);
00075   };
00076 
00077   RegisterAnalysis<DSGC> X("datastructure-gc", "DSA Graph Checking Pass");
00078 }
00079 
00080 FunctionPass *llvm::createDataStructureGraphCheckerPass() {
00081   return new DSGC();
00082 }
00083 
00084 
00085 DSGC::DSGC() {
00086   if (!AbortIfAnyCollapsed && AbortIfCollapsed.empty() &&
00087       CheckFlags.empty() && AbortIfMerged.empty()) {
00088     std::cerr << "The -datastructure-gc is useless if you don't specify any"
00089                  " -dsgc-* options.  See the -help-hidden output for a list.\n";
00090     abort();
00091   }
00092 }
00093 
00094 
00095 /// doFinalization - Verify that the globals graph is in good shape...
00096 ///
00097 bool DSGC::doFinalization(Module &M) {
00098   switch (DSPass) {
00099   case local:verify(getAnalysis<LocalDataStructures>().getGlobalsGraph());break;
00100   case bu:   verify(getAnalysis<BUDataStructures>().getGlobalsGraph()); break;
00101   case td:   verify(getAnalysis<TDDataStructures>().getGlobalsGraph()); break;
00102   }
00103   return false;
00104 }
00105 
00106 /// runOnFunction - Get the DSGraph for this function and verify that it is ok.
00107 ///
00108 bool DSGC::runOnFunction(Function &F) {
00109   switch (DSPass) {
00110   case local: verify(getAnalysis<LocalDataStructures>().getDSGraph(F)); break;
00111   case bu:    verify(getAnalysis<BUDataStructures>().getDSGraph(F)); break;
00112   case td:    verify(getAnalysis<TDDataStructures>().getDSGraph(F)); break;
00113   }
00114 
00115   return false;
00116 }
00117 
00118 /// verify - This is the function which checks to make sure that all of the
00119 /// invariants established on the command line are true.
00120 ///
00121 void DSGC::verify(const DSGraph &G) {
00122   // Loop over all of the nodes, checking to see if any are collapsed...
00123   if (AbortIfAnyCollapsed) {
00124     for (DSGraph::node_const_iterator I = G.node_begin(), E = G.node_end();
00125          I != E; ++I)
00126       if (I->isNodeCompletelyFolded()) {
00127         std::cerr << "Node is collapsed: ";
00128         I->print(std::cerr, &G);
00129         abort();
00130       }
00131   }
00132 
00133   if (!AbortIfCollapsed.empty() || !CheckFlags.empty() ||
00134       !AbortIfMerged.empty()) {
00135     // Convert from a list to a set, because we don't have cl::set's yet.  FIXME
00136     std::set<std::string> AbortIfCollapsedS(AbortIfCollapsed.begin(),
00137                                             AbortIfCollapsed.end());
00138     std::set<std::string> AbortIfMergedS(AbortIfMerged.begin(),
00139                                          AbortIfMerged.end());
00140     std::map<std::string, unsigned> CheckFlagsM;
00141 
00142     for (cl::list<std::string>::iterator I = CheckFlags.begin(),
00143            E = CheckFlags.end(); I != E; ++I) {
00144       std::string::size_type ColonPos = I->rfind(':');
00145       if (ColonPos == std::string::npos) {
00146         std::cerr << "Error: '" << *I
00147                << "' is an invalid value for the --dsgc-check-flags option!\n";
00148         abort();
00149       }
00150 
00151       unsigned Flags = 0;
00152       for (unsigned C = ColonPos+1; C != I->size(); ++C)
00153         switch ((*I)[C]) {
00154         case 'S': Flags |= DSNode::AllocaNode;  break;
00155         case 'H': Flags |= DSNode::HeapNode;    break;
00156         case 'G': Flags |= DSNode::GlobalNode;  break;
00157         case 'U': Flags |= DSNode::UnknownNode; break;
00158         case 'I': Flags |= DSNode::Incomplete;  break;
00159         case 'M': Flags |= DSNode::Modified;    break;
00160         case 'R': Flags |= DSNode::Read;        break;
00161         case 'A': Flags |= DSNode::Array;       break;
00162         default: std::cerr << "Invalid DSNode flag!\n"; abort();
00163         }
00164       CheckFlagsM[std::string(I->begin(), I->begin()+ColonPos)] = Flags;
00165     }
00166 
00167     // Now we loop over all of the scalars, checking to see if any are collapsed
00168     // that are not supposed to be, or if any are merged together.
00169     const DSGraph::ScalarMapTy &SM = G.getScalarMap();
00170     std::map<DSNode*, std::string> AbortIfMergedNodes;
00171 
00172     for (DSGraph::ScalarMapTy::const_iterator I = SM.begin(), E = SM.end();
00173          I != E; ++I)
00174       if (I->first->hasName() && I->second.getNode()) {
00175         const std::string &Name = I->first->getName();
00176         DSNode *N = I->second.getNode();
00177 
00178         // Verify it is not collapsed if it is not supposed to be...
00179         if (N->isNodeCompletelyFolded() && AbortIfCollapsedS.count(Name)) {
00180           std::cerr << "Node for value '%" << Name << "' is collapsed: ";
00181           N->print(std::cerr, &G);
00182           abort();
00183         }
00184 
00185         if (CheckFlagsM.count(Name) && CheckFlagsM[Name] != N->getNodeFlags()) {
00186           std::cerr << "Node flags are not as expected for node: " << Name
00187                     << "\n";
00188           N->print(std::cerr, &G);
00189           abort();
00190         }
00191 
00192         // Verify that it is not merged if it is not supposed to be...
00193         if (AbortIfMergedS.count(Name)) {
00194           if (AbortIfMergedNodes.count(N)) {
00195             std::cerr << "Nodes for values '%" << Name << "' and '%"
00196                       << AbortIfMergedNodes[N] << "' is merged: ";
00197             N->print(std::cerr, &G);
00198             abort();
00199           }
00200           AbortIfMergedNodes[N] = Name;
00201         }
00202       }
00203   }
00204 }