14#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
15#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/iterator_range.h"
29#include "llvm/Support/Casting.h"
38class CXXBindTemporaryExpr;
44class FunctionSummariesTy;
67 std::vector<std::pair<BlockEdge, const ExplodedNode *>>;
70 std::vector<std::pair<const CFGBlock *, const ExplodedNode *>>;
81 std::unique_ptr<WorkList> WList;
82 std::unique_ptr<WorkList> CTUWList;
173 blocksAborted.push_back(std::make_pair(block, node));
180 return llvm::iterator_range(blocksExhausted);
223 return Eng.WList->getBlockCounter().getNumVisited(
239 virtual void anchor();
272 bool MarkAsSink =
false);
296 State->isPosteriorlyOverconstrained());
334 for (
const auto I : S)
346 void anchor()
override;
392 :
NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
400 :
NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
402 for (
const auto I : SrcSet)
439 bool InFeasibleFalse;
441 void anchor()
override;
447 :
NodeBuilder(SrcNode, DstSet,
C), DstT(dstT), DstF(dstF),
448 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
457 :
NodeBuilder(SrcSet, DstSet,
C), DstT(dstT), DstF(dstF),
458 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
466 return branch ? DstT : DstF;
471 InFeasibleTrue =
true;
473 InFeasibleFalse =
true;
477 return branch ? !InFeasibleTrue : !InFeasibleFalse;
491 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
510 return cast<LabelStmt>((*I)->getLabel())->getDecl();
523 bool isSink =
false);
537 const Expr *Condition;
543 : Eng(*eng), Src(src),
Condition(condition), Pred(pred) {}
558 return cast<CaseStmt>((*I)->getLabel());
577 bool isSink =
false);
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.
Stores options for the analyzer from the command line.
Represents a single basic block in a source-level CFG.
succ_reverse_iterator succ_rend()
succ_reverse_iterator succ_rbegin()
AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator
CFGTerminator getTerminator() const
succ_iterator succ_begin()
unsigned getBlockID() const
AdjacentBlocks::const_iterator const_succ_iterator
Represents binding an expression to a temporary.
Represents a point when we begin processing an inlined call.
CaseStmt - Represent a case statement.
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
This represents one expression.
Represents the declaration of a label.
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const StackFrameContext * getStackFrame() const
ProgramPoints can be "tagged" as representing points specific to a given analysis entity.
static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K, const LocationContext *LC, const ProgramPointTag *tag)
ProgramPoint withTag(const ProgramPointTag *tag) const
Create a new ProgramPoint object that is the same as the original except for using the specified tag ...
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Stmt - This represents one statement.
SwitchStmt - This represents a 'switch' stmt.
An abstract data type used to count the number of times a given block has been visited along a path a...
BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...
BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &C, const CFGBlock *dstT, const CFGBlock *dstF)
void markInfeasible(bool branch)
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
bool isFeasible(bool branch)
BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, const NodeBuilderContext &C, const CFGBlock *dstT, const CFGBlock *dstF)
const CFGBlock * getTargetBlock(bool branch) const
CoreEngine - Implements the core logic of the graph-reachability analysis.
void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block)
Inform the CoreEngine that a basic block was aborted because it could not be completely analyzed.
DataTag::Factory & getDataTags()
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
bool wasBlockAborted() const
CoreEngine & operator=(const CoreEngine &)=delete
friend class CommonNodeBuilder
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
WorkList * getCTUWorkList() const
bool wasBlocksExhausted() const
WorkList * getWorkList() const
std::vector< std::pair< BlockEdge, const ExplodedNode * > > BlocksExhausted
CoreEngine(const CoreEngine &)=delete
std::vector< std::pair< const CFGBlock *, const ExplodedNode * > > BlocksAborted
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Returns true if there is still simulation state on the worklist.
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
friend class EndOfFunctionNodeBuilder
auto exhausted_blocks() const
bool hasWorkRemaining() const
ExplodedGraph & getGraph()
getGraph - Returns the exploded graph.
void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS)
enqueue the nodes corresponding to the end of function onto the end of path / work list.
auto aborted_blocks() const
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
bool erase(ExplodedNode *N)
ImplTy::iterator iterator
void insert(const ExplodedNodeSet &S)
void Add(ExplodedNode *N)
const LocationContext * getLocationContext() const
const iterator & operator*() const
const LabelDecl * getLabel() const
bool operator!=(const iterator &X) const
const CFGBlock * getBlock() const
const Expr * getTarget() const
const LocationContext * getLocationContext() const
IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src, const Expr *e, const CFGBlock *dispatch, CoreEngine *eng)
ProgramStateRef getState() const
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
This node builder keeps track of the generated sink nodes.
ExplodedNode * generateNode(ProgramStateRef State, ExplodedNode *Pred, const ProgramPointTag *Tag=nullptr)
NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, ProgramPoint &L)
ExplodedNode * generateSink(ProgramStateRef State, ExplodedNode *Pred, const ProgramPointTag *Tag=nullptr)
const SmallVectorImpl< ExplodedNode * > & getSinks() const
SmallVector< ExplodedNode *, 2 > sinksGenerated
This is the simplest builder which generates nodes in the ExplodedGraph.
const NodeBuilderContext & C
virtual void finalizeResults()
Allow subclasses to finalize results before result_begin() is executed.
bool Finalized
Specifies if the builder results have been finalized.
virtual ~NodeBuilder()=default
void takeNodes(ExplodedNode *N)
ExplodedNode * generateNode(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred)
Generates a node in the ExplodedGraph.
iterator begin()
Iterators through the results frontier.
ExplodedNodeSet::iterator iterator
void takeNodes(const ExplodedNodeSet &S)
NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, bool F=true)
ExplodedNode * generateSink(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred)
Generates a sink in the ExplodedGraph.
ExplodedNodeSet & Frontier
The frontier set - a set of nodes which need to be propagated after the builder dies.
void addNodes(ExplodedNode *N)
bool hasNoSinksInFrontier()
void addNodes(const ExplodedNodeSet &S)
const NodeBuilderContext & getContext()
NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, bool F=true)
virtual bool checkResults()
Checks if the results are ready.
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
const ExplodedNodeSet & getResults()
This builder class is useful for generating nodes that resulted from visiting a statement.
ExplodedNode * generateNode(const Stmt *S, ExplodedNode *Pred, ProgramStateRef St, const ProgramPointTag *tag=nullptr, ProgramPoint::Kind K=ProgramPoint::PostStmtKind)
ExplodedNode * generateSink(const Stmt *S, ExplodedNode *Pred, ProgramStateRef St, const ProgramPointTag *tag=nullptr, ProgramPoint::Kind K=ProgramPoint::PostStmtKind)
StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, NodeBuilder *Enclosing=nullptr)
Constructs a StmtNodeBuilder.
StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx, NodeBuilder *Enclosing=nullptr)
~StmtNodeBuilder() override
bool operator==(const iterator &X) const
bool operator!=(const iterator &X) const
const CFGBlock * getBlock() const
const CaseStmt * getCase() const
ProgramStateRef getState() const
const Expr * getCondition() const
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
const LocationContext * getLocationContext() const
SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, const Expr *condition, CoreEngine *eng)
const SwitchStmt * getSwitch() const
@ C
Languages that the frontend can parse and compile.
const CFGBlock * getBlock() const
Return the CFGBlock associated with this builder.
NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, const LocationContext *L)
NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
const LocationContext * LC
unsigned blockCount() const
Returns the number of times the current basic block has been visited on the exploded graph path.