ExplodedGraph.cpp 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424
  1. //=-- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -*- C++ -*------=//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // This file defines the template classes ExplodedNode and ExplodedGraph,
  11. // which represent a path-sensitive, intra-procedural "exploded graph."
  12. //
  13. //===----------------------------------------------------------------------===//
  14. #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  15. #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  16. #include "clang/AST/Stmt.h"
  17. #include "clang/AST/ParentMap.h"
  18. #include "llvm/ADT/DenseSet.h"
  19. #include "llvm/ADT/DenseMap.h"
  20. #include "llvm/ADT/SmallVector.h"
  21. #include <vector>
  22. using namespace clang;
  23. using namespace ento;
  24. //===----------------------------------------------------------------------===//
  25. // Node auditing.
  26. //===----------------------------------------------------------------------===//
  27. // An out of line virtual method to provide a home for the class vtable.
  28. ExplodedNode::Auditor::~Auditor() {}
  29. #ifndef NDEBUG
  30. static ExplodedNode::Auditor* NodeAuditor = 0;
  31. #endif
  32. void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) {
  33. #ifndef NDEBUG
  34. NodeAuditor = A;
  35. #endif
  36. }
  37. //===----------------------------------------------------------------------===//
  38. // Cleanup.
  39. //===----------------------------------------------------------------------===//
  40. typedef std::vector<ExplodedNode*> NodeList;
  41. static inline NodeList*& getNodeList(void *&p) { return (NodeList*&) p; }
  42. static const unsigned CounterTop = 1000;
  43. ExplodedGraph::ExplodedGraph()
  44. : NumNodes(0), recentlyAllocatedNodes(0),
  45. freeNodes(0), reclaimNodes(false),
  46. reclaimCounter(CounterTop) {}
  47. ExplodedGraph::~ExplodedGraph() {
  48. if (reclaimNodes) {
  49. delete getNodeList(recentlyAllocatedNodes);
  50. delete getNodeList(freeNodes);
  51. }
  52. }
  53. //===----------------------------------------------------------------------===//
  54. // Node reclamation.
  55. //===----------------------------------------------------------------------===//
  56. bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
  57. // Reclaimn all nodes that match *all* the following criteria:
  58. //
  59. // (1) 1 predecessor (that has one successor)
  60. // (2) 1 successor (that has one predecessor)
  61. // (3) The ProgramPoint is for a PostStmt.
  62. // (4) There is no 'tag' for the ProgramPoint.
  63. // (5) The 'store' is the same as the predecessor.
  64. // (6) The 'GDM' is the same as the predecessor.
  65. // (7) The LocationContext is the same as the predecessor.
  66. // (8) The PostStmt is for a non-consumed Stmt or Expr.
  67. // Conditions 1 and 2.
  68. if (node->pred_size() != 1 || node->succ_size() != 1)
  69. return false;
  70. const ExplodedNode *pred = *(node->pred_begin());
  71. if (pred->succ_size() != 1)
  72. return false;
  73. const ExplodedNode *succ = *(node->succ_begin());
  74. if (succ->pred_size() != 1)
  75. return false;
  76. // Condition 3.
  77. ProgramPoint progPoint = node->getLocation();
  78. if (!isa<PostStmt>(progPoint) ||
  79. (isa<CallEnter>(progPoint) || isa<CallExit>(progPoint)))
  80. return false;
  81. // Condition 4.
  82. PostStmt ps = cast<PostStmt>(progPoint);
  83. if (ps.getTag())
  84. return false;
  85. if (isa<BinaryOperator>(ps.getStmt()))
  86. return false;
  87. // Conditions 5, 6, and 7.
  88. ProgramStateRef state = node->getState();
  89. ProgramStateRef pred_state = pred->getState();
  90. if (state->store != pred_state->store || state->GDM != pred_state->GDM ||
  91. progPoint.getLocationContext() != pred->getLocationContext())
  92. return false;
  93. // Condition 8.
  94. if (const Expr *Ex = dyn_cast<Expr>(ps.getStmt())) {
  95. ParentMap &PM = progPoint.getLocationContext()->getParentMap();
  96. if (!PM.isConsumedExpr(Ex))
  97. return false;
  98. }
  99. return true;
  100. }
  101. void ExplodedGraph::collectNode(ExplodedNode *node) {
  102. // Removing a node means:
  103. // (a) changing the predecessors successor to the successor of this node
  104. // (b) changing the successors predecessor to the predecessor of this node
  105. // (c) Putting 'node' onto freeNodes.
  106. assert(node->pred_size() == 1 || node->succ_size() == 1);
  107. ExplodedNode *pred = *(node->pred_begin());
  108. ExplodedNode *succ = *(node->succ_begin());
  109. pred->replaceSuccessor(succ);
  110. succ->replacePredecessor(pred);
  111. if (!freeNodes)
  112. freeNodes = new NodeList();
  113. getNodeList(freeNodes)->push_back(node);
  114. Nodes.RemoveNode(node);
  115. --NumNodes;
  116. node->~ExplodedNode();
  117. }
  118. void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
  119. if (!recentlyAllocatedNodes)
  120. return;
  121. // Only periodically relcaim nodes so that we can build up a set of
  122. // nodes that meet the reclamation criteria. Freshly created nodes
  123. // by definition have no successor, and thus cannot be reclaimed (see below).
  124. assert(reclaimCounter > 0);
  125. if (--reclaimCounter != 0)
  126. return;
  127. reclaimCounter = CounterTop;
  128. NodeList &nl = *getNodeList(recentlyAllocatedNodes);
  129. for (NodeList::iterator i = nl.begin(), e = nl.end() ; i != e; ++i) {
  130. ExplodedNode *node = *i;
  131. if (shouldCollect(node))
  132. collectNode(node);
  133. }
  134. nl.clear();
  135. }
  136. //===----------------------------------------------------------------------===//
  137. // ExplodedNode.
  138. //===----------------------------------------------------------------------===//
  139. static inline BumpVector<ExplodedNode*>& getVector(void *P) {
  140. return *reinterpret_cast<BumpVector<ExplodedNode*>*>(P);
  141. }
  142. void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
  143. assert (!V->isSink());
  144. Preds.addNode(V, G);
  145. V->Succs.addNode(this, G);
  146. #ifndef NDEBUG
  147. if (NodeAuditor) NodeAuditor->AddEdge(V, this);
  148. #endif
  149. }
  150. void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
  151. assert(getKind() == Size1);
  152. P = reinterpret_cast<uintptr_t>(node);
  153. assert(getKind() == Size1);
  154. }
  155. void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
  156. assert((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
  157. assert(!getFlag());
  158. if (getKind() == Size1) {
  159. if (ExplodedNode *NOld = getNode()) {
  160. BumpVectorContext &Ctx = G.getNodeAllocator();
  161. BumpVector<ExplodedNode*> *V =
  162. G.getAllocator().Allocate<BumpVector<ExplodedNode*> >();
  163. new (V) BumpVector<ExplodedNode*>(Ctx, 4);
  164. assert((reinterpret_cast<uintptr_t>(V) & Mask) == 0x0);
  165. V->push_back(NOld, Ctx);
  166. V->push_back(N, Ctx);
  167. P = reinterpret_cast<uintptr_t>(V) | SizeOther;
  168. assert(getPtr() == (void*) V);
  169. assert(getKind() == SizeOther);
  170. }
  171. else {
  172. P = reinterpret_cast<uintptr_t>(N);
  173. assert(getKind() == Size1);
  174. }
  175. }
  176. else {
  177. assert(getKind() == SizeOther);
  178. getVector(getPtr()).push_back(N, G.getNodeAllocator());
  179. }
  180. }
  181. unsigned ExplodedNode::NodeGroup::size() const {
  182. if (getFlag())
  183. return 0;
  184. if (getKind() == Size1)
  185. return getNode() ? 1 : 0;
  186. else
  187. return getVector(getPtr()).size();
  188. }
  189. ExplodedNode **ExplodedNode::NodeGroup::begin() const {
  190. if (getFlag())
  191. return NULL;
  192. if (getKind() == Size1)
  193. return (ExplodedNode**) (getPtr() ? &P : NULL);
  194. else
  195. return const_cast<ExplodedNode**>(&*(getVector(getPtr()).begin()));
  196. }
  197. ExplodedNode** ExplodedNode::NodeGroup::end() const {
  198. if (getFlag())
  199. return NULL;
  200. if (getKind() == Size1)
  201. return (ExplodedNode**) (getPtr() ? &P+1 : NULL);
  202. else {
  203. // Dereferencing end() is undefined behaviour. The vector is not empty, so
  204. // we can dereference the last elem and then add 1 to the result.
  205. return const_cast<ExplodedNode**>(getVector(getPtr()).end());
  206. }
  207. }
  208. ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
  209. ProgramStateRef State,
  210. bool IsSink,
  211. bool* IsNew) {
  212. // Profile 'State' to determine if we already have an existing node.
  213. llvm::FoldingSetNodeID profile;
  214. void *InsertPos = 0;
  215. NodeTy::Profile(profile, L, State, IsSink);
  216. NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
  217. if (!V) {
  218. if (freeNodes && !getNodeList(freeNodes)->empty()) {
  219. NodeList *nl = getNodeList(freeNodes);
  220. V = nl->back();
  221. nl->pop_back();
  222. }
  223. else {
  224. // Allocate a new node.
  225. V = (NodeTy*) getAllocator().Allocate<NodeTy>();
  226. }
  227. new (V) NodeTy(L, State, IsSink);
  228. if (reclaimNodes) {
  229. if (!recentlyAllocatedNodes)
  230. recentlyAllocatedNodes = new NodeList();
  231. getNodeList(recentlyAllocatedNodes)->push_back(V);
  232. }
  233. // Insert the node into the node set and return it.
  234. Nodes.InsertNode(V, InsertPos);
  235. ++NumNodes;
  236. if (IsNew) *IsNew = true;
  237. }
  238. else
  239. if (IsNew) *IsNew = false;
  240. return V;
  241. }
  242. std::pair<ExplodedGraph*, InterExplodedGraphMap*>
  243. ExplodedGraph::Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd,
  244. llvm::DenseMap<const void*, const void*> *InverseMap) const {
  245. if (NBeg == NEnd)
  246. return std::make_pair((ExplodedGraph*) 0,
  247. (InterExplodedGraphMap*) 0);
  248. assert (NBeg < NEnd);
  249. OwningPtr<InterExplodedGraphMap> M(new InterExplodedGraphMap());
  250. ExplodedGraph* G = TrimInternal(NBeg, NEnd, M.get(), InverseMap);
  251. return std::make_pair(static_cast<ExplodedGraph*>(G), M.take());
  252. }
  253. ExplodedGraph*
  254. ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources,
  255. const ExplodedNode* const* EndSources,
  256. InterExplodedGraphMap* M,
  257. llvm::DenseMap<const void*, const void*> *InverseMap) const {
  258. typedef llvm::DenseSet<const ExplodedNode*> Pass1Ty;
  259. Pass1Ty Pass1;
  260. typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> Pass2Ty;
  261. Pass2Ty& Pass2 = M->M;
  262. SmallVector<const ExplodedNode*, 10> WL1, WL2;
  263. // ===- Pass 1 (reverse DFS) -===
  264. for (const ExplodedNode* const* I = BeginSources; I != EndSources; ++I) {
  265. assert(*I);
  266. WL1.push_back(*I);
  267. }
  268. // Process the first worklist until it is empty. Because it is a std::list
  269. // it acts like a FIFO queue.
  270. while (!WL1.empty()) {
  271. const ExplodedNode *N = WL1.back();
  272. WL1.pop_back();
  273. // Have we already visited this node? If so, continue to the next one.
  274. if (Pass1.count(N))
  275. continue;
  276. // Otherwise, mark this node as visited.
  277. Pass1.insert(N);
  278. // If this is a root enqueue it to the second worklist.
  279. if (N->Preds.empty()) {
  280. WL2.push_back(N);
  281. continue;
  282. }
  283. // Visit our predecessors and enqueue them.
  284. for (ExplodedNode** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I)
  285. WL1.push_back(*I);
  286. }
  287. // We didn't hit a root? Return with a null pointer for the new graph.
  288. if (WL2.empty())
  289. return 0;
  290. // Create an empty graph.
  291. ExplodedGraph* G = MakeEmptyGraph();
  292. // ===- Pass 2 (forward DFS to construct the new graph) -===
  293. while (!WL2.empty()) {
  294. const ExplodedNode *N = WL2.back();
  295. WL2.pop_back();
  296. // Skip this node if we have already processed it.
  297. if (Pass2.find(N) != Pass2.end())
  298. continue;
  299. // Create the corresponding node in the new graph and record the mapping
  300. // from the old node to the new node.
  301. ExplodedNode *NewN = G->getNode(N->getLocation(), N->State, N->isSink(), 0);
  302. Pass2[N] = NewN;
  303. // Also record the reverse mapping from the new node to the old node.
  304. if (InverseMap) (*InverseMap)[NewN] = N;
  305. // If this node is a root, designate it as such in the graph.
  306. if (N->Preds.empty())
  307. G->addRoot(NewN);
  308. // In the case that some of the intended predecessors of NewN have already
  309. // been created, we should hook them up as predecessors.
  310. // Walk through the predecessors of 'N' and hook up their corresponding
  311. // nodes in the new graph (if any) to the freshly created node.
  312. for (ExplodedNode **I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) {
  313. Pass2Ty::iterator PI = Pass2.find(*I);
  314. if (PI == Pass2.end())
  315. continue;
  316. NewN->addPredecessor(PI->second, *G);
  317. }
  318. // In the case that some of the intended successors of NewN have already
  319. // been created, we should hook them up as successors. Otherwise, enqueue
  320. // the new nodes from the original graph that should have nodes created
  321. // in the new graph.
  322. for (ExplodedNode **I=N->Succs.begin(), **E=N->Succs.end(); I!=E; ++I) {
  323. Pass2Ty::iterator PI = Pass2.find(*I);
  324. if (PI != Pass2.end()) {
  325. PI->second->addPredecessor(NewN, *G);
  326. continue;
  327. }
  328. // Enqueue nodes to the worklist that were marked during pass 1.
  329. if (Pass1.count(*I))
  330. WL2.push_back(*I);
  331. }
  332. }
  333. return G;
  334. }
  335. void InterExplodedGraphMap::anchor() { }
  336. ExplodedNode*
  337. InterExplodedGraphMap::getMappedNode(const ExplodedNode *N) const {
  338. llvm::DenseMap<const ExplodedNode*, ExplodedNode*>::const_iterator I =
  339. M.find(N);
  340. return I == M.end() ? 0 : I->second;
  341. }