1 //===- GraphChecker.cpp - Assert that various graph properties hold -------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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
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.
24 //===----------------------------------------------------------------------===//
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"
36 enum DSPass { local, bu, td };
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));
46 AbortIfAnyCollapsed("dsgc-abort-if-any-collapsed", cl::Hidden,
47 cl::desc("Abort if any collapsed nodes are found"));
49 AbortIfCollapsed("dsgc-abort-if-collapsed", cl::Hidden, cl::CommaSeparated,
50 cl::desc("Abort if any of the named symbols is collapsed"));
52 CheckFlags("dsgc-check-flags", cl::Hidden, cl::CommaSeparated,
53 cl::desc("Check that flags are specified for nodes"));
55 AbortIfMerged("dsgc-abort-if-merged", cl::Hidden, cl::CommaSeparated,
56 cl::desc("Abort if any of the named symbols are merged together"));
58 struct DSGC : public FunctionPass {
60 bool doFinalization(Module &M);
61 bool runOnFunction(Function &F);
63 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
65 case local: AU.addRequired<LocalDataStructures>(); break;
66 case bu: AU.addRequired<BUDataStructures>(); break;
67 case td: AU.addRequired<TDDataStructures>(); break;
71 void print(std::ostream &O, const Module *M) const {}
74 void verify(const DSGraph &G);
77 RegisterPass<DSGC> X("datastructure-gc", "DSA Graph Checking Pass");
80 FunctionPass *llvm::createDataStructureGraphCheckerPass() {
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";
95 /// doFinalization - Verify that the globals graph is in good shape...
97 bool DSGC::doFinalization(Module &M) {
99 case local:verify(getAnalysis<LocalDataStructures>().getGlobalsGraph());break;
100 case bu: verify(getAnalysis<BUDataStructures>().getGlobalsGraph()); break;
101 case td: verify(getAnalysis<TDDataStructures>().getGlobalsGraph()); break;
106 /// runOnFunction - Get the DSGraph for this function and verify that it is ok.
108 bool DSGC::runOnFunction(Function &F) {
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;
118 /// verify - This is the function which checks to make sure that all of the
119 /// invariants established on the command line are true.
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();
126 if (I->isNodeCompletelyFolded()) {
127 std::cerr << "Node is collapsed: ";
128 I->print(std::cerr, &G);
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;
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";
152 for (unsigned C = ColonPos+1; C != I->size(); ++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();
164 CheckFlagsM[std::string(I->begin(), I->begin()+ColonPos)] = Flags;
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;
172 for (DSGraph::ScalarMapTy::const_iterator I = SM.begin(), E = SM.end();
174 if (I->first->hasName() && I->second.getNode()) {
175 const std::string &Name = I->first->getName();
176 DSNode *N = I->second.getNode();
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);
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()
189 N->print(std::cerr, &G);
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);
201 AbortIfMergedNodes[N] = Name;