lib/Analysis/ExplodedGraph.cpp

   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
  15 #include "clang/Analysis/PathSensitive/ExplodedGraph.h"
  16 #include "clang/Analysis/PathSensitive/GRState.h"
  17 #include "clang/AST/Stmt.h"
  18 #include "llvm/ADT/DenseSet.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include <vector>
  22
  23 using namespace clang;
  24
  25 //===----------------------------------------------------------------------===//
  26 // Node auditing.
  27 //===----------------------------------------------------------------------===//
  28
  29 // An out of line virtual method to provide a home for the class vtable.
  30 ExplodedNode::Auditor::~Auditor() {}
  31
  32 #ifndef NDEBUG
  33 static ExplodedNode::Auditor* NodeAuditor = 0;
  34 #endif
  35
  36 void ExplodedNode::SetAuditor(ExplodedNode::Auditor* A) {
  37 #ifndef NDEBUG
  38   NodeAuditor = A;
  39 #endif
  40 }
  41
  42 //===----------------------------------------------------------------------===//
  43 // ExplodedNode.
  44 //===----------------------------------------------------------------------===//
  45
  46 static inline BumpVector<ExplodedNode*>& getVector(void* P) {
  47   return *reinterpret_cast<BumpVector<ExplodedNode*>*>(P);
  48 }
  49
  50 void ExplodedNode::addPredecessor(ExplodedNode* V, ExplodedGraph &G) {
  51   assert (!V->isSink());
  52   Preds.addNode(V, G);
  53   V->Succs.addNode(this, G);
  54 #ifndef NDEBUG
  55   if (NodeAuditor) NodeAuditor->AddEdge(V, this);
  56 #endif
  57 }
  58
  59 void ExplodedNode::NodeGroup::addNode(ExplodedNode* N, ExplodedGraph &G) {
  60   assert((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
  61   assert(!getFlag());
  62
  63   if (getKind() == Size1) {
  64     if (ExplodedNode* NOld = getNode()) {
  65       BumpVectorContext &Ctx = G.getNodeAllocator();
  66       BumpVector<ExplodedNode*> *V =
  67         G.getAllocator().Allocate<BumpVector<ExplodedNode*> >();
  68       new (V) BumpVector<ExplodedNode*>(Ctx, 4);
  69
  70       assert((reinterpret_cast<uintptr_t>(V) & Mask) == 0x0);
  71       V->push_back(NOld, Ctx);
  72       V->push_back(N, Ctx);
  73       P = reinterpret_cast<uintptr_t>(V) | SizeOther;
  74       assert(getPtr() == (void*) V);
  75       assert(getKind() == SizeOther);
  76     }
  77     else {
  78       P = reinterpret_cast<uintptr_t>(N);
  79       assert(getKind() == Size1);
  80     }
  81   }
  82   else {
  83     assert(getKind() == SizeOther);
  84     getVector(getPtr()).push_back(N, G.getNodeAllocator());
  85   }
  86 }
  87
  88 unsigned ExplodedNode::NodeGroup::size() const {
  89   if (getFlag())
  90     return 0;
  91
  92   if (getKind() == Size1)
  93     return getNode() ? 1 : 0;
  94   else
  95     return getVector(getPtr()).size();
  96 }
  97
  98 ExplodedNode **ExplodedNode::NodeGroup::begin() const {
  99   if (getFlag())
 100     return NULL;
 101
 102   if (getKind() == Size1)
 103     return (ExplodedNode**) (getPtr() ? &P : NULL);
 104   else
 105     return const_cast<ExplodedNode**>(&*(getVector(getPtr()).begin()));
 106 }
 107
 108 ExplodedNode** ExplodedNode::NodeGroup::end() const {
 109   if (getFlag())
 110     return NULL;
 111
 112   if (getKind() == Size1)
 113     return (ExplodedNode**) (getPtr() ? &P+1 : NULL);
 114   else {
 115     // Dereferencing end() is undefined behaviour. The vector is not empty, so
 116     // we can dereference the last elem and then add 1 to the result.
 117     return const_cast<ExplodedNode**>(getVector(getPtr()).end());
 118   }
 119 }
 120
 121 ExplodedNode *ExplodedGraph::getNode(const ProgramPoint& L,
 122                                      const GRState* State, bool* IsNew) {
 123   // Profile 'State' to determine if we already have an existing node.
 124   llvm::FoldingSetNodeID profile;
 125   void* InsertPos = 0;
 126
 127   NodeTy::Profile(profile, L, State);
 128   NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
 129
 130   if (!V) {
 131     // Allocate a new node.
 132     V = (NodeTy*) getAllocator().Allocate<NodeTy>();
 133     new (V) NodeTy(L, State);
 134
 135     // Insert the node into the node set and return it.
 136     Nodes.InsertNode(V, InsertPos);
 137
 138     ++NumNodes;
 139
 140     if (IsNew) *IsNew = true;
 141   }
 142   else
 143     if (IsNew) *IsNew = false;
 144
 145   return V;
 146 }
 147
 148 std::pair<ExplodedGraph*, InterExplodedGraphMap*>
 149 ExplodedGraph::Trim(const NodeTy* const* NBeg, const NodeTy* const* NEnd,
 150                llvm::DenseMap<const void*, const void*> *InverseMap) const {
 151
 152   if (NBeg == NEnd)
 153     return std::make_pair((ExplodedGraph*) 0,
 154                           (InterExplodedGraphMap*) 0);
 155
 156   assert (NBeg < NEnd);
 157
 158   llvm::OwningPtr<InterExplodedGraphMap> M(new InterExplodedGraphMap());
 159
 160   ExplodedGraph* G = TrimInternal(NBeg, NEnd, M.get(), InverseMap);
 161
 162   return std::make_pair(static_cast<ExplodedGraph*>(G), M.take());
 163 }
 164
 165 ExplodedGraph*
 166 ExplodedGraph::TrimInternal(const ExplodedNode* const* BeginSources,
 167                             const ExplodedNode* const* EndSources,
 168                             InterExplodedGraphMap* M,
 169                    llvm::DenseMap<const void*, const void*> *InverseMap) const {
 170
 171   typedef llvm::DenseSet<const ExplodedNode*> Pass1Ty;
 172   Pass1Ty Pass1;
 173
 174   typedef llvm::DenseMap<const ExplodedNode*, ExplodedNode*> Pass2Ty;
 175   Pass2Ty& Pass2 = M->M;
 176
 177   llvm::SmallVector<const ExplodedNode*, 10> WL1, WL2;
 178
 179   // ===- Pass 1 (reverse DFS) -===
 180   for (const ExplodedNode* const* I = BeginSources; I != EndSources; ++I) {
 181     assert(*I);
 182     WL1.push_back(*I);
 183   }
 184
 185   // Process the first worklist until it is empty.  Because it is a std::list
 186   // it acts like a FIFO queue.
 187   while (!WL1.empty()) {
 188     const ExplodedNode *N = WL1.back();
 189     WL1.pop_back();
 190
 191     // Have we already visited this node?  If so, continue to the next one.
 192     if (Pass1.count(N))
 193       continue;
 194
 195     // Otherwise, mark this node as visited.
 196     Pass1.insert(N);
 197
 198     // If this is a root enqueue it to the second worklist.
 199     if (N->Preds.empty()) {
 200       WL2.push_back(N);
 201       continue;
 202     }
 203
 204     // Visit our predecessors and enqueue them.
 205     for (ExplodedNode** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I)
 206       WL1.push_back(*I);
 207   }
 208
 209   // We didn't hit a root? Return with a null pointer for the new graph.
 210   if (WL2.empty())
 211     return 0;
 212
 213   // Create an empty graph.
 214   ExplodedGraph* G = MakeEmptyGraph();
 215
 216   // ===- Pass 2 (forward DFS to construct the new graph) -===
 217   while (!WL2.empty()) {
 218     const ExplodedNode* N = WL2.back();
 219     WL2.pop_back();
 220
 221     // Skip this node if we have already processed it.
 222     if (Pass2.find(N) != Pass2.end())
 223       continue;
 224
 225     // Create the corresponding node in the new graph and record the mapping
 226     // from the old node to the new node.
 227     ExplodedNode* NewN = G->getNode(N->getLocation(), N->State, NULL);
 228     Pass2[N] = NewN;
 229
 230     // Also record the reverse mapping from the new node to the old node.
 231     if (InverseMap) (*InverseMap)[NewN] = N;
 232
 233     // If this node is a root, designate it as such in the graph.
 234     if (N->Preds.empty())
 235       G->addRoot(NewN);
 236
 237     // In the case that some of the intended predecessors of NewN have already
 238     // been created, we should hook them up as predecessors.
 239
 240     // Walk through the predecessors of 'N' and hook up their corresponding
 241     // nodes in the new graph (if any) to the freshly created node.
 242     for (ExplodedNode **I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) {
 243       Pass2Ty::iterator PI = Pass2.find(*I);
 244       if (PI == Pass2.end())
 245         continue;
 246
 247       NewN->addPredecessor(PI->second, *G);
 248     }
 249
 250     // In the case that some of the intended successors of NewN have already
 251     // been created, we should hook them up as successors.  Otherwise, enqueue
 252     // the new nodes from the original graph that should have nodes created
 253     // in the new graph.
 254     for (ExplodedNode **I=N->Succs.begin(), **E=N->Succs.end(); I!=E; ++I) {
 255       Pass2Ty::iterator PI = Pass2.find(*I);
 256       if (PI != Pass2.end()) {
 257         PI->second->addPredecessor(NewN, *G);
 258         continue;
 259       }
 260
 261       // Enqueue nodes to the worklist that were marked during pass 1.
 262       if (Pass1.count(*I))
 263         WL2.push_back(*I);
 264     }
 265
 266     // Finally, explictly mark all nodes without any successors as sinks.
 267     if (N->isSink())
 268       NewN->markAsSink();
 269   }
 270
 271   return G;
 272 }
 273
 274 ExplodedNode*
 275 InterExplodedGraphMap::getMappedNode(const ExplodedNode* N) const {
 276   llvm::DenseMap<const ExplodedNode*, ExplodedNode*>::const_iterator I =
 277     M.find(N);
 278
 279   return I == M.end() ? 0 : I->second;
 280 }
 281