LLVM API Documentation
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 << " (" << CheckFlagsM[Name] << ":" <<N->getNodeFlags() 00188 << ")\n"; 00189 N->print(std::cerr, &G); 00190 abort(); 00191 } 00192 00193 // Verify that it is not merged if it is not supposed to be... 00194 if (AbortIfMergedS.count(Name)) { 00195 if (AbortIfMergedNodes.count(N)) { 00196 std::cerr << "Nodes for values '%" << Name << "' and '%" 00197 << AbortIfMergedNodes[N] << "' is merged: "; 00198 N->print(std::cerr, &G); 00199 abort(); 00200 } 00201 AbortIfMergedNodes[N] = Name; 00202 } 00203 } 00204 } 00205 }