106f32e7eSjoerg //===- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -------------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This file defines the template classes ExplodedNode and ExplodedGraph,
1006f32e7eSjoerg // which represent a path-sensitive, intra-procedural "exploded graph."
1106f32e7eSjoerg //
1206f32e7eSjoerg //===----------------------------------------------------------------------===//
1306f32e7eSjoerg
1406f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
1506f32e7eSjoerg #include "clang/AST/Expr.h"
1606f32e7eSjoerg #include "clang/AST/ExprObjC.h"
1706f32e7eSjoerg #include "clang/AST/ParentMap.h"
1806f32e7eSjoerg #include "clang/AST/Stmt.h"
1906f32e7eSjoerg #include "clang/Analysis/CFGStmtMap.h"
2006f32e7eSjoerg #include "clang/Analysis/ProgramPoint.h"
2106f32e7eSjoerg #include "clang/Analysis/Support/BumpVector.h"
2206f32e7eSjoerg #include "clang/Basic/LLVM.h"
2306f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
2406f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
2506f32e7eSjoerg #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
2606f32e7eSjoerg #include "llvm/ADT/DenseSet.h"
2706f32e7eSjoerg #include "llvm/ADT/FoldingSet.h"
2806f32e7eSjoerg #include "llvm/ADT/Optional.h"
2906f32e7eSjoerg #include "llvm/ADT/PointerUnion.h"
3006f32e7eSjoerg #include "llvm/ADT/SmallVector.h"
3106f32e7eSjoerg #include "llvm/Support/Casting.h"
3206f32e7eSjoerg #include <cassert>
3306f32e7eSjoerg #include <memory>
3406f32e7eSjoerg
3506f32e7eSjoerg using namespace clang;
3606f32e7eSjoerg using namespace ento;
3706f32e7eSjoerg
3806f32e7eSjoerg //===----------------------------------------------------------------------===//
3906f32e7eSjoerg // Cleanup.
4006f32e7eSjoerg //===----------------------------------------------------------------------===//
4106f32e7eSjoerg
4206f32e7eSjoerg ExplodedGraph::ExplodedGraph() = default;
4306f32e7eSjoerg
4406f32e7eSjoerg ExplodedGraph::~ExplodedGraph() = default;
4506f32e7eSjoerg
4606f32e7eSjoerg //===----------------------------------------------------------------------===//
4706f32e7eSjoerg // Node reclamation.
4806f32e7eSjoerg //===----------------------------------------------------------------------===//
4906f32e7eSjoerg
isInterestingLValueExpr(const Expr * Ex)5006f32e7eSjoerg bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) {
5106f32e7eSjoerg if (!Ex->isLValue())
5206f32e7eSjoerg return false;
53*13fbcb42Sjoerg return isa<DeclRefExpr>(Ex) || isa<MemberExpr>(Ex) ||
54*13fbcb42Sjoerg isa<ObjCIvarRefExpr>(Ex) || isa<ArraySubscriptExpr>(Ex);
5506f32e7eSjoerg }
5606f32e7eSjoerg
shouldCollect(const ExplodedNode * node)5706f32e7eSjoerg bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
5806f32e7eSjoerg // First, we only consider nodes for reclamation of the following
5906f32e7eSjoerg // conditions apply:
6006f32e7eSjoerg //
6106f32e7eSjoerg // (1) 1 predecessor (that has one successor)
6206f32e7eSjoerg // (2) 1 successor (that has one predecessor)
6306f32e7eSjoerg //
6406f32e7eSjoerg // If a node has no successor it is on the "frontier", while a node
6506f32e7eSjoerg // with no predecessor is a root.
6606f32e7eSjoerg //
6706f32e7eSjoerg // After these prerequisites, we discard all "filler" nodes that
6806f32e7eSjoerg // are used only for intermediate processing, and are not essential
6906f32e7eSjoerg // for analyzer history:
7006f32e7eSjoerg //
7106f32e7eSjoerg // (a) PreStmtPurgeDeadSymbols
7206f32e7eSjoerg //
7306f32e7eSjoerg // We then discard all other nodes where *all* of the following conditions
7406f32e7eSjoerg // apply:
7506f32e7eSjoerg //
7606f32e7eSjoerg // (3) The ProgramPoint is for a PostStmt, but not a PostStore.
7706f32e7eSjoerg // (4) There is no 'tag' for the ProgramPoint.
7806f32e7eSjoerg // (5) The 'store' is the same as the predecessor.
7906f32e7eSjoerg // (6) The 'GDM' is the same as the predecessor.
8006f32e7eSjoerg // (7) The LocationContext is the same as the predecessor.
8106f32e7eSjoerg // (8) Expressions that are *not* lvalue expressions.
8206f32e7eSjoerg // (9) The PostStmt isn't for a non-consumed Stmt or Expr.
8306f32e7eSjoerg // (10) The successor is neither a CallExpr StmtPoint nor a CallEnter or
8406f32e7eSjoerg // PreImplicitCall (so that we would be able to find it when retrying a
8506f32e7eSjoerg // call with no inlining).
8606f32e7eSjoerg // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well.
8706f32e7eSjoerg
8806f32e7eSjoerg // Conditions 1 and 2.
8906f32e7eSjoerg if (node->pred_size() != 1 || node->succ_size() != 1)
9006f32e7eSjoerg return false;
9106f32e7eSjoerg
9206f32e7eSjoerg const ExplodedNode *pred = *(node->pred_begin());
9306f32e7eSjoerg if (pred->succ_size() != 1)
9406f32e7eSjoerg return false;
9506f32e7eSjoerg
9606f32e7eSjoerg const ExplodedNode *succ = *(node->succ_begin());
9706f32e7eSjoerg if (succ->pred_size() != 1)
9806f32e7eSjoerg return false;
9906f32e7eSjoerg
10006f32e7eSjoerg // Now reclaim any nodes that are (by definition) not essential to
10106f32e7eSjoerg // analysis history and are not consulted by any client code.
10206f32e7eSjoerg ProgramPoint progPoint = node->getLocation();
10306f32e7eSjoerg if (progPoint.getAs<PreStmtPurgeDeadSymbols>())
10406f32e7eSjoerg return !progPoint.getTag();
10506f32e7eSjoerg
10606f32e7eSjoerg // Condition 3.
10706f32e7eSjoerg if (!progPoint.getAs<PostStmt>() || progPoint.getAs<PostStore>())
10806f32e7eSjoerg return false;
10906f32e7eSjoerg
11006f32e7eSjoerg // Condition 4.
11106f32e7eSjoerg if (progPoint.getTag())
11206f32e7eSjoerg return false;
11306f32e7eSjoerg
11406f32e7eSjoerg // Conditions 5, 6, and 7.
11506f32e7eSjoerg ProgramStateRef state = node->getState();
11606f32e7eSjoerg ProgramStateRef pred_state = pred->getState();
11706f32e7eSjoerg if (state->store != pred_state->store || state->GDM != pred_state->GDM ||
11806f32e7eSjoerg progPoint.getLocationContext() != pred->getLocationContext())
11906f32e7eSjoerg return false;
12006f32e7eSjoerg
12106f32e7eSjoerg // All further checks require expressions. As per #3, we know that we have
12206f32e7eSjoerg // a PostStmt.
12306f32e7eSjoerg const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt());
12406f32e7eSjoerg if (!Ex)
12506f32e7eSjoerg return false;
12606f32e7eSjoerg
12706f32e7eSjoerg // Condition 8.
12806f32e7eSjoerg // Do not collect nodes for "interesting" lvalue expressions since they are
12906f32e7eSjoerg // used extensively for generating path diagnostics.
13006f32e7eSjoerg if (isInterestingLValueExpr(Ex))
13106f32e7eSjoerg return false;
13206f32e7eSjoerg
13306f32e7eSjoerg // Condition 9.
13406f32e7eSjoerg // Do not collect nodes for non-consumed Stmt or Expr to ensure precise
13506f32e7eSjoerg // diagnostic generation; specifically, so that we could anchor arrows
13606f32e7eSjoerg // pointing to the beginning of statements (as written in code).
13706f32e7eSjoerg const ParentMap &PM = progPoint.getLocationContext()->getParentMap();
13806f32e7eSjoerg if (!PM.isConsumedExpr(Ex))
13906f32e7eSjoerg return false;
14006f32e7eSjoerg
14106f32e7eSjoerg // Condition 10.
14206f32e7eSjoerg const ProgramPoint SuccLoc = succ->getLocation();
14306f32e7eSjoerg if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>())
14406f32e7eSjoerg if (CallEvent::isCallStmt(SP->getStmt()))
14506f32e7eSjoerg return false;
14606f32e7eSjoerg
14706f32e7eSjoerg // Condition 10, continuation.
14806f32e7eSjoerg if (SuccLoc.getAs<CallEnter>() || SuccLoc.getAs<PreImplicitCall>())
14906f32e7eSjoerg return false;
15006f32e7eSjoerg
15106f32e7eSjoerg return true;
15206f32e7eSjoerg }
15306f32e7eSjoerg
collectNode(ExplodedNode * node)15406f32e7eSjoerg void ExplodedGraph::collectNode(ExplodedNode *node) {
15506f32e7eSjoerg // Removing a node means:
15606f32e7eSjoerg // (a) changing the predecessors successor to the successor of this node
15706f32e7eSjoerg // (b) changing the successors predecessor to the predecessor of this node
15806f32e7eSjoerg // (c) Putting 'node' onto freeNodes.
15906f32e7eSjoerg assert(node->pred_size() == 1 || node->succ_size() == 1);
16006f32e7eSjoerg ExplodedNode *pred = *(node->pred_begin());
16106f32e7eSjoerg ExplodedNode *succ = *(node->succ_begin());
16206f32e7eSjoerg pred->replaceSuccessor(succ);
16306f32e7eSjoerg succ->replacePredecessor(pred);
16406f32e7eSjoerg FreeNodes.push_back(node);
16506f32e7eSjoerg Nodes.RemoveNode(node);
16606f32e7eSjoerg --NumNodes;
16706f32e7eSjoerg node->~ExplodedNode();
16806f32e7eSjoerg }
16906f32e7eSjoerg
reclaimRecentlyAllocatedNodes()17006f32e7eSjoerg void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
17106f32e7eSjoerg if (ChangedNodes.empty())
17206f32e7eSjoerg return;
17306f32e7eSjoerg
17406f32e7eSjoerg // Only periodically reclaim nodes so that we can build up a set of
17506f32e7eSjoerg // nodes that meet the reclamation criteria. Freshly created nodes
17606f32e7eSjoerg // by definition have no successor, and thus cannot be reclaimed (see below).
17706f32e7eSjoerg assert(ReclaimCounter > 0);
17806f32e7eSjoerg if (--ReclaimCounter != 0)
17906f32e7eSjoerg return;
18006f32e7eSjoerg ReclaimCounter = ReclaimNodeInterval;
18106f32e7eSjoerg
18206f32e7eSjoerg for (const auto node : ChangedNodes)
18306f32e7eSjoerg if (shouldCollect(node))
18406f32e7eSjoerg collectNode(node);
18506f32e7eSjoerg ChangedNodes.clear();
18606f32e7eSjoerg }
18706f32e7eSjoerg
18806f32e7eSjoerg //===----------------------------------------------------------------------===//
18906f32e7eSjoerg // ExplodedNode.
19006f32e7eSjoerg //===----------------------------------------------------------------------===//
19106f32e7eSjoerg
19206f32e7eSjoerg // An NodeGroup's storage type is actually very much like a TinyPtrVector:
19306f32e7eSjoerg // it can be either a pointer to a single ExplodedNode, or a pointer to a
19406f32e7eSjoerg // BumpVector allocated with the ExplodedGraph's allocator. This allows the
19506f32e7eSjoerg // common case of single-node NodeGroups to be implemented with no extra memory.
19606f32e7eSjoerg //
19706f32e7eSjoerg // Consequently, each of the NodeGroup methods have up to four cases to handle:
19806f32e7eSjoerg // 1. The flag is set and this group does not actually contain any nodes.
19906f32e7eSjoerg // 2. The group is empty, in which case the storage value is null.
20006f32e7eSjoerg // 3. The group contains a single node.
20106f32e7eSjoerg // 4. The group contains more than one node.
20206f32e7eSjoerg using ExplodedNodeVector = BumpVector<ExplodedNode *>;
20306f32e7eSjoerg using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;
20406f32e7eSjoerg
addPredecessor(ExplodedNode * V,ExplodedGraph & G)20506f32e7eSjoerg void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
20606f32e7eSjoerg assert(!V->isSink());
20706f32e7eSjoerg Preds.addNode(V, G);
20806f32e7eSjoerg V->Succs.addNode(this, G);
20906f32e7eSjoerg }
21006f32e7eSjoerg
replaceNode(ExplodedNode * node)21106f32e7eSjoerg void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
21206f32e7eSjoerg assert(!getFlag());
21306f32e7eSjoerg
21406f32e7eSjoerg GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
21506f32e7eSjoerg assert(Storage.is<ExplodedNode *>());
21606f32e7eSjoerg Storage = node;
21706f32e7eSjoerg assert(Storage.is<ExplodedNode *>());
21806f32e7eSjoerg }
21906f32e7eSjoerg
addNode(ExplodedNode * N,ExplodedGraph & G)22006f32e7eSjoerg void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
22106f32e7eSjoerg assert(!getFlag());
22206f32e7eSjoerg
22306f32e7eSjoerg GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
22406f32e7eSjoerg if (Storage.isNull()) {
22506f32e7eSjoerg Storage = N;
22606f32e7eSjoerg assert(Storage.is<ExplodedNode *>());
22706f32e7eSjoerg return;
22806f32e7eSjoerg }
22906f32e7eSjoerg
23006f32e7eSjoerg ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>();
23106f32e7eSjoerg
23206f32e7eSjoerg if (!V) {
23306f32e7eSjoerg // Switch from single-node to multi-node representation.
23406f32e7eSjoerg ExplodedNode *Old = Storage.get<ExplodedNode *>();
23506f32e7eSjoerg
23606f32e7eSjoerg BumpVectorContext &Ctx = G.getNodeAllocator();
23706f32e7eSjoerg V = G.getAllocator().Allocate<ExplodedNodeVector>();
23806f32e7eSjoerg new (V) ExplodedNodeVector(Ctx, 4);
23906f32e7eSjoerg V->push_back(Old, Ctx);
24006f32e7eSjoerg
24106f32e7eSjoerg Storage = V;
24206f32e7eSjoerg assert(!getFlag());
24306f32e7eSjoerg assert(Storage.is<ExplodedNodeVector *>());
24406f32e7eSjoerg }
24506f32e7eSjoerg
24606f32e7eSjoerg V->push_back(N, G.getNodeAllocator());
24706f32e7eSjoerg }
24806f32e7eSjoerg
size() const24906f32e7eSjoerg unsigned ExplodedNode::NodeGroup::size() const {
25006f32e7eSjoerg if (getFlag())
25106f32e7eSjoerg return 0;
25206f32e7eSjoerg
25306f32e7eSjoerg const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
25406f32e7eSjoerg if (Storage.isNull())
25506f32e7eSjoerg return 0;
25606f32e7eSjoerg if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
25706f32e7eSjoerg return V->size();
25806f32e7eSjoerg return 1;
25906f32e7eSjoerg }
26006f32e7eSjoerg
begin() const26106f32e7eSjoerg ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {
26206f32e7eSjoerg if (getFlag())
26306f32e7eSjoerg return nullptr;
26406f32e7eSjoerg
26506f32e7eSjoerg const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
26606f32e7eSjoerg if (Storage.isNull())
26706f32e7eSjoerg return nullptr;
26806f32e7eSjoerg if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
26906f32e7eSjoerg return V->begin();
27006f32e7eSjoerg return Storage.getAddrOfPtr1();
27106f32e7eSjoerg }
27206f32e7eSjoerg
end() const27306f32e7eSjoerg ExplodedNode * const *ExplodedNode::NodeGroup::end() const {
27406f32e7eSjoerg if (getFlag())
27506f32e7eSjoerg return nullptr;
27606f32e7eSjoerg
27706f32e7eSjoerg const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
27806f32e7eSjoerg if (Storage.isNull())
27906f32e7eSjoerg return nullptr;
28006f32e7eSjoerg if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
28106f32e7eSjoerg return V->end();
28206f32e7eSjoerg return Storage.getAddrOfPtr1() + 1;
28306f32e7eSjoerg }
28406f32e7eSjoerg
isTrivial() const28506f32e7eSjoerg bool ExplodedNode::isTrivial() const {
28606f32e7eSjoerg return pred_size() == 1 && succ_size() == 1 &&
28706f32e7eSjoerg getFirstPred()->getState()->getID() == getState()->getID() &&
28806f32e7eSjoerg getFirstPred()->succ_size() == 1;
28906f32e7eSjoerg }
29006f32e7eSjoerg
getCFGBlock() const29106f32e7eSjoerg const CFGBlock *ExplodedNode::getCFGBlock() const {
29206f32e7eSjoerg ProgramPoint P = getLocation();
29306f32e7eSjoerg if (auto BEP = P.getAs<BlockEntrance>())
29406f32e7eSjoerg return BEP->getBlock();
29506f32e7eSjoerg
29606f32e7eSjoerg // Find the node's current statement in the CFG.
29706f32e7eSjoerg // FIXME: getStmtForDiagnostics() does nasty things in order to provide
29806f32e7eSjoerg // a valid statement for body farms, do we need this behavior here?
29906f32e7eSjoerg if (const Stmt *S = getStmtForDiagnostics())
30006f32e7eSjoerg return getLocationContext()
30106f32e7eSjoerg ->getAnalysisDeclContext()
30206f32e7eSjoerg ->getCFGStmtMap()
30306f32e7eSjoerg ->getBlock(S);
30406f32e7eSjoerg
30506f32e7eSjoerg return nullptr;
30606f32e7eSjoerg }
30706f32e7eSjoerg
30806f32e7eSjoerg static const LocationContext *
findTopAutosynthesizedParentContext(const LocationContext * LC)30906f32e7eSjoerg findTopAutosynthesizedParentContext(const LocationContext *LC) {
31006f32e7eSjoerg assert(LC->getAnalysisDeclContext()->isBodyAutosynthesized());
31106f32e7eSjoerg const LocationContext *ParentLC = LC->getParent();
31206f32e7eSjoerg assert(ParentLC && "We don't start analysis from autosynthesized code");
31306f32e7eSjoerg while (ParentLC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
31406f32e7eSjoerg LC = ParentLC;
31506f32e7eSjoerg ParentLC = LC->getParent();
31606f32e7eSjoerg assert(ParentLC && "We don't start analysis from autosynthesized code");
31706f32e7eSjoerg }
31806f32e7eSjoerg return LC;
31906f32e7eSjoerg }
32006f32e7eSjoerg
getStmtForDiagnostics() const32106f32e7eSjoerg const Stmt *ExplodedNode::getStmtForDiagnostics() const {
32206f32e7eSjoerg // We cannot place diagnostics on autosynthesized code.
32306f32e7eSjoerg // Put them onto the call site through which we jumped into autosynthesized
32406f32e7eSjoerg // code for the first time.
32506f32e7eSjoerg const LocationContext *LC = getLocationContext();
32606f32e7eSjoerg if (LC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
32706f32e7eSjoerg // It must be a stack frame because we only autosynthesize functions.
32806f32e7eSjoerg return cast<StackFrameContext>(findTopAutosynthesizedParentContext(LC))
32906f32e7eSjoerg ->getCallSite();
33006f32e7eSjoerg }
33106f32e7eSjoerg // Otherwise, see if the node's program point directly points to a statement.
33206f32e7eSjoerg // FIXME: Refactor into a ProgramPoint method?
33306f32e7eSjoerg ProgramPoint P = getLocation();
33406f32e7eSjoerg if (auto SP = P.getAs<StmtPoint>())
33506f32e7eSjoerg return SP->getStmt();
33606f32e7eSjoerg if (auto BE = P.getAs<BlockEdge>())
33706f32e7eSjoerg return BE->getSrc()->getTerminatorStmt();
33806f32e7eSjoerg if (auto CE = P.getAs<CallEnter>())
33906f32e7eSjoerg return CE->getCallExpr();
34006f32e7eSjoerg if (auto CEE = P.getAs<CallExitEnd>())
34106f32e7eSjoerg return CEE->getCalleeContext()->getCallSite();
34206f32e7eSjoerg if (auto PIPP = P.getAs<PostInitializer>())
34306f32e7eSjoerg return PIPP->getInitializer()->getInit();
34406f32e7eSjoerg if (auto CEB = P.getAs<CallExitBegin>())
34506f32e7eSjoerg return CEB->getReturnStmt();
34606f32e7eSjoerg if (auto FEP = P.getAs<FunctionExitPoint>())
34706f32e7eSjoerg return FEP->getStmt();
34806f32e7eSjoerg
34906f32e7eSjoerg return nullptr;
35006f32e7eSjoerg }
35106f32e7eSjoerg
getNextStmtForDiagnostics() const35206f32e7eSjoerg const Stmt *ExplodedNode::getNextStmtForDiagnostics() const {
35306f32e7eSjoerg for (const ExplodedNode *N = getFirstSucc(); N; N = N->getFirstSucc()) {
35406f32e7eSjoerg if (const Stmt *S = N->getStmtForDiagnostics()) {
35506f32e7eSjoerg // Check if the statement is '?' or '&&'/'||'. These are "merges",
35606f32e7eSjoerg // not actual statement points.
35706f32e7eSjoerg switch (S->getStmtClass()) {
35806f32e7eSjoerg case Stmt::ChooseExprClass:
35906f32e7eSjoerg case Stmt::BinaryConditionalOperatorClass:
36006f32e7eSjoerg case Stmt::ConditionalOperatorClass:
36106f32e7eSjoerg continue;
36206f32e7eSjoerg case Stmt::BinaryOperatorClass: {
36306f32e7eSjoerg BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
36406f32e7eSjoerg if (Op == BO_LAnd || Op == BO_LOr)
36506f32e7eSjoerg continue;
36606f32e7eSjoerg break;
36706f32e7eSjoerg }
36806f32e7eSjoerg default:
36906f32e7eSjoerg break;
37006f32e7eSjoerg }
37106f32e7eSjoerg // We found the statement, so return it.
37206f32e7eSjoerg return S;
37306f32e7eSjoerg }
37406f32e7eSjoerg }
37506f32e7eSjoerg
37606f32e7eSjoerg return nullptr;
37706f32e7eSjoerg }
37806f32e7eSjoerg
getPreviousStmtForDiagnostics() const37906f32e7eSjoerg const Stmt *ExplodedNode::getPreviousStmtForDiagnostics() const {
38006f32e7eSjoerg for (const ExplodedNode *N = getFirstPred(); N; N = N->getFirstPred())
38106f32e7eSjoerg if (const Stmt *S = N->getStmtForDiagnostics())
38206f32e7eSjoerg return S;
38306f32e7eSjoerg
38406f32e7eSjoerg return nullptr;
38506f32e7eSjoerg }
38606f32e7eSjoerg
getCurrentOrPreviousStmtForDiagnostics() const38706f32e7eSjoerg const Stmt *ExplodedNode::getCurrentOrPreviousStmtForDiagnostics() const {
38806f32e7eSjoerg if (const Stmt *S = getStmtForDiagnostics())
38906f32e7eSjoerg return S;
39006f32e7eSjoerg
39106f32e7eSjoerg return getPreviousStmtForDiagnostics();
39206f32e7eSjoerg }
39306f32e7eSjoerg
getNode(const ProgramPoint & L,ProgramStateRef State,bool IsSink,bool * IsNew)39406f32e7eSjoerg ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
39506f32e7eSjoerg ProgramStateRef State,
39606f32e7eSjoerg bool IsSink,
39706f32e7eSjoerg bool* IsNew) {
39806f32e7eSjoerg // Profile 'State' to determine if we already have an existing node.
39906f32e7eSjoerg llvm::FoldingSetNodeID profile;
40006f32e7eSjoerg void *InsertPos = nullptr;
40106f32e7eSjoerg
40206f32e7eSjoerg NodeTy::Profile(profile, L, State, IsSink);
40306f32e7eSjoerg NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
40406f32e7eSjoerg
40506f32e7eSjoerg if (!V) {
40606f32e7eSjoerg if (!FreeNodes.empty()) {
40706f32e7eSjoerg V = FreeNodes.back();
40806f32e7eSjoerg FreeNodes.pop_back();
40906f32e7eSjoerg }
41006f32e7eSjoerg else {
41106f32e7eSjoerg // Allocate a new node.
41206f32e7eSjoerg V = (NodeTy*) getAllocator().Allocate<NodeTy>();
41306f32e7eSjoerg }
41406f32e7eSjoerg
41506f32e7eSjoerg ++NumNodes;
41606f32e7eSjoerg new (V) NodeTy(L, State, NumNodes, IsSink);
41706f32e7eSjoerg
41806f32e7eSjoerg if (ReclaimNodeInterval)
41906f32e7eSjoerg ChangedNodes.push_back(V);
42006f32e7eSjoerg
42106f32e7eSjoerg // Insert the node into the node set and return it.
42206f32e7eSjoerg Nodes.InsertNode(V, InsertPos);
42306f32e7eSjoerg
42406f32e7eSjoerg if (IsNew) *IsNew = true;
42506f32e7eSjoerg }
42606f32e7eSjoerg else
42706f32e7eSjoerg if (IsNew) *IsNew = false;
42806f32e7eSjoerg
42906f32e7eSjoerg return V;
43006f32e7eSjoerg }
43106f32e7eSjoerg
createUncachedNode(const ProgramPoint & L,ProgramStateRef State,int64_t Id,bool IsSink)43206f32e7eSjoerg ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
43306f32e7eSjoerg ProgramStateRef State,
43406f32e7eSjoerg int64_t Id,
43506f32e7eSjoerg bool IsSink) {
43606f32e7eSjoerg NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
43706f32e7eSjoerg new (V) NodeTy(L, State, Id, IsSink);
43806f32e7eSjoerg return V;
43906f32e7eSjoerg }
44006f32e7eSjoerg
44106f32e7eSjoerg std::unique_ptr<ExplodedGraph>
trim(ArrayRef<const NodeTy * > Sinks,InterExplodedGraphMap * ForwardMap,InterExplodedGraphMap * InverseMap) const44206f32e7eSjoerg ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
44306f32e7eSjoerg InterExplodedGraphMap *ForwardMap,
44406f32e7eSjoerg InterExplodedGraphMap *InverseMap) const {
44506f32e7eSjoerg if (Nodes.empty())
44606f32e7eSjoerg return nullptr;
44706f32e7eSjoerg
44806f32e7eSjoerg using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;
44906f32e7eSjoerg Pass1Ty Pass1;
45006f32e7eSjoerg
45106f32e7eSjoerg using Pass2Ty = InterExplodedGraphMap;
45206f32e7eSjoerg InterExplodedGraphMap Pass2Scratch;
45306f32e7eSjoerg Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
45406f32e7eSjoerg
45506f32e7eSjoerg SmallVector<const ExplodedNode*, 10> WL1, WL2;
45606f32e7eSjoerg
45706f32e7eSjoerg // ===- Pass 1 (reverse DFS) -===
45806f32e7eSjoerg for (const auto Sink : Sinks)
45906f32e7eSjoerg if (Sink)
46006f32e7eSjoerg WL1.push_back(Sink);
46106f32e7eSjoerg
46206f32e7eSjoerg // Process the first worklist until it is empty.
46306f32e7eSjoerg while (!WL1.empty()) {
46406f32e7eSjoerg const ExplodedNode *N = WL1.pop_back_val();
46506f32e7eSjoerg
46606f32e7eSjoerg // Have we already visited this node? If so, continue to the next one.
46706f32e7eSjoerg if (!Pass1.insert(N).second)
46806f32e7eSjoerg continue;
46906f32e7eSjoerg
47006f32e7eSjoerg // If this is a root enqueue it to the second worklist.
47106f32e7eSjoerg if (N->Preds.empty()) {
47206f32e7eSjoerg WL2.push_back(N);
47306f32e7eSjoerg continue;
47406f32e7eSjoerg }
47506f32e7eSjoerg
47606f32e7eSjoerg // Visit our predecessors and enqueue them.
47706f32e7eSjoerg WL1.append(N->Preds.begin(), N->Preds.end());
47806f32e7eSjoerg }
47906f32e7eSjoerg
48006f32e7eSjoerg // We didn't hit a root? Return with a null pointer for the new graph.
48106f32e7eSjoerg if (WL2.empty())
48206f32e7eSjoerg return nullptr;
48306f32e7eSjoerg
48406f32e7eSjoerg // Create an empty graph.
48506f32e7eSjoerg std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
48606f32e7eSjoerg
48706f32e7eSjoerg // ===- Pass 2 (forward DFS to construct the new graph) -===
48806f32e7eSjoerg while (!WL2.empty()) {
48906f32e7eSjoerg const ExplodedNode *N = WL2.pop_back_val();
49006f32e7eSjoerg
49106f32e7eSjoerg // Skip this node if we have already processed it.
49206f32e7eSjoerg if (Pass2.find(N) != Pass2.end())
49306f32e7eSjoerg continue;
49406f32e7eSjoerg
49506f32e7eSjoerg // Create the corresponding node in the new graph and record the mapping
49606f32e7eSjoerg // from the old node to the new node.
49706f32e7eSjoerg ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State,
49806f32e7eSjoerg N->getID(), N->isSink());
49906f32e7eSjoerg Pass2[N] = NewN;
50006f32e7eSjoerg
50106f32e7eSjoerg // Also record the reverse mapping from the new node to the old node.
50206f32e7eSjoerg if (InverseMap) (*InverseMap)[NewN] = N;
50306f32e7eSjoerg
50406f32e7eSjoerg // If this node is a root, designate it as such in the graph.
50506f32e7eSjoerg if (N->Preds.empty())
50606f32e7eSjoerg G->addRoot(NewN);
50706f32e7eSjoerg
50806f32e7eSjoerg // In the case that some of the intended predecessors of NewN have already
50906f32e7eSjoerg // been created, we should hook them up as predecessors.
51006f32e7eSjoerg
51106f32e7eSjoerg // Walk through the predecessors of 'N' and hook up their corresponding
51206f32e7eSjoerg // nodes in the new graph (if any) to the freshly created node.
51306f32e7eSjoerg for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
51406f32e7eSjoerg I != E; ++I) {
51506f32e7eSjoerg Pass2Ty::iterator PI = Pass2.find(*I);
51606f32e7eSjoerg if (PI == Pass2.end())
51706f32e7eSjoerg continue;
51806f32e7eSjoerg
51906f32e7eSjoerg NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
52006f32e7eSjoerg }
52106f32e7eSjoerg
52206f32e7eSjoerg // In the case that some of the intended successors of NewN have already
52306f32e7eSjoerg // been created, we should hook them up as successors. Otherwise, enqueue
52406f32e7eSjoerg // the new nodes from the original graph that should have nodes created
52506f32e7eSjoerg // in the new graph.
52606f32e7eSjoerg for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
52706f32e7eSjoerg I != E; ++I) {
52806f32e7eSjoerg Pass2Ty::iterator PI = Pass2.find(*I);
52906f32e7eSjoerg if (PI != Pass2.end()) {
53006f32e7eSjoerg const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
53106f32e7eSjoerg continue;
53206f32e7eSjoerg }
53306f32e7eSjoerg
53406f32e7eSjoerg // Enqueue nodes to the worklist that were marked during pass 1.
53506f32e7eSjoerg if (Pass1.count(*I))
53606f32e7eSjoerg WL2.push_back(*I);
53706f32e7eSjoerg }
53806f32e7eSjoerg }
53906f32e7eSjoerg
54006f32e7eSjoerg return G;
54106f32e7eSjoerg }
542