18 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
19 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
28 #include "llvm/ADT/ArrayRef.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/DepthFirstIterator.h"
31 #include "llvm/ADT/FoldingSet.h"
32 #include "llvm/ADT/GraphTraits.h"
33 #include "llvm/ADT/STLExtras.h"
34 #include "llvm/ADT/SetVector.h"
35 #include "llvm/ADT/iterator_range.h"
36 #include "llvm/Support/Allocator.h"
37 #include "llvm/Support/Compiler.h"
92 NodeGroup(
bool Flag =
false) :
P(Flag) {
93 assert(getFlag() == Flag);
100 unsigned size()
const;
102 bool empty()
const {
return P == 0 || getFlag() != 0; }
117 bool getFlag()
const {
124 const ProgramPoint Location;
140 : Location(loc), State(
std::move(state)), Succs(IsSink),
Id(
Id) {
141 assert(
isSink() == IsSink);
172 return Location.getAs<
T>();
185 ID.AddPointer(state.get());
186 ID.AddBoolean(IsSink);
203 bool isSink()
const {
return Succs.getFlag(); }
301 llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
321 llvm::FoldingSet<ExplodedNode>
Nodes;
354 bool* IsNew =
nullptr);
363 bool IsSink =
false);
366 return std::make_unique<ExplodedGraph>();
399 llvm::iterator_range<node_iterator>
nodes() {
return Nodes; }
401 llvm::iterator_range<const_node_iterator>
nodes()
const {
return Nodes; }
422 using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
434 std::unique_ptr<ExplodedGraph>
471 if (N && !
static_cast<ExplodedNode*
>(N)->isSink()) Impl.insert(N);
477 unsigned size()
const {
return Impl.size(); }
478 bool empty()
const {
return Impl.empty(); }
488 Impl.insert(S.begin(), S.end());
505 template <>
struct GraphTraits<
clang::ento::ExplodedGraph *> {
520 if (predecessorOfTrivial(N))
526 if (predecessorOfTrivial(N))
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
llvm::BumpPtrAllocator & getAllocator()
Represents a single basic block in a source-level CFG.
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Decl - This represents one declaration (or definition), e.g.
This represents one expression.
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const Decl * getDecl() const
const ParentMap & getParentMap() const
const LocationContext * getLocationContext() const
const StackFrameContext * getStackFrame() const
It represents a stack frame of the call stack (based on CallEvent).
Stmt - This represents one statement.
BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...
CoreEngine - Implements the core logic of the graph-reachability analysis.
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.
const_roots_iterator roots_begin() const
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
unsigned num_eops() const
roots_iterator roots_end()
std::vector< ExplodedNode * > NodeVector
unsigned ReclaimCounter
Counter to determine when to reclaim nodes.
llvm::iterator_range< node_iterator > nodes()
void reserve(unsigned NodeCount)
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
int64_t NumNodes
NumNodes - The number of nodes in the graph.
NodeVector Roots
The roots of the simulation graph.
BumpVectorContext & getNodeAllocator()
llvm::iterator_range< const_node_iterator > nodes() const
void enableNodeReclamation(unsigned Interval)
Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAll...
NodeVector::const_iterator const_roots_iterator
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
NodeVector EndNodes
The nodes in the simulation graph which have been specially marked as the endpoint of an abstract sim...
NodeVector::iterator eop_iterator
const_roots_iterator roots_end() const
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.
AllNodesTy::const_iterator const_node_iterator
unsigned num_roots() const
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const
AllNodesTy::iterator node_iterator
llvm::FoldingSet< ExplodedNode > AllNodesTy
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 ...
const_eop_iterator eop_begin() const
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
NodeVector::const_iterator const_eop_iterator
BumpVectorContext BVC
BVC - Allocator and context for allocating nodes and their predecessor and successor groups.
roots_iterator roots_begin()
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.
llvm::BumpPtrAllocator & getAllocator()
llvm::DenseMap< const ExplodedNode *, ExplodedNode * > NodeMap
NodeVector::iterator roots_iterator
NodeVector FreeNodes
A list of nodes that can be reused.
const_eop_iterator eop_end() const
bool erase(ExplodedNode *N)
ExplodedNodeSet(ExplodedNode *N)
ImplTy::iterator iterator
ImplTy::const_iterator const_iterator
void insert(const ExplodedNodeSet &S)
const_iterator end() const
void Add(ExplodedNode *N)
ExplodedNodeSet()=default
const_iterator begin() const
ExplodedNode * getFirstPred()
const CFGBlock * getCFGBlock() const
ExplodedNode * getFirstSucc()
llvm::iterator_range< pred_iterator > pred_range
const ProgramStateRef & getState() const
const ParentMap & getParentMap() const
const LocationContext * getLocationContext() const
friend class ExplodedGraph
llvm::iterator_range< const_succ_iterator > const_succ_range
pred_iterator pred_begin()
const_pred_iterator pred_begin() const
const Stmt * getStmtForDiagnostics() const
If the node's program point corresponds to a statement, retrieve that statement.
const_succ_iterator succ_begin() const
llvm::iterator_range< succ_iterator > succ_range
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.
void Profile(llvm::FoldingSetNodeID &ID) const
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 ...
llvm::iterator_range< const_pred_iterator > const_pred_range
const StackFrameContext * getStackFrame() const
unsigned pred_size() const
static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)
ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, int64_t Id, bool IsSink)
bool hasSinglePred() const
const_succ_range succs() const
const Decl & getCodeDecl() const
succ_iterator succ_begin()
const ExplodedNode * getFirstPred() const
const Stmt * getNextStmtForDiagnostics() const
Find the next statement that was executed on this node's execution path.
const ExplodedNode * getFirstSucc() const
ExplodedNode *const * succ_iterator
const_pred_range preds() const
friend class EndOfFunctionNodeBuilder
SVal getSVal(const Stmt *S) const
Get the value of an arbitrary expression at this node.
const Stmt * getCurrentOrPreviousStmtForDiagnostics() const
Find the statement that was executed at or immediately before this node.
const ExplodedNode *const * const_pred_iterator
const_succ_iterator succ_end() const
unsigned succ_size() const
std::optional< T > getLocationAs() const &
ExplodedNode *const * pred_iterator
const ExplodedNode *const * const_succ_iterator
const_pred_iterator pred_end() const
This is the simplest builder which generates nodes in the ExplodedGraph.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
The JSON file list parser is used to communicate input to InstallAPI.
const FunctionProtoType * T
Diagnostic wrappers for TextAPI types for error reporting.
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
static nodes_iterator nodes_end(const GraphTy G)
static bool predecessorOfTrivial(NodeRef N)
static nodes_iterator nodes_begin(const GraphTy G)
static ChildIteratorType child_end(NodeRef N)
llvm::df_iterator< GraphTy > nodes_iterator
clang::ento::ExplodedNode::succ_iterator ChildIteratorType
static NodeRef getEntryNode(const GraphTy G)
static ChildIteratorType child_begin(NodeRef N)