Go to the documentation of this file.
26 #include "llvm/ADT/DenseSet.h"
27 #include "llvm/ADT/FoldingSet.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/ADT/PointerUnion.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/Support/Casting.h"
35 using namespace clang;
53 return isa<DeclRefExpr, MemberExpr, ObjCIvarRefExpr, ArraySubscriptExpr>(Ex);
88 if (
node->pred_size() != 1 ||
node->succ_size() != 1)
103 return !progPoint.
getTag();
116 if (
state->store != pred_state->store ||
state->GDM != pred_state->GDM ||
153 void ExplodedGraph::collectNode(ExplodedNode *
node) {
158 assert(
node->pred_size() == 1 ||
node->succ_size() == 1);
159 ExplodedNode *pred = *(
node->pred_begin());
160 ExplodedNode *succ = *(
node->succ_begin());
161 pred->replaceSuccessor(succ);
162 succ->replacePredecessor(pred);
166 node->~ExplodedNode();
182 if (shouldCollect(
node))
202 using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;
205 assert(!
V->isSink());
207 V->Succs.addNode(
this, G);
219 void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
223 if (Storage.isNull()) {
225 assert(Storage.is<ExplodedNode *>());
233 ExplodedNode *Old = Storage.get<ExplodedNode *>();
238 V->push_back(Old, Ctx);
245 V->push_back(N, G.getNodeAllocator());
248 unsigned ExplodedNode::NodeGroup::size()
const {
253 if (Storage.isNull())
260 ExplodedNode *
const *ExplodedNode::NodeGroup::begin()
const {
265 if (Storage.isNull())
269 return Storage.getAddrOfPtr1();
272 ExplodedNode *
const *ExplodedNode::NodeGroup::end()
const {
277 if (Storage.isNull())
281 return Storage.getAddrOfPtr1() + 1;
293 return BEP->getBlock();
311 assert(ParentLC &&
"We don't start analysis from autosynthesized code");
315 assert(ParentLC &&
"We don't start analysis from autosynthesized code");
334 return SP->getStmt();
336 return BE->getSrc()->getTerminatorStmt();
338 return CE->getCallExpr();
340 return CEE->getCalleeContext()->getCallSite();
342 return PIPP->getInitializer()->getInit();
344 return CEB->getReturnStmt();
346 return FEP->getStmt();
353 if (
const Stmt *S = N->getStmtForDiagnostics()) {
356 switch (S->getStmtClass()) {
357 case Stmt::ChooseExprClass:
358 case Stmt::BinaryConditionalOperatorClass:
359 case Stmt::ConditionalOperatorClass:
361 case Stmt::BinaryOperatorClass: {
363 if (Op == BO_LAnd || Op == BO_LOr)
380 if (
const Stmt *S = N->getStmtForDiagnostics())
398 llvm::FoldingSetNodeID profile;
399 void *InsertPos =
nullptr;
402 NodeTy*
V =
Nodes.FindNodeOrInsertPos(profile, InsertPos);
421 Nodes.InsertNode(
V, InsertPos);
423 if (IsNew) *IsNew =
true;
426 if (IsNew) *IsNew =
false;
440 std::unique_ptr<ExplodedGraph>
452 Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
457 for (
const auto Sink : Sinks)
462 while (!WL1.empty()) {
466 if (!Pass1.insert(N).second)
470 if (N->Preds.empty()) {
476 WL1.append(N->Preds.begin(), N->Preds.end());
487 while (!WL2.empty()) {
491 if (Pass2.find(N) != Pass2.end())
501 if (InverseMap) (*InverseMap)[NewN] = N;
504 if (N->Preds.empty())
514 Pass2Ty::iterator PI = Pass2.find(*I);
515 if (PI == Pass2.end())
527 Pass2Ty::iterator PI = Pass2.find(*I);
528 if (PI != Pass2.end()) {
529 const_cast<ExplodedNode *
>(PI->second)->addPredecessor(NewN, *G);
CFGStmtMap * getCFGStmtMap()
Represents a point when we start the call exit sequence (for inlined call).
ExplodedNode * createUncachedNode(const ProgramPoint &L, ProgramStateRef State, int64_t Id, bool IsSink=false)
Create a node for a (Location, State) pair, but don't store it for deduplication later.
const LocationContext * getLocationContext() const
llvm::PointerUnion< ExplodedNode *, ExplodedNodeVector * > GroupStorage
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
unsigned succ_size() const
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language.
bool isBodyAutosynthesized() const
llvm::FoldingSet< ExplodedNode > Nodes
Nodes - The nodes in the graph.
int64_t NumNodes
NumNodes - The number of nodes in the graph.
ExplodedNode *const * pred_iterator
static bool isCallStmt(const Stmt *S)
Returns true if this is a statement is a function or method call of some kind.
const LocationContext * getLocationContext() const
Represents a single basic block in a source-level CFG.
void reclaimRecentlyAllocatedNodes()
Reclaim "uninteresting" nodes created since the last time this method was called.
ExplodedNode *const * succ_iterator
ExplodedNode * getFirstSucc()
const ProgramStateRef & getState() const
const CFGBlock * getCFGBlock() const
ExplodedNode * getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)
Retrieve the node associated with a (Location,State) pair, where the 'Location' is a ProgramPoint in ...
AnalysisDeclContext * getAnalysisDeclContext() const
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
const ProgramPointTag * getTag() const
Represents a point when we finish the call exit sequence (for inlined call).
Represents a program point after a store evaluation.
CFGBlock * getBlock(Stmt *S)
Returns the CFGBlock the specified Stmt* appears in.
BumpVector< ExplodedNode * > ExplodedNodeVector
T castAs() const
Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type.
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
const Stmt * getPreviousStmtForDiagnostics() const
Find the statement that was executed immediately before this node.
unsigned ReclaimCounter
Counter to determine when to reclaim nodes.
const Stmt * getStmt() const
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
and static some checkers Checker The latter are built on top of the former via the Checker and CheckerVisitor and attempts to isolate them from much of the gore of the internal analysis the analyzer is basically a source code simulator that traces out possible paths of execution The state of the and the combination of state and program point is a node in an exploded which has the entry program point and initial state
unsigned pred_size() const
bool isTrivial() const
The node is trivial if it has only one successor, only one predecessor, it's predecessor has only one...
const LocationContext * getParent() const
static bool isInterestingLValueExpr(const Expr *Ex)
Returns true if nodes for the given expression kind are always kept around.
ExplodedNode * getFirstPred()
const Stmt * getNextStmtForDiagnostics() const
Find the next statement that was executed on this node's execution path.
std::unique_ptr< ExplodedGraph > trim(ArrayRef< const NodeTy * > Nodes, InterExplodedGraphMap *ForwardMap=nullptr, InterExplodedGraphMap *InverseMap=nullptr) const
Creates a trimmed version of the graph that only contains paths leading to the given nodes.
Represents a program point just before an implicit call event.
static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
Stmt - This represents one statement.
NodeVector FreeNodes
A list of nodes that can be reused.
const Stmt * getStmtForDiagnostics() const
If the node's program point corresponds to a statement, retrieve that statement.
static const LocationContext * findTopAutosynthesizedParentContext(const LocationContext *LC)
Represents a point when we begin processing an inlined call.
const Stmt * getCurrentOrPreviousStmtForDiagnostics() const
Find the statement that was executed at or immediately before this node.
llvm::BumpPtrAllocator & getAllocator()
bool isConsumedExpr(Expr *E) const
This represents one expression.
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
Represents a point after we ran remove dead bindings BEFORE processing the given statement.
const ParentMap & getParentMap() const