(1) Rematerialize nodes from the globals graph into the current graph
[oota-llvm.git] / 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-abort-if-incomplete=<list>- Abort if any of the named SSA values
13 //                                      are incomplete.
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   AbortIfIncomplete("dsgc-abort-if-incomplete", cl::Hidden, cl::CommaSeparated,
42                    cl::desc("Abort if any of the named symbols is incomplete"));
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       AbortIfIncomplete.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() || !AbortIfIncomplete.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> AbortIfIncompleteS(AbortIfIncomplete.begin(),
123                                              AbortIfIncomplete.end());
124     std::set<std::string> AbortIfMergedS(AbortIfMerged.begin(),
125                                          AbortIfMerged.end());
126     
127     
128     // Now we loop over all of the scalars, checking to see if any are collapsed
129     // that are not supposed to be, or if any are merged together.
130     const DSGraph::ScalarMapTy &SM = G.getScalarMap();
131     std::map<DSNode*, std::string> AbortIfMergedNodes;
132     
133     for (DSGraph::ScalarMapTy::const_iterator I = SM.begin(), E = SM.end();
134          I != E; ++I)
135       if (I->first->hasName() && I->second.getNode()) {
136         std::string Name = I->first->getName();
137         DSNode *N = I->second.getNode();
138         
139         // Verify it is not collapsed if it is not supposed to be...
140         if (N->isNodeCompletelyFolded() && AbortIfCollapsedS.count(Name)) {
141           std::cerr << "Node for value '%" << Name << "' is collapsed: ";
142           N->print(std::cerr, &G);
143           abort();
144         }
145
146         if (N->isIncomplete() && AbortIfIncompleteS.count(Name)) {
147           std::cerr << "Node for value '%" << Name << "' is incomplete: ";
148           N->print(std::cerr, &G);
149           abort();
150         }
151
152         // Verify that it is not merged if it is not supposed to be...
153         if (AbortIfMergedS.count(Name)) {
154           if (AbortIfMergedNodes.count(N)) {
155             std::cerr << "Nodes for values '%" << Name << "' and '%"
156                       << AbortIfMergedNodes[N] << "' is merged: ";
157             N->print(std::cerr, &G);
158             abort();
159           }
160           AbortIfMergedNodes[N] = Name;
161         }
162       }
163   }
164 }