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.");
47 "The # of times we reached the max number of steps.");
49 "The # of paths explored by the analyzer.");
56 SubEngine &subengine) {
71 llvm_unreachable(
"Unknown AnalyzerOptions::ExplorationStrategyKind");
77 BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
87 assert(Entry->
empty() &&
"Entry block must be empty.");
89 assert(Entry->
succ_size() == 1 &&
"Entry block must have 1 successor.");
122 bool UnlimitedSteps = Steps == 0;
125 const unsigned PreReservationCap = 4000000;
129 while (WList->hasWork()) {
130 if (!UnlimitedSteps) {
132 NumReachedMaxSteps++;
151 return WList->hasWork();
167 assert(
false &&
"BlockExit location never occur in forward analysis.");
180 "Assume epsilon has exactly one predecessor by construction");
222 "EXIT block cannot contain Stmts.");
229 RS = dyn_cast<
ReturnStmt>(LastStmt->getStmt());
232 RS = dyn_cast<
ReturnStmt>(AutoDtor->getTriggerStmt());
250 if (!nodeBuilder.hasGeneratedNodes()) {
251 nodeBuilder.generateNode(Pred->State, Pred);
266 WList->setBlockCounter(Counter);
274 HandleBlockExit(L.
getBlock(), Pred);
279 switch (Term->getStmtClass()) {
281 llvm_unreachable(
"Analysis for this terminator not implemented.");
283 case Stmt::CXXBindTemporaryExprClass:
284 HandleCleanupTemporaryBranch(
289 case Stmt::DeclStmtClass:
290 HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
293 case Stmt::BinaryOperatorClass:
294 HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
297 case Stmt::BinaryConditionalOperatorClass:
298 case Stmt::ConditionalOperatorClass:
299 HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
306 case Stmt::ChooseExprClass:
307 HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
310 case Stmt::CXXTryStmtClass:
314 et = B->
succ_end(); it != et; ++it) {
322 case Stmt::DoStmtClass:
323 HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
326 case Stmt::CXXForRangeStmtClass:
327 HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
330 case Stmt::ForStmtClass:
331 HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
334 case Stmt::ContinueStmtClass:
335 case Stmt::BreakStmtClass:
336 case Stmt::GotoStmtClass:
339 case Stmt::IfStmtClass:
340 HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
343 case Stmt::IndirectGotoStmtClass: {
348 builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
355 case Stmt::ObjCForCollectionStmtClass:
366 HandleBranch(Term, Term, B, Pred);
369 case Stmt::SwitchStmtClass: {
377 case Stmt::WhileStmtClass:
378 HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
384 "Blocks with no terminator should have at most 1 successor.");
395 void CoreEngine::HandleBranch(
const Stmt *Cond,
const Stmt *Term,
429 void CoreEngine::HandlePostStmt(
const CFGBlock *B,
unsigned StmtIdx,
434 if (StmtIdx == B->
size())
435 HandleBlockExit(B, Pred);
458 if (IsNew) WList->enqueue(Node);
462 const CFGBlock *Block,
unsigned Idx) {
470 WList->enqueue(N, Block, Idx);
478 WList->enqueue(N, Block, Idx+1);
483 WList->enqueue(N, Block, Idx);
488 WList->enqueue(N, Block, Idx+1);
499 WList->enqueue(N, Block, Idx+1);
508 WList->enqueue(Succ, Block, Idx+1);
522 return isNew ?
Node :
nullptr;
526 for (
const auto I : Set)
531 const CFGBlock *Block,
unsigned Idx) {
532 for (
const auto I : Set)
539 if (I->getLocationContext()->getParent()) {
540 I = generateCallExitBeginNode(I, RS);
551 void NodeBuilder::anchor() {}
557 HasGeneratedNodes =
true;
559 ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
561 Frontier.erase(FromN);
572 void NodeBuilderWithSinks::anchor() {}
576 for (
const auto I : Frontier)
577 EnclosingBldr->addNodes(I);
580 void BranchNodeBuilder::anchor() {}
586 if (!isFeasible(branch))
591 ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
609 Eng.WList->enqueue(Succ);
625 Eng.WList->enqueue(Succ);
633 assert(Src->succ_rbegin() != Src->succ_rend());
651 Eng.WList->enqueue(Succ);
succ_reverse_iterator succ_rbegin()
const Stmt * getStmt() const
succ_iterator succ_begin()
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
Stmt - This represents one statement.
unsigned getBlockID() const
const CFGBlock * getSrc() const
Represents a point when we begin processing an inlined call.
ProgramPoint withTag(const ProgramPointTag *tag) const
Create a new ProgramPoint object that is the same as the original except for using the specified tag ...
virtual ProgramStateRef getInitialState(const LocationContext *InitLoc)=0
STATISTIC(NumSteps, "The # of steps executed.")
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type...
~StmtNodeBuilder() override
const ProgramStateRef & getState() const
An abstract data type used to count the number of times a given block has been visited along a path a...
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityQueue()
virtual void processBranch(const Stmt *Condition, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)=0
Called by CoreEngine.
Optional< CFGElement > getFirstElement() const
Represents a point when we exit a loop.
unsigned succ_size() const
virtual void processCFGElement(const CFGElement E, ExplodedNode *Pred, unsigned StmtIdx, NodeBuilderContext *Ctx)=0
Called by CoreEngine.
void enqueue(ExplodedNodeSet &Set)
Enqueue the given set of nodes onto the work list.
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Returns true if there is still simulation state on the worklist.
Defines the clang::Expr interface and subclasses for C++ expressions.
const CFGBlock * getEntry() const
Returns the entry block in the CFG for the entered function.
static std::unique_ptr< WorkList > makeDFS()
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts)
Construct a CoreEngine object to analyze the provided CFG.
bool hasSinglePred() const
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
Represents a point when we start the call exit sequence (for inlined call).
AdjacentBlocks::const_iterator const_succ_iterator
This is a meta program point, which should be skipped by all the diagnostic reasoning etc...
ExplodedNode * generateNodeImpl(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink=false)
virtual void processIndirectGoto(IndirectGotoNodeBuilder &builder)=0
Called by CoreEngine.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
const LocationContext * getLocationContext() const
ExplodedNode * generateCaseStmtNode(const iterator &I, ProgramStateRef State)
const CFGBlock * getBlock() const
BlockCounter getBlockCounter() const
Returns the block counter map associated with the worklist unit.
virtual void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE, NodeBuilderContext &BldCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)=0
Called by CoreEngine.
Represents binding an expression to a temporary.
ExplodedNode * getFirstPred()
static std::unique_ptr< WorkList > makeBFS()
Represents a single basic block in a source-level CFG.
Represents a point when we finish the call exit sequence (for inlined call).
const CFGBlock * getBlock() const
virtual void processSwitch(SwitchNodeBuilder &builder)=0
Called by CoreEngine.
unsigned getIndex() const
Return the index within the CFGBlock for the worklist unit.
void Add(ExplodedNode *N)
unsigned num_roots() const
const CFGBlock * getDst() const
void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx)
Enqueue a single node created as a result of statement processing.
virtual void processStaticInitializer(const DeclStmt *DS, NodeBuilderContext &BuilderCtx, ExplodedNode *Pred, ExplodedNodeSet &Dst, const CFGBlock *DstT, const CFGBlock *DstF)=0
Called by CoreEngine.
ReturnStmt - This represents a return, optionally of an expression: return; return 4;...
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 * getNode() const
Returns the node associated with the worklist unit.
ExplodedNode * generateNode(const iterator &I, ProgramStateRef State, bool isSink=false)
CFGTerminator getTerminator()
static std::unique_ptr< WorkList > makeUnexploredFirstPriorityLocationQueue()
T castAs() const
Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type...
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
void dispatchWorkItem(ExplodedNode *Pred, ProgramPoint Loc, const WorkListUnit &WU)
Dispatch the work list item based on the given location information.
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
NodeVector::iterator eop_iterator
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
static std::unique_ptr< WorkList > makeBFSBlockDFSContents()
virtual void processCallExit(ExplodedNode *Pred)=0
Optional< T > getAs() const
Convert to the specified CFGElement type, returning None if this CFGElement is not of the desired typ...
ast_type_traits::DynTypedNode Node
ExplorationStrategyKind getExplorationStrategy() const
Dataflow Directional Tag Classes.
ExplodedNode * generateDefaultCaseNode(ProgramStateRef State, bool isSink=false)
Represents a program point just after an implicit call event.
This node builder keeps track of the generated sink nodes.
virtual void processCallEnter(NodeBuilderContext &BC, CallEnter CE, ExplodedNode *Pred)=0
const CFGBlock * getBlock() const
Returns the CFGblock associated with the worklist unit.
const Decl * getDecl() const
void reserve(unsigned NodeCount)
BlockCounter GetEmptyCounter()
virtual void processEndWorklist()=0
Called by CoreEngine when the analysis worklist is either empty or the.
const LocationContext * getLocationContext() const
virtual void processBeginOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, ExplodedNodeSet &Dst, const BlockEdge &L)=0
Called by CoreEngine.
const StackFrameContext * getStackFrame() const
Stores options for the analyzer from the command line.
void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS)
enqueue the nodes corresponding to the end of function onto the end of path / work list...
ExplodedNode * generateNode(ProgramStateRef State, bool branch, ExplodedNode *Pred)
Represents a top-level expression in a basic block.
BlockCounter IncrementCount(BlockCounter BC, const StackFrameContext *CallSite, unsigned BlockID)
virtual void processEndOfFunction(NodeBuilderContext &BC, ExplodedNode *Pred, const ReturnStmt *RS=nullptr)=0
Called by CoreEngine.
ExplodedNode * addEndOfPath(ExplodedNode *V)
addEndOfPath - Add an untyped node to the set of EOP nodes.
static Decl::Kind getKind(const Decl *D)
static std::unique_ptr< WorkList > makeUnexploredFirst()
const CFGBlock * getBlock() const
virtual void processCFGBlockEntrance(const BlockEdge &L, NodeBuilderWithSinks &nodeBuilder, ExplodedNode *Pred)=0
Called by CoreEngine when it starts processing a CFGBlock.
__DEVICE__ int min(int __a, int __b)
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
ExplodedNode * addRoot(ExplodedNode *V)
addRoot - Add an untyped node to the set of roots.
void markVisitedBasicBlock(unsigned ID, const Decl *D, unsigned TotalIDs)
static std::unique_ptr< WorkList > generateWorkList(AnalyzerOptions &Opts, SubEngine &subengine)