1//===- CoreEngine.h - Path-Sensitive Dataflow Engine ------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines a generic engine for intraprocedural, path-sensitive,
10// dataflow analysis via graph reachability.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
15#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
16
17#include "clang/AST/Stmt.h"
18#include "clang/Analysis/AnalysisDeclContext.h"
19#include "clang/Analysis/CFG.h"
20#include "clang/Analysis/ProgramPoint.h"
21#include "clang/Basic/LLVM.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/Support/Casting.h"
28#include <cassert>
29#include <memory>
30#include <utility>
31#include <vector>
32
33namespace clang {
34
35class AnalyzerOptions;
36class CXXBindTemporaryExpr;
37class Expr;
38class LabelDecl;
39
40namespace ento {
41
42class FunctionSummariesTy;
43class SubEngine;
44
45//===----------------------------------------------------------------------===//
46/// CoreEngine - Implements the core logic of the graph-reachability
47/// analysis. It traverses the CFG and generates the ExplodedGraph.
48/// Program "states" are treated as opaque void pointers.
49/// The template class CoreEngine (which subclasses CoreEngine)
50/// provides the matching component to the engine that knows the actual types
51/// for states. Note that this engine only dispatches to transfer functions
52/// at the statement and block-level. The analyses themselves must implement
53/// any transfer function logic and the sub-expression level (if any).
54class CoreEngine {
55 friend class CommonNodeBuilder;
56 friend class EndOfFunctionNodeBuilder;
57 friend class ExprEngine;
58 friend class IndirectGotoNodeBuilder;
59 friend class NodeBuilder;
60 friend struct NodeBuilderContext;
61 friend class SwitchNodeBuilder;
62
63public:
64 using BlocksExhausted =
65 std::vector<std::pair<BlockEdge, const ExplodedNode *>>;
66
67 using BlocksAborted =
68 std::vector<std::pair<const CFGBlock *, const ExplodedNode *>>;
69
70private:
71 SubEngine &SubEng;
72
73 /// G - The simulation graph. Each node is a (location,state) pair.
74 mutable ExplodedGraph G;
75
76 /// WList - A set of queued nodes that need to be processed by the
77 /// worklist algorithm. It is up to the implementation of WList to decide
78 /// the order that nodes are processed.
79 std::unique_ptr<WorkList> WList;
80
81 /// BCounterFactory - A factory object for created BlockCounter objects.
82 /// These are used to record for key nodes in the ExplodedGraph the
83 /// number of times different CFGBlocks have been visited along a path.
84 BlockCounter::Factory BCounterFactory;
85
86 /// The locations where we stopped doing work because we visited a location
87 /// too many times.
88 BlocksExhausted blocksExhausted;
89
90 /// The locations where we stopped because the engine aborted analysis,
91 /// usually because it could not reason about something.
92 BlocksAborted blocksAborted;
93
94 /// The information about functions shared by the whole translation unit.
95 /// (This data is owned by AnalysisConsumer.)
96 FunctionSummariesTy *FunctionSummaries;
97
98 void generateNode(const ProgramPoint &Loc,
99 ProgramStateRef State,
100 ExplodedNode *Pred);
101
102 void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
103 void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
104 void HandleBlockExit(const CFGBlock *B, ExplodedNode *Pred);
105
106 void HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred);
107
108 void HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, ExplodedNode *Pred);
109
110 void HandleBranch(const Stmt *Cond, const Stmt *Term, const CFGBlock *B,
111 ExplodedNode *Pred);
112 void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
113 const CFGBlock *B, ExplodedNode *Pred);
114
115 /// Handle conditional logic for running static initializers.
116 void HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
117 ExplodedNode *Pred);
118
119private:
120 ExplodedNode *generateCallExitBeginNode(ExplodedNode *N,
121 const ReturnStmt *RS);
122
123public:
124 /// Construct a CoreEngine object to analyze the provided CFG.
125 CoreEngine(SubEngine &subengine,
126 FunctionSummariesTy *FS,
127 AnalyzerOptions &Opts);
128
129 CoreEngine(const CoreEngine &) = delete;
130 CoreEngine &operator=(const CoreEngine &) = delete;
131
132 /// getGraph - Returns the exploded graph.
133 ExplodedGraph &getGraph() { return G; }
134
135 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
136 /// steps. Returns true if there is still simulation state on the worklist.
137 bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
138 ProgramStateRef InitState);
139
140 /// Returns true if there is still simulation state on the worklist.
141 bool ExecuteWorkListWithInitialState(const LocationContext *L,
142 unsigned Steps,
143 ProgramStateRef InitState,
144 ExplodedNodeSet &Dst);
145
146 /// Dispatch the work list item based on the given location information.
147 /// Use Pred parameter as the predecessor state.
148 void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
149 const WorkListUnit& WU);
150
151 // Functions for external checking of whether we have unfinished work
152 bool wasBlockAborted() const { return !blocksAborted.empty(); }
153 bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
154 bool hasWorkRemaining() const { return wasBlocksExhausted() ||
155 WList->hasWork() ||
156 wasBlockAborted(); }
157
158 /// Inform the CoreEngine that a basic block was aborted because
159 /// it could not be completely analyzed.
160 void addAbortedBlock(const ExplodedNode *node, const CFGBlock *block) {
161 blocksAborted.push_back(std::make_pair(block, node));
162 }
163
164 WorkList *getWorkList() const { return WList.get(); }
165
166 BlocksExhausted::const_iterator blocks_exhausted_begin() const {
167 return blocksExhausted.begin();
168 }
169
170 BlocksExhausted::const_iterator blocks_exhausted_end() const {
171 return blocksExhausted.end();
172 }
173
174 BlocksAborted::const_iterator blocks_aborted_begin() const {
175 return blocksAborted.begin();
176 }
177
178 BlocksAborted::const_iterator blocks_aborted_end() const {
179 return blocksAborted.end();
180 }
181
182 /// Enqueue the given set of nodes onto the work list.
183 void enqueue(ExplodedNodeSet &Set);
184
185 /// Enqueue nodes that were created as a result of processing
186 /// a statement onto the work list.
187 void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
188
189 /// enqueue the nodes corresponding to the end of function onto the
190 /// end of path / work list.
191 void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS);
192
193 /// Enqueue a single node created as a result of statement processing.
194 void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
195};
196
197// TODO: Turn into a calss.
198struct NodeBuilderContext {
199 const CoreEngine &Eng;
200 const CFGBlock *Block;
201 const LocationContext *LC;
202
203 NodeBuilderContext(const CoreEngine &E, const CFGBlock *B, ExplodedNode *N)
204 : Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); }
205
206 /// Return the CFGBlock associated with this builder.
207 const CFGBlock *getBlock() const { return Block; }
208
209 /// Returns the number of times the current basic block has been
210 /// visited on the exploded graph path.
211 unsigned blockCount() const {
212 return Eng.WList->getBlockCounter().getNumVisited(
213 LC->getStackFrame(),
214 Block->getBlockID());
215 }
216};
217
218/// \class NodeBuilder
219/// This is the simplest builder which generates nodes in the
220/// ExplodedGraph.
221///
222/// The main benefit of the builder is that it automatically tracks the
223/// frontier nodes (or destination set). This is the set of nodes which should
224/// be propagated to the next step / builder. They are the nodes which have been
225/// added to the builder (either as the input node set or as the newly
226/// constructed nodes) but did not have any outgoing transitions added.
227class NodeBuilder {
228 virtual void anchor();
229
230protected:
231 const NodeBuilderContext &C;
232
233 /// Specifies if the builder results have been finalized. For example, if it
234 /// is set to false, autotransitions are yet to be generated.
235 bool Finalized;
236
237 bool HasGeneratedNodes = false;
238
239 /// The frontier set - a set of nodes which need to be propagated after
240 /// the builder dies.
241 ExplodedNodeSet &Frontier;
242
243 /// Checks if the results are ready.
244 virtual bool checkResults() {
245 return Finalized;
246 }
247
248 bool hasNoSinksInFrontier() {
249 for (const auto I : Frontier)
250 if (I->isSink())
251 return false;
252 return true;
253 }
254
255 /// Allow subclasses to finalize results before result_begin() is executed.
256 virtual void finalizeResults() {}
257
258 ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
259 ProgramStateRef State,
260 ExplodedNode *Pred,
261 bool MarkAsSink = false);
262
263public:
264 NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
265 const NodeBuilderContext &Ctx, bool F = true)
266 : C(Ctx), Finalized(F), Frontier(DstSet) {
267 Frontier.Add(SrcNode);
268 }
269
270 NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
271 const NodeBuilderContext &Ctx, bool F = true)
272 : C(Ctx), Finalized(F), Frontier(DstSet) {
273 Frontier.insert(SrcSet);
274 assert(hasNoSinksInFrontier());
275 }
276
277 virtual ~NodeBuilder() = default;
278
279 /// Generates a node in the ExplodedGraph.
280 ExplodedNode *generateNode(const ProgramPoint &PP,
281 ProgramStateRef State,
282 ExplodedNode *Pred) {
283 return generateNodeImpl(PP, State, Pred, false);
284 }
285
286 /// Generates a sink in the ExplodedGraph.
287 ///
288 /// When a node is marked as sink, the exploration from the node is stopped -
289 /// the node becomes the last node on the path and certain kinds of bugs are
290 /// suppressed.
291 ExplodedNode *generateSink(const ProgramPoint &PP,
292 ProgramStateRef State,
293 ExplodedNode *Pred) {
294 return generateNodeImpl(PP, State, Pred, true);
295 }
296
297 const ExplodedNodeSet &getResults() {
298 finalizeResults();
299 assert(checkResults());
300 return Frontier;
301 }
302
303 using iterator = ExplodedNodeSet::iterator;
304
305 /// Iterators through the results frontier.
306 iterator begin() {
307 finalizeResults();
308 assert(checkResults());
309 return Frontier.begin();
310 }
311
312 iterator end() {
313 finalizeResults();
314 return Frontier.end();
315 }
316
317 const NodeBuilderContext &getContext() { return C; }
318 bool hasGeneratedNodes() { return HasGeneratedNodes; }
319
320 void takeNodes(const ExplodedNodeSet &S) {
321 for (const auto I : S)
322 Frontier.erase(I);
323 }
324
325 void takeNodes(ExplodedNode *N) { Frontier.erase(N); }
326 void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
327 void addNodes(ExplodedNode *N) { Frontier.Add(N); }
328};
329
330/// \class NodeBuilderWithSinks
331/// This node builder keeps track of the generated sink nodes.
332class NodeBuilderWithSinks: public NodeBuilder {
333 void anchor() override;
334
335protected:
336 SmallVector<ExplodedNode*, 2> sinksGenerated;
337 ProgramPoint &Location;
338
339public:
340 NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
341 const NodeBuilderContext &Ctx, ProgramPoint &L)
342 : NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
343
344 ExplodedNode *generateNode(ProgramStateRef State,
345 ExplodedNode *Pred,
346 const ProgramPointTag *Tag = nullptr) {
347 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
348 return NodeBuilder::generateNode(LocalLoc, State, Pred);
349 }
350
351 ExplodedNode *generateSink(ProgramStateRef State, ExplodedNode *Pred,
352 const ProgramPointTag *Tag = nullptr) {
353 const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
354 ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
355 if (N && N->isSink())
356 sinksGenerated.push_back(N);
357 return N;
358 }
359
360 const SmallVectorImpl<ExplodedNode*> &getSinks() const {
361 return sinksGenerated;
362 }
363};
364
365/// \class StmtNodeBuilder
366/// This builder class is useful for generating nodes that resulted from
367/// visiting a statement. The main difference from its parent NodeBuilder is
368/// that it creates a statement specific ProgramPoint.
369class StmtNodeBuilder: public NodeBuilder {
370 NodeBuilder *EnclosingBldr;
371
372public:
373 /// Constructs a StmtNodeBuilder. If the builder is going to process
374 /// nodes currently owned by another builder(with larger scope), use
375 /// Enclosing builder to transfer ownership.
376 StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
377 const NodeBuilderContext &Ctx,
378 NodeBuilder *Enclosing = nullptr)
379 : NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
380 if (EnclosingBldr)
381 EnclosingBldr->takeNodes(SrcNode);
382 }
383
384 StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
385 const NodeBuilderContext &Ctx,
386 NodeBuilder *Enclosing = nullptr)
387 : NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
388 if (EnclosingBldr)
389 for (const auto I : SrcSet)
390 EnclosingBldr->takeNodes(I);
391 }
392
393 ~StmtNodeBuilder() override;
394
395 using NodeBuilder::generateNode;
396 using NodeBuilder::generateSink;
397
398 ExplodedNode *generateNode(const Stmt *S,
399 ExplodedNode *Pred,
400 ProgramStateRef St,
401 const ProgramPointTag *tag = nullptr,
402 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
403 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
404 Pred->getLocationContext(), tag);
405 return NodeBuilder::generateNode(L, St, Pred);
406 }
407
408 ExplodedNode *generateSink(const Stmt *S,
409 ExplodedNode *Pred,
410 ProgramStateRef St,
411 const ProgramPointTag *tag = nullptr,
412 ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
413 const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
414 Pred->getLocationContext(), tag);
415 return NodeBuilder::generateSink(L, St, Pred);
416 }
417};
418
419/// BranchNodeBuilder is responsible for constructing the nodes
420/// corresponding to the two branches of the if statement - true and false.
421class BranchNodeBuilder: public NodeBuilder {
422 const CFGBlock *DstT;
423 const CFGBlock *DstF;
424
425 bool InFeasibleTrue;
426 bool InFeasibleFalse;
427
428 void anchor() override;
429
430public:
431 BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
432 const NodeBuilderContext &C,
433 const CFGBlock *dstT, const CFGBlock *dstF)
434 : NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
435 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
436 // The branch node builder does not generate autotransitions.
437 // If there are no successors it means that both branches are infeasible.
438 takeNodes(SrcNode);
439 }
440
441 BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
442 const NodeBuilderContext &C,
443 const CFGBlock *dstT, const CFGBlock *dstF)
444 : NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
445 InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
446 takeNodes(SrcSet);
447 }
448
449 ExplodedNode *generateNode(ProgramStateRef State, bool branch,
450 ExplodedNode *Pred);
451
452 const CFGBlock *getTargetBlock(bool branch) const {
453 return branch ? DstT : DstF;
454 }
455
456 void markInfeasible(bool branch) {
457 if (branch)
458 InFeasibleTrue = true;
459 else
460 InFeasibleFalse = true;
461 }
462
463 bool isFeasible(bool branch) {
464 return branch ? !InFeasibleTrue : !InFeasibleFalse;
465 }
466};
467
468class IndirectGotoNodeBuilder {
469 CoreEngine& Eng;
470 const CFGBlock *Src;
471 const CFGBlock &DispatchBlock;
472 const Expr *E;
473 ExplodedNode *Pred;
474
475public:
476 IndirectGotoNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
477 const Expr *e, const CFGBlock *dispatch, CoreEngine* eng)
478 : Eng(*eng), Src(src), DispatchBlock(*dispatch), E(e), Pred(pred) {}
479
480 class iterator {
481 friend class IndirectGotoNodeBuilder;
482
483 CFGBlock::const_succ_iterator I;
484
485 iterator(CFGBlock::const_succ_iterator i) : I(i) {}
486
487 public:
488 iterator &operator++() { ++I; return *this; }
489 bool operator!=(const iterator &X) const { return I != X.I; }
490
491 const LabelDecl *getLabel() const {
492 return cast<LabelStmt>((*I)->getLabel())->getDecl();
493 }
494
495 const CFGBlock *getBlock() const {
496 return *I;
497 }
498 };
499
500 iterator begin() { return iterator(DispatchBlock.succ_begin()); }
501 iterator end() { return iterator(DispatchBlock.succ_end()); }
502
503 ExplodedNode *generateNode(const iterator &I,
504 ProgramStateRef State,
505 bool isSink = false);
506
507 const Expr *getTarget() const { return E; }
508
509 ProgramStateRef getState() const { return Pred->State; }
510
511 const LocationContext *getLocationContext() const {
512 return Pred->getLocationContext();
513 }
514};
515
516class SwitchNodeBuilder {
517 CoreEngine& Eng;
518 const CFGBlock *Src;
519 const Expr *Condition;
520 ExplodedNode *Pred;
521
522public:
523 SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src,
524 const Expr *condition, CoreEngine* eng)
525 : Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
526
527 class iterator {
528 friend class SwitchNodeBuilder;
529
530 CFGBlock::const_succ_reverse_iterator I;
531
532 iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
533
534 public:
535 iterator &operator++() { ++I; return *this; }
536 bool operator!=(const iterator &X) const { return I != X.I; }
537 bool operator==(const iterator &X) const { return I == X.I; }
538
539 const CaseStmt *getCase() const {
540 return cast<CaseStmt>((*I)->getLabel());
541 }
542
543 const CFGBlock *getBlock() const {
544 return *I;
545 }
546 };
547
548 iterator begin() { return iterator(Src->succ_rbegin()+1); }
549 iterator end() { return iterator(Src->succ_rend()); }
550
551 const SwitchStmt *getSwitch() const {
552 return cast<SwitchStmt>(Src->getTerminator());
553 }
554
555 ExplodedNode *generateCaseStmtNode(const iterator &I,
556 ProgramStateRef State);
557
558 ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
559 bool isSink = false);
560
561 const Expr *getCondition() const { return Condition; }
562
563 ProgramStateRef getState() const { return Pred->State; }
564
565 const LocationContext *getLocationContext() const {
566 return Pred->getLocationContext();
567 }
568};
569
570} // namespace ento
571
572} // namespace clang
573
574#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
575