Go to the documentation of this file.
29 #include "llvm/ADT/Optional.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Support/Casting.h"
33 #include "llvm/Support/ErrorHandling.h"
39 using namespace clang;
42 #define DEBUG_TYPE "CoreEngine"
45 "The # of steps executed.");
46 STATISTIC(NumSTUSteps,
"The # of STU steps executed.");
47 STATISTIC(NumCTUSteps,
"The # of CTU steps executed.");
49 "The # of times we reached the max number of steps.");
51 "The # of paths explored by the analyzer.");
72 llvm_unreachable(
"Unknown AnalyzerOptions::ExplorationStrategyKind");
79 BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
82 WList->setBlockCounter(C);
84 CTUWList->setBlockCounter(C);
95 assert(Entry->
empty() &&
"Entry block must be empty.");
97 assert(Entry->
succ_size() == 1 &&
"Entry block must have 1 successor.");
130 bool UnlimitedSteps = MaxSteps == 0;
134 const unsigned PreReservationCap = 4000000;
138 auto ProcessWList = [
this, UnlimitedSteps](
unsigned MaxSteps) {
139 unsigned Steps = MaxSteps;
140 while (WList->hasWork()) {
141 if (!UnlimitedSteps) {
143 NumReachedMaxSteps++;
161 return MaxSteps - Steps;
163 const unsigned STUSteps = ProcessWList(MaxSteps);
166 NumSTUSteps += STUSteps;
167 const unsigned MinCTUSteps =
171 unsigned MaxCTUSteps =
std::max(STUSteps * Pct / 100, MinCTUSteps);
173 WList = std::move(CTUWList);
174 const unsigned CTUSteps = ProcessWList(MaxCTUSteps);
175 NumCTUSteps += CTUSteps;
179 return WList->hasWork();
185 switch (
Loc.getKind()) {
195 assert(
false &&
"BlockExit location never occur in forward analysis.");
208 "Assume epsilon has exactly one predecessor by construction");
255 return "Virtual base initialization skipped because "
256 "it has already been handled by the most derived class";
262 Pred = Bldr.generateNode(
P, Pred->
getState(), Pred);
270 "EXIT block cannot contain Stmts.");
277 RS = dyn_cast<ReturnStmt>(LastStmt->getStmt());
280 RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt());
292 ExplodedNodeSet dstNodes;
294 NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
298 if (!nodeBuilder.hasGeneratedNodes()) {
299 nodeBuilder.generateNode(Pred->State, Pred);
307 ExplodedNode *Pred) {
311 BlockCounter Counter = WList->getBlockCounter();
314 setBlockCounter(Counter);
322 HandleBlockExit(L.
getBlock(), Pred);
325 void CoreEngine::HandleBlockExit(
const CFGBlock * B, ExplodedNode *Pred) {
327 switch (Term->getStmtClass()) {
329 llvm_unreachable(
"Analysis for this terminator not implemented.");
331 case Stmt::CXXBindTemporaryExprClass:
332 HandleCleanupTemporaryBranch(
333 cast<CXXBindTemporaryExpr>(Term), B, Pred);
337 case Stmt::DeclStmtClass:
338 HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
341 case Stmt::BinaryOperatorClass:
342 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
345 case Stmt::BinaryConditionalOperatorClass:
346 case Stmt::ConditionalOperatorClass:
347 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
354 case Stmt::ChooseExprClass:
355 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
358 case Stmt::CXXTryStmtClass:
362 et = B->
succ_end(); it != et; ++it) {
364 generateNode(
BlockEdge(B, succ, Pred->getLocationContext()),
370 case Stmt::DoStmtClass:
371 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
374 case Stmt::CXXForRangeStmtClass:
375 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
378 case Stmt::ForStmtClass:
379 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
382 case Stmt::SEHLeaveStmtClass:
383 case Stmt::ContinueStmtClass:
384 case Stmt::BreakStmtClass:
385 case Stmt::GotoStmtClass:
388 case Stmt::IfStmtClass:
389 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
392 case Stmt::IndirectGotoStmtClass: {
397 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
404 case Stmt::ObjCForCollectionStmtClass:
415 HandleBranch(Term, Term, B, Pred);
418 case Stmt::SwitchStmtClass: {
426 case Stmt::WhileStmtClass:
427 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
430 case Stmt::GCCAsmStmtClass:
431 assert(cast<GCCAsmStmt>(Term)->isAsmGoto() &&
"Encountered GCCAsmStmt without labels");
438 HandleVirtualBaseBranch(B, Pred);
443 "Blocks with no terminator should have at most 1 successor.");
449 void CoreEngine::HandleCallEnter(
const CallEnter &CE, ExplodedNode *Pred) {
454 void CoreEngine::HandleBranch(
const Stmt *Cond,
const Stmt *Term,
455 const CFGBlock * B, ExplodedNode *Pred) {
467 ExplodedNode *Pred) {
478 ExplodedNode *Pred) {
488 void CoreEngine::HandlePostStmt(
const CFGBlock *B,
unsigned StmtIdx,
489 ExplodedNode *Pred) {
493 if (StmtIdx == B->
size())
494 HandleBlockExit(B, Pred);
501 void CoreEngine::HandleVirtualBaseBranch(
const CFGBlock *B,
502 ExplodedNode *Pred) {
504 if (
const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
506 switch (CallerCtor->getConstructionKind()) {
510 HandleBlockEdge(Loc, Pred);
521 HandleBlockEdge(Loc, Pred);
528 ExplodedNode *Pred) {
533 Node->addPredecessor(Pred, G);
540 if (IsNew) WList->enqueue(
Node);
544 const CFGBlock *Block,
unsigned Idx) {
552 WList->enqueue(N,
Block, Idx);
560 WList->enqueue(N,
Block, Idx+1);
565 WList->enqueue(N,
Block, Idx);
570 WList->enqueue(N,
Block, Idx+1);
581 WList->enqueue(N,
Block, Idx+1);
590 WList->enqueue(Succ,
Block, Idx+1);
603 Node->addPredecessor(N, G);
604 return isNew ?
Node :
nullptr;
608 for (
const auto I : Set)
613 const CFGBlock *Block,
unsigned Idx) {
614 for (
const auto I : Set)
621 if (I->getLocationContext()->getParent()) {
622 I = generateCallExitBeginNode(I, RS);
633 void NodeBuilder::anchor() {}
654 void NodeBuilderWithSinks::anchor() {}
662 void BranchNodeBuilder::anchor() {}
691 Eng.WList->enqueue(Succ);
707 Eng.WList->enqueue(Succ);
733 Eng.WList->enqueue(Succ);
void processCallEnter(NodeBuilderContext &BC, CallEnter CE, ExplodedNode *Pred)
Generate the entry node of the callee.
CFGTerminator getTerminator() const
Represents a point when we start the call exit sequence (for inlined call).
__DEVICE__ int max(int __a, int __b)
ProgramPoint withTag(const ProgramPointTag *tag) const
Create a new ProgramPoint object that is the same as the original except for using the specified tag ...
BlockCounter GetEmptyCounter()
const LocationContext * getLocationContext() const
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityLocationQueue()
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
const StackFrameContext * getStackFrame() const
succ_reverse_iterator succ_rbegin()
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
unsigned succ_size() const
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
succ_iterator succ_begin()
NodeVector::iterator eop_iterator
unsigned getBlockID() const
static std::unique_ptr< WorkList > makeBFSBlockDFSContents()
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
@ UnexploredFirstLocationQueue
CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts)
Construct a CoreEngine object to analyze the provided CFG.
void Add(ExplodedNode *N)
void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, NodeBuilderContext &BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
Called by CoreEngine.
This is a meta program point, which should be skipped by all the diagnostic reasoning etc.
AdjacentBlocks::const_iterator const_succ_iterator
Represents a program point just after an implicit call event.
void processCallExit(ExplodedNode *Pred)
Generate the sequence of nodes that simulate the call exit and the post visit for CallExpr.
const LocationContext * getLocationContext() const
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type.
void processSwitch(SwitchNodeBuilder &builder)
ProcessSwitch - Called by CoreEngine.
ExplodedNodeSet & Frontier
The frontier set - a set of nodes which need to be propagated after the builder dies.
static std::unique_ptr< WorkList > generateWorkList(AnalyzerOptions &Opts)
ExplorationStrategyKind getExplorationStrategy() const
const CFGBlock * getSrc() const
Represents a point when we exit a loop.
Represents a single basic block in a source-level CFG.
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
ExplodedNode * getNode() const
Returns the node associated with the worklist unit.
const ProgramStateRef & getState() const
__DEVICE__ int min(int __a, int __b)
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
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 ...
Represents binding an expression to a temporary.
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Returns true if there is still simulation state on the worklist.
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
bool hasSinglePred() const
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
static std::unique_ptr< WorkList > makeDFS()
Represents a point when we finish the call exit sequence (for inlined call).
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
static std::unique_ptr< WorkList > makeBFS()
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
void processBranch(const Stmt *Condition, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
ProcessBranch - Called by CoreEngine.
void processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred)
Called by CoreEngine when processing the entrance of a CFGBlock.
bool isVirtualBaseBranch() const
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
STATISTIC(NumSteps, "The # of steps executed.")
const CFGBlock * getDst() const
const CFGBlock * getEntry() const
Returns the entry block in the CFG for the entered function.
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
const CFGBlock * getBlock() const
static Decl::Kind getKind(const Decl *D)
void processEndWorklist()
Called by CoreEngine when the analysis worklist has terminated.
BlockCounter IncrementCount(BlockCounter BC, const StackFrameContext *CallSite, unsigned BlockID)
ProgramStateRef getInitialState(const LocationContext *InitLoc)
getInitialState - Return the initial state used for the root vertex in the ExplodedGraph.
const CFGBlock * getBlock() const
Returns the CFGblock associated with the worklist unit.
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
bool isFeasible(bool branch)
~StmtNodeBuilder() override
AnalyzerOptions & options
Optional< T > getAs() const
Convert to the specified CFGElement type, returning None if this CFGElement is not of the desired typ...
void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS)
enqueue the nodes corresponding to the end of function onto the end of path / work list.
void processEndOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, const ReturnStmt *RS=nullptr)
Called by CoreEngine.
ExplodedNode * getFirstPred()
void markVisitedBasicBlock(unsigned ID, const Decl *D, unsigned TotalIDs)
Optional< CFGElement > getFirstElement() const
void processStaticInitializer(const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)
Called by CoreEngine.
const Stmt * getCallSite() const
friend class IndirectGotoNodeBuilder
Stores options for the analyzer from the command line.
succ_reverse_iterator succ_rend()
const Stmt * getStmt() const
void processIndirectGoto(IndirectGotoNodeBuilder &builder)
processIndirectGoto - Called by CoreEngine.
void processBeginOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, ExplodedNodeSet &Dst, const BlockEdge &L)
Called by CoreEngine.
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
AnalysisManager & getAnalysisManager()
Represents a top-level expression in a basic block.
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
void reserve(unsigned NodeCount)
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
const NodeBuilderContext & C
friend class SwitchNodeBuilder
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
Stmt - This represents one statement.
void processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx)
processCFGElement - Called by CoreEngine.
Stmt * getTerminatorStmt()
unsigned num_roots() const
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityQueue()
static std::unique_ptr< WorkList > makeUnexploredFirst()
bool erase(ExplodedNode *N)
Represents a point when we begin processing an inlined call.
DataTag::Factory & getDataTags()
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
void addNodes(const ExplodedNodeSet &S)
const CFGBlock * getBlock() const
const Decl * getDecl() const
friend struct NodeBuilderContext
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
const CFGBlock * getBlock() const