contrib/llvm-project/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

   1 //===- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file defines the template classes ExplodedNode and ExplodedGraph,
  10 //  which represent a path-sensitive, intra-procedural "exploded graph."
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  15 #include "clang/AST/Expr.h"
  16 #include "clang/AST/ExprObjC.h"
  17 #include "clang/AST/ParentMap.h"
  18 #include "clang/AST/Stmt.h"
  19 #include "clang/Analysis/ProgramPoint.h"
  20 #include "clang/Analysis/Support/BumpVector.h"
  21 #include "clang/Basic/LLVM.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  25 #include "llvm/ADT/DenseSet.h"
  26 #include "llvm/ADT/FoldingSet.h"
  27 #include "llvm/ADT/Optional.h"
  28 #include "llvm/ADT/PointerUnion.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/Support/Casting.h"
  31 #include <cassert>
  32 #include <memory>
  33
  34 using namespace clang;
  35 using namespace ento;
  36
  37 //===----------------------------------------------------------------------===//
  38 // Cleanup.
  39 //===----------------------------------------------------------------------===//
  40
  41 ExplodedGraph::ExplodedGraph() = default;
  42
  43 ExplodedGraph::~ExplodedGraph() = default;
  44
  45 //===----------------------------------------------------------------------===//
  46 // Node reclamation.
  47 //===----------------------------------------------------------------------===//
  48
  49 bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) {
  50   if (!Ex->isLValue())
  51     return false;
  52   return isa<DeclRefExpr>(Ex) ||
  53          isa<MemberExpr>(Ex) ||
  54          isa<ObjCIvarRefExpr>(Ex);
  55 }
  56
  57 bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
  58   // First, we only consider nodes for reclamation of the following
  59   // conditions apply:
  60   //
  61   // (1) 1 predecessor (that has one successor)
  62   // (2) 1 successor (that has one predecessor)
  63   //
  64   // If a node has no successor it is on the "frontier", while a node
  65   // with no predecessor is a root.
  66   //
  67   // After these prerequisites, we discard all "filler" nodes that
  68   // are used only for intermediate processing, and are not essential
  69   // for analyzer history:
  70   //
  71   // (a) PreStmtPurgeDeadSymbols
  72   //
  73   // We then discard all other nodes where *all* of the following conditions
  74   // apply:
  75   //
  76   // (3) The ProgramPoint is for a PostStmt, but not a PostStore.
  77   // (4) There is no 'tag' for the ProgramPoint.
  78   // (5) The 'store' is the same as the predecessor.
  79   // (6) The 'GDM' is the same as the predecessor.
  80   // (7) The LocationContext is the same as the predecessor.
  81   // (8) Expressions that are *not* lvalue expressions.
  82   // (9) The PostStmt isn't for a non-consumed Stmt or Expr.
  83   // (10) The successor is neither a CallExpr StmtPoint nor a CallEnter or
  84   //      PreImplicitCall (so that we would be able to find it when retrying a
  85   //      call with no inlining).
  86   // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well.
  87
  88   // Conditions 1 and 2.
  89   if (node->pred_size() != 1 || node->succ_size() != 1)
  90     return false;
  91
  92   const ExplodedNode *pred = *(node->pred_begin());
  93   if (pred->succ_size() != 1)
  94     return false;
  95
  96   const ExplodedNode *succ = *(node->succ_begin());
  97   if (succ->pred_size() != 1)
  98     return false;
  99
 100   // Now reclaim any nodes that are (by definition) not essential to
 101   // analysis history and are not consulted by any client code.
 102   ProgramPoint progPoint = node->getLocation();
 103   if (progPoint.getAs<PreStmtPurgeDeadSymbols>())
 104     return !progPoint.getTag();
 105
 106   // Condition 3.
 107   if (!progPoint.getAs<PostStmt>() || progPoint.getAs<PostStore>())
 108     return false;
 109
 110   // Condition 4.
 111   if (progPoint.getTag())
 112     return false;
 113
 114   // Conditions 5, 6, and 7.
 115   ProgramStateRef state = node->getState();
 116   ProgramStateRef pred_state = pred->getState();
 117   if (state->store != pred_state->store || state->GDM != pred_state->GDM ||
 118       progPoint.getLocationContext() != pred->getLocationContext())
 119     return false;
 120
 121   // All further checks require expressions. As per #3, we know that we have
 122   // a PostStmt.
 123   const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt());
 124   if (!Ex)
 125     return false;
 126
 127   // Condition 8.
 128   // Do not collect nodes for "interesting" lvalue expressions since they are
 129   // used extensively for generating path diagnostics.
 130   if (isInterestingLValueExpr(Ex))
 131     return false;
 132
 133   // Condition 9.
 134   // Do not collect nodes for non-consumed Stmt or Expr to ensure precise
 135   // diagnostic generation; specifically, so that we could anchor arrows
 136   // pointing to the beginning of statements (as written in code).
 137   ParentMap &PM = progPoint.getLocationContext()->getParentMap();
 138   if (!PM.isConsumedExpr(Ex))
 139     return false;
 140
 141   // Condition 10.
 142   const ProgramPoint SuccLoc = succ->getLocation();
 143   if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>())
 144     if (CallEvent::isCallStmt(SP->getStmt()))
 145       return false;
 146
 147   // Condition 10, continuation.
 148   if (SuccLoc.getAs<CallEnter>() || SuccLoc.getAs<PreImplicitCall>())
 149     return false;
 150
 151   return true;
 152 }
 153
 154 void ExplodedGraph::collectNode(ExplodedNode *node) {
 155   // Removing a node means:
 156   // (a) changing the predecessors successor to the successor of this node
 157   // (b) changing the successors predecessor to the predecessor of this node
 158   // (c) Putting 'node' onto freeNodes.
 159   assert(node->pred_size() == 1 || node->succ_size() == 1);
 160   ExplodedNode *pred = *(node->pred_begin());
 161   ExplodedNode *succ = *(node->succ_begin());
 162   pred->replaceSuccessor(succ);
 163   succ->replacePredecessor(pred);
 164   FreeNodes.push_back(node);
 165   Nodes.RemoveNode(node);
 166   --NumNodes;
 167   node->~ExplodedNode();
 168 }
 169
 170 void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
 171   if (ChangedNodes.empty())
 172     return;
 173
 174   // Only periodically reclaim nodes so that we can build up a set of
 175   // nodes that meet the reclamation criteria.  Freshly created nodes
 176   // by definition have no successor, and thus cannot be reclaimed (see below).
 177   assert(ReclaimCounter > 0);
 178   if (--ReclaimCounter != 0)
 179     return;
 180   ReclaimCounter = ReclaimNodeInterval;
 181
 182   for (const auto node : ChangedNodes)
 183     if (shouldCollect(node))
 184       collectNode(node);
 185   ChangedNodes.clear();
 186 }
 187
 188 //===----------------------------------------------------------------------===//
 189 // ExplodedNode.
 190 //===----------------------------------------------------------------------===//
 191
 192 // An NodeGroup's storage type is actually very much like a TinyPtrVector:
 193 // it can be either a pointer to a single ExplodedNode, or a pointer to a
 194 // BumpVector allocated with the ExplodedGraph's allocator. This allows the
 195 // common case of single-node NodeGroups to be implemented with no extra memory.
 196 //
 197 // Consequently, each of the NodeGroup methods have up to four cases to handle:
 198 // 1. The flag is set and this group does not actually contain any nodes.
 199 // 2. The group is empty, in which case the storage value is null.
 200 // 3. The group contains a single node.
 201 // 4. The group contains more than one node.
 202 using ExplodedNodeVector = BumpVector<ExplodedNode *>;
 203 using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;
 204
 205 void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
 206   assert(!V->isSink());
 207   Preds.addNode(V, G);
 208   V->Succs.addNode(this, G);
 209 }
 210
 211 void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
 212   assert(!getFlag());
 213
 214   GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
 215   assert(Storage.is<ExplodedNode *>());
 216   Storage = node;
 217   assert(Storage.is<ExplodedNode *>());
 218 }
 219
 220 void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
 221   assert(!getFlag());
 222
 223   GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
 224   if (Storage.isNull()) {
 225     Storage = N;
 226     assert(Storage.is<ExplodedNode *>());
 227     return;
 228   }
 229
 230   ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>();
 231
 232   if (!V) {
 233     // Switch from single-node to multi-node representation.
 234     ExplodedNode *Old = Storage.get<ExplodedNode *>();
 235
 236     BumpVectorContext &Ctx = G.getNodeAllocator();
 237     V = G.getAllocator().Allocate<ExplodedNodeVector>();
 238     new (V) ExplodedNodeVector(Ctx, 4);
 239     V->push_back(Old, Ctx);
 240
 241     Storage = V;
 242     assert(!getFlag());
 243     assert(Storage.is<ExplodedNodeVector *>());
 244   }
 245
 246   V->push_back(N, G.getNodeAllocator());
 247 }
 248
 249 unsigned ExplodedNode::NodeGroup::size() const {
 250   if (getFlag())
 251     return 0;
 252
 253   const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
 254   if (Storage.isNull())
 255     return 0;
 256   if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
 257     return V->size();
 258   return 1;
 259 }
 260
 261 ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {
 262   if (getFlag())
 263     return nullptr;
 264
 265   const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
 266   if (Storage.isNull())
 267     return nullptr;
 268   if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
 269     return V->begin();
 270   return Storage.getAddrOfPtr1();
 271 }
 272
 273 ExplodedNode * const *ExplodedNode::NodeGroup::end() const {
 274   if (getFlag())
 275     return nullptr;
 276
 277   const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
 278   if (Storage.isNull())
 279     return nullptr;
 280   if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
 281     return V->end();
 282   return Storage.getAddrOfPtr1() + 1;
 283 }
 284
 285 int64_t ExplodedNode::getID(ExplodedGraph *G) const {
 286   return G->getAllocator().identifyKnownAlignedObject<ExplodedNode>(this);
 287 }
 288
 289 bool ExplodedNode::isTrivial() const {
 290   return pred_size() == 1 && succ_size() == 1 &&
 291          getFirstPred()->getState()->getID() == getState()->getID() &&
 292          getFirstPred()->succ_size() == 1;
 293 }
 294
 295 ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
 296                                      ProgramStateRef State,
 297                                      bool IsSink,
 298                                      bool* IsNew) {
 299   // Profile 'State' to determine if we already have an existing node.
 300   llvm::FoldingSetNodeID profile;
 301   void *InsertPos = nullptr;
 302
 303   NodeTy::Profile(profile, L, State, IsSink);
 304   NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
 305
 306   if (!V) {
 307     if (!FreeNodes.empty()) {
 308       V = FreeNodes.back();
 309       FreeNodes.pop_back();
 310     }
 311     else {
 312       // Allocate a new node.
 313       V = (NodeTy*) getAllocator().Allocate<NodeTy>();
 314     }
 315
 316     new (V) NodeTy(L, State, IsSink);
 317
 318     if (ReclaimNodeInterval)
 319       ChangedNodes.push_back(V);
 320
 321     // Insert the node into the node set and return it.
 322     Nodes.InsertNode(V, InsertPos);
 323     ++NumNodes;
 324
 325     if (IsNew) *IsNew = true;
 326   }
 327   else
 328     if (IsNew) *IsNew = false;
 329
 330   return V;
 331 }
 332
 333 ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
 334                                                 ProgramStateRef State,
 335                                                 bool IsSink) {
 336   NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
 337   new (V) NodeTy(L, State, IsSink);
 338   return V;
 339 }
 340
 341 std::unique_ptr<ExplodedGraph>
 342 ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
 343                     InterExplodedGraphMap *ForwardMap,
 344                     InterExplodedGraphMap *InverseMap) const {
 345   if (Nodes.empty())
 346     return nullptr;
 347
 348   using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;
 349   Pass1Ty Pass1;
 350
 351   using Pass2Ty = InterExplodedGraphMap;
 352   InterExplodedGraphMap Pass2Scratch;
 353   Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
 354
 355   SmallVector<const ExplodedNode*, 10> WL1, WL2;
 356
 357   // ===- Pass 1 (reverse DFS) -===
 358   for (const auto Sink : Sinks)
 359     if (Sink)
 360       WL1.push_back(Sink);
 361
 362   // Process the first worklist until it is empty.
 363   while (!WL1.empty()) {
 364     const ExplodedNode *N = WL1.pop_back_val();
 365
 366     // Have we already visited this node?  If so, continue to the next one.
 367     if (!Pass1.insert(N).second)
 368       continue;
 369
 370     // If this is a root enqueue it to the second worklist.
 371     if (N->Preds.empty()) {
 372       WL2.push_back(N);
 373       continue;
 374     }
 375
 376     // Visit our predecessors and enqueue them.
 377     WL1.append(N->Preds.begin(), N->Preds.end());
 378   }
 379
 380   // We didn't hit a root? Return with a null pointer for the new graph.
 381   if (WL2.empty())
 382     return nullptr;
 383
 384   // Create an empty graph.
 385   std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
 386
 387   // ===- Pass 2 (forward DFS to construct the new graph) -===
 388   while (!WL2.empty()) {
 389     const ExplodedNode *N = WL2.pop_back_val();
 390
 391     // Skip this node if we have already processed it.
 392     if (Pass2.find(N) != Pass2.end())
 393       continue;
 394
 395     // Create the corresponding node in the new graph and record the mapping
 396     // from the old node to the new node.
 397     ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State, N->isSink());
 398     Pass2[N] = NewN;
 399
 400     // Also record the reverse mapping from the new node to the old node.
 401     if (InverseMap) (*InverseMap)[NewN] = N;
 402
 403     // If this node is a root, designate it as such in the graph.
 404     if (N->Preds.empty())
 405       G->addRoot(NewN);
 406
 407     // In the case that some of the intended predecessors of NewN have already
 408     // been created, we should hook them up as predecessors.
 409
 410     // Walk through the predecessors of 'N' and hook up their corresponding
 411     // nodes in the new graph (if any) to the freshly created node.
 412     for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
 413          I != E; ++I) {
 414       Pass2Ty::iterator PI = Pass2.find(*I);
 415       if (PI == Pass2.end())
 416         continue;
 417
 418       NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
 419     }
 420
 421     // In the case that some of the intended successors of NewN have already
 422     // been created, we should hook them up as successors.  Otherwise, enqueue
 423     // the new nodes from the original graph that should have nodes created
 424     // in the new graph.
 425     for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
 426          I != E; ++I) {
 427       Pass2Ty::iterator PI = Pass2.find(*I);
 428       if (PI != Pass2.end()) {
 429         const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
 430         continue;
 431       }
 432
 433       // Enqueue nodes to the worklist that were marked during pass 1.
 434       if (Pass1.count(*I))
 435         WL2.push_back(*I);
 436     }
 437   }
 438
 439   return G;
 440 }