26#include "llvm/ADT/DenseSet.h"
27#include "llvm/ADT/FoldingSet.h"
28#include "llvm/ADT/PointerUnion.h"
29#include "llvm/ADT/SmallVector.h"
30#include "llvm/Support/Casting.h"
53 return isa<DeclRefExpr, MemberExpr, ObjCIvarRefExpr, ArraySubscriptExpr>(Ex);
56bool ExplodedGraph::shouldCollect(
const ExplodedNode *node) {
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 ||
158 assert(node->pred_size() == 1 || node->succ_size() == 1);
161 pred->replaceSuccessor(succ);
162 succ->replacePredecessor(pred);
164 Nodes.RemoveNode(node);
166 node->~ExplodedNode();
182 if (shouldCollect(node))
202using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;
205 assert(!
V->isSink());
207 V->Succs.addNode(
this, G);
210void ExplodedNode::NodeGroup::replaceNode(
ExplodedNode *node) {
223 if (Storage.isNull()) {
238 V->push_back(Old, Ctx);
248unsigned ExplodedNode::NodeGroup::size()
const {
253 if (Storage.isNull())
260ExplodedNode *
const *ExplodedNode::NodeGroup::begin()
const {
265 if (Storage.isNull())
269 return Storage.getAddrOfPtr1();
272ExplodedNode *
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();
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)
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;
440std::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.contains(N))
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);
llvm::PointerUnion< ExplodedNode *, ExplodedNodeVector * > GroupStorage
BumpVector< ExplodedNode * > ExplodedNodeVector
static const LocationContext * findTopAutosynthesizedParentContext(const LocationContext *LC)
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
CFGStmtMap * getCFGStmtMap()
bool isBodyAutosynthesized() const
Represents a single basic block in a source-level CFG.
CFGBlock * getBlock(Stmt *S)
Returns the CFGBlock the specified Stmt* appears in.
Represents a point when we begin processing an inlined call.
Represents a point when we start the call exit sequence (for inlined call).
Represents a point when we finish the call exit sequence (for inlined call).
This represents one expression.
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language.
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const ParentMap & getParentMap() const
LLVM_ATTRIBUTE_RETURNS_NONNULL AnalysisDeclContext * getAnalysisDeclContext() const
const LocationContext * getParent() const
It might return null.
bool isConsumedExpr(Expr *E) const
Represents a program point after a store evaluation.
Represents a program point just before an implicit call event.
Represents a point after we ran remove dead bindings BEFORE processing the given statement.
const ProgramPointTag * getTag() const
T castAs() const
Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type.
std::optional< T > getAs() const
Convert to the specified ProgramPoint type, returning std::nullopt if this ProgramPoint is not of the...
const LocationContext * getLocationContext() const
const Stmt * getStmt() const
Stmt - This represents one statement.
static bool isCallStmt(const Stmt *S)
Returns true if this is a statement is a function or method call of some kind.
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.
BumpVectorContext & getNodeAllocator()
unsigned ReclaimCounter
Counter to determine when to reclaim nodes.
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
int64_t NumNodes
NumNodes - The number of nodes in the graph.
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
void reclaimRecentlyAllocatedNodes()
Reclaim "uninteresting" nodes created since the last time this method was called.
static bool isInterestingLValueExpr(const Expr *Ex)
Returns true if nodes for the given expression kind are always kept around.
llvm::BumpPtrAllocator & getAllocator()
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() 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 ...
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.
llvm::FoldingSet< ExplodedNode > Nodes
Nodes - The nodes in the graph.
NodeVector FreeNodes
A list of nodes that can be reused.
const CFGBlock * getCFGBlock() const
const ProgramStateRef & getState() const
const Stmt * getStmtForDiagnostics() const
If the node's program point corresponds to a statement, retrieve that statement.
bool isTrivial() const
The node is trivial if it has only one successor, only one predecessor, it's predecessor has only one...
const Stmt * getPreviousStmtForDiagnostics() const
Find the statement that was executed immediately before this node.
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
ExplodedNode * getFirstSucc()
unsigned pred_size() const
static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)
const Stmt * getNextStmtForDiagnostics() const
Find the next statement that was executed on this node's execution path.
ExplodedNode *const * succ_iterator
const LocationContext * getLocationContext() const
const Stmt * getCurrentOrPreviousStmtForDiagnostics() const
Find the statement that was executed at or immediately before this node.
ExplodedNode * getFirstPred()
unsigned succ_size() const
ExplodedNode *const * pred_iterator
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap