clang 20.0.0git
TypeErasedDataflowAnalysis.cpp
Go to the documentation of this file.
1//===- TypeErasedDataflowAnalysis.cpp -------------------------------------===//
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 type-erased base types and functions for building dataflow
10// analyses that run over Control-Flow Graphs (CFGs).
11//
12//===----------------------------------------------------------------------===//
13
14#include <optional>
15#include <system_error>
16#include <utility>
17#include <vector>
18
19#include "clang/AST/ASTDumper.h"
20#include "clang/AST/DeclCXX.h"
22#include "clang/AST/StmtCXX.h"
25#include "clang/Analysis/CFG.h"
33#include "llvm/ADT/ArrayRef.h"
34#include "llvm/ADT/STLExtras.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/Error.h"
37
38#define DEBUG_TYPE "clang-dataflow"
39
40namespace clang {
41namespace dataflow {
42
43/// Returns the index of `Block` in the successors of `Pred`.
44static int blockIndexInPredecessor(const CFGBlock &Pred,
45 const CFGBlock &Block) {
46 auto BlockPos = llvm::find_if(
47 Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
48 return Succ && Succ->getBlockID() == Block.getBlockID();
49 });
50 return BlockPos - Pred.succ_begin();
51}
52
53// A "backedge" node is a block introduced in the CFG exclusively to indicate a
54// loop backedge. They are exactly identified by the presence of a non-null
55// pointer to the entry block of the loop condition. Note that this is not
56// necessarily the block with the loop statement as terminator, because
57// short-circuit operators will result in multiple blocks encoding the loop
58// condition, only one of which will contain the loop statement as terminator.
59static bool isBackedgeNode(const CFGBlock &B) {
60 return B.getLoopTarget() != nullptr;
61}
62
63namespace {
64
65/// Extracts the terminator's condition expression.
66class TerminatorVisitor
67 : public ConstStmtVisitor<TerminatorVisitor, const Expr *> {
68public:
69 TerminatorVisitor() = default;
70 const Expr *VisitIfStmt(const IfStmt *S) { return S->getCond(); }
71 const Expr *VisitWhileStmt(const WhileStmt *S) { return S->getCond(); }
72 const Expr *VisitDoStmt(const DoStmt *S) { return S->getCond(); }
73 const Expr *VisitForStmt(const ForStmt *S) { return S->getCond(); }
74 const Expr *VisitCXXForRangeStmt(const CXXForRangeStmt *) {
75 // Don't do anything special for CXXForRangeStmt, because the condition
76 // (being implicitly generated) isn't visible from the loop body.
77 return nullptr;
78 }
79 const Expr *VisitBinaryOperator(const BinaryOperator *S) {
80 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
81 return S->getLHS();
82 }
83 const Expr *VisitConditionalOperator(const ConditionalOperator *S) {
84 return S->getCond();
85 }
86};
87
88/// Holds data structures required for running dataflow analysis.
89struct AnalysisContext {
90 AnalysisContext(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
91 const Environment &InitEnv,
92 llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
93 BlockStates)
94 : ACFG(ACFG), Analysis(Analysis), InitEnv(InitEnv),
95 Log(*InitEnv.getDataflowAnalysisContext().getOptions().Log),
97 Log.beginAnalysis(ACFG, Analysis);
98 }
99 ~AnalysisContext() { Log.endAnalysis(); }
100
101 /// Contains the CFG being analyzed.
102 const AdornedCFG &ACFG;
103 /// The analysis to be run.
104 TypeErasedDataflowAnalysis &Analysis;
105 /// Initial state to start the analysis.
106 const Environment &InitEnv;
107 Logger &Log;
108 /// Stores the state of a CFG block if it has been evaluated by the analysis.
109 /// The indices correspond to the block IDs.
111};
112
113class PrettyStackTraceAnalysis : public llvm::PrettyStackTraceEntry {
114public:
115 PrettyStackTraceAnalysis(const AdornedCFG &ACFG, const char *Message)
116 : ACFG(ACFG), Message(Message) {}
117
118 void print(raw_ostream &OS) const override {
119 OS << Message << "\n";
120 OS << "Decl:\n";
121 ACFG.getDecl().dump(OS);
122 OS << "CFG:\n";
123 ACFG.getCFG().print(OS, LangOptions(), false);
124 }
125
126private:
127 const AdornedCFG &ACFG;
128 const char *Message;
129};
130
131class PrettyStackTraceCFGElement : public llvm::PrettyStackTraceEntry {
132public:
133 PrettyStackTraceCFGElement(const CFGElement &Element, int BlockIdx,
134 int ElementIdx, const char *Message)
135 : Element(Element), BlockIdx(BlockIdx), ElementIdx(ElementIdx),
136 Message(Message) {}
137
138 void print(raw_ostream &OS) const override {
139 OS << Message << ": Element [B" << BlockIdx << "." << ElementIdx << "]\n";
140 if (auto Stmt = Element.getAs<CFGStmt>()) {
141 OS << "Stmt:\n";
142 ASTDumper Dumper(OS, false);
143 Dumper.Visit(Stmt->getStmt());
144 }
145 }
146
147private:
148 const CFGElement &Element;
149 int BlockIdx;
150 int ElementIdx;
151 const char *Message;
152};
153
154// Builds a joined TypeErasedDataflowAnalysisState from 0 or more sources,
155// each of which may be owned (built as part of the join) or external (a
156// reference to an Environment that will outlive the builder).
157// Avoids unneccesary copies of the environment.
158class JoinedStateBuilder {
159 AnalysisContext &AC;
161 std::vector<const TypeErasedDataflowAnalysisState *> All;
162 std::deque<TypeErasedDataflowAnalysisState> Owned;
163
164 TypeErasedDataflowAnalysisState
165 join(const TypeErasedDataflowAnalysisState &L,
166 const TypeErasedDataflowAnalysisState &R) {
167 return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),
168 Environment::join(L.Env, R.Env, AC.Analysis, JoinBehavior)};
169 }
170
171public:
172 JoinedStateBuilder(AnalysisContext &AC,
174 : AC(AC), JoinBehavior(JoinBehavior) {}
175
176 void addOwned(TypeErasedDataflowAnalysisState State) {
177 Owned.push_back(std::move(State));
178 All.push_back(&Owned.back());
179 }
180 void addUnowned(const TypeErasedDataflowAnalysisState &State) {
181 All.push_back(&State);
182 }
183 TypeErasedDataflowAnalysisState take() && {
184 if (All.empty())
185 // FIXME: Consider passing `Block` to Analysis.typeErasedInitialElement
186 // to enable building analyses like computation of dominators that
187 // initialize the state of each basic block differently.
188 return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};
189 if (All.size() == 1)
190 // Join the environment with itself so that we discard expression state if
191 // desired.
192 // FIXME: We could consider writing special-case code for this that only
193 // does the discarding, but it's not clear if this is worth it.
194 return {All[0]->Lattice, Environment::join(All[0]->Env, All[0]->Env,
195 AC.Analysis, JoinBehavior)};
196
197 auto Result = join(*All[0], *All[1]);
198 for (unsigned I = 2; I < All.size(); ++I)
199 Result = join(Result, *All[I]);
200 return Result;
201 }
202};
203} // namespace
204
205static const Expr *getTerminatorCondition(const Stmt *TerminatorStmt) {
206 return TerminatorStmt == nullptr ? nullptr
207 : TerminatorVisitor().Visit(TerminatorStmt);
208}
209
210/// Computes the input state for a given basic block by joining the output
211/// states of its predecessors.
212///
213/// Requirements:
214///
215/// All predecessors of `Block` except those with loop back edges must have
216/// already been transferred. States in `AC.BlockStates` that are set to
217/// `std::nullopt` represent basic blocks that are not evaluated yet.
218static TypeErasedDataflowAnalysisState
219computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) {
220 std::vector<const CFGBlock *> Preds(Block.pred_begin(), Block.pred_end());
221 if (Block.getTerminator().isTemporaryDtorsBranch()) {
222 // This handles a special case where the code that produced the CFG includes
223 // a conditional operator with a branch that constructs a temporary and
224 // calls a destructor annotated as noreturn. The CFG models this as follows:
225 //
226 // B1 (contains the condition of the conditional operator) - succs: B2, B3
227 // B2 (contains code that does not call a noreturn destructor) - succs: B4
228 // B3 (contains code that calls a noreturn destructor) - succs: B4
229 // B4 (has temporary destructor terminator) - succs: B5, B6
230 // B5 (noreturn block that is associated with the noreturn destructor call)
231 // B6 (contains code that follows the conditional operator statement)
232 //
233 // The first successor (B5 above) of a basic block with a temporary
234 // destructor terminator (B4 above) is the block that evaluates the
235 // destructor. If that block has a noreturn element then the predecessor
236 // block that constructed the temporary object (B3 above) is effectively a
237 // noreturn block and its state should not be used as input for the state
238 // of the block that has a temporary destructor terminator (B4 above). This
239 // holds regardless of which branch of the ternary operator calls the
240 // noreturn destructor. However, it doesn't cases where a nested ternary
241 // operator includes a branch that contains a noreturn destructor call.
242 //
243 // See `NoreturnDestructorTest` for concrete examples.
244 if (Block.succ_begin()->getReachableBlock() != nullptr &&
245 Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
246 const CFGBlock *StmtBlock = nullptr;
247 if (const Stmt *Terminator = Block.getTerminatorStmt())
248 StmtBlock = AC.ACFG.blockForStmt(*Terminator);
249 assert(StmtBlock != nullptr);
250 llvm::erase(Preds, StmtBlock);
251 }
252 }
253
254 // If any of the predecessor blocks contains an expression consumed in a
255 // different block, we need to keep expression state.
256 // Note that in this case, we keep expression state for all predecessors,
257 // rather than only those predecessors that actually contain an expression
258 // consumed in a different block. While this is potentially suboptimal, it's
259 // actually likely, if we have control flow within a full expression, that
260 // all predecessors have expression state consumed in a different block.
262 for (const CFGBlock *Pred : Preds) {
263 if (Pred && AC.ACFG.containsExprConsumedInDifferentBlock(*Pred)) {
264 JoinBehavior = Environment::KeepExprState;
265 break;
266 }
267 }
268
269 JoinedStateBuilder Builder(AC, JoinBehavior);
270 for (const CFGBlock *Pred : Preds) {
271 // Skip if the `Block` is unreachable or control flow cannot get past it.
272 if (!Pred || Pred->hasNoReturnElement())
273 continue;
274
275 // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
276 // loop back edge to `Block`.
277 const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
278 AC.BlockStates[Pred->getBlockID()];
279 if (!MaybePredState)
280 continue;
281
282 const TypeErasedDataflowAnalysisState &PredState = *MaybePredState;
283 const Expr *Cond = getTerminatorCondition(Pred->getTerminatorStmt());
284 if (Cond == nullptr) {
285 Builder.addUnowned(PredState);
286 continue;
287 }
288
289 bool BranchVal = blockIndexInPredecessor(*Pred, Block) == 0;
290
291 // `transferBranch` may need to mutate the environment to describe the
292 // dynamic effect of the terminator for a given branch. Copy now.
293 TypeErasedDataflowAnalysisState Copy = MaybePredState->fork();
294 if (AC.Analysis.builtinOptions()) {
295 auto *CondVal = Copy.Env.get<BoolValue>(*Cond);
296 // In transferCFGBlock(), we ensure that we always have a `Value`
297 // for the terminator condition, so assert this. We consciously
298 // assert ourselves instead of asserting via `cast()` so that we get
299 // a more meaningful line number if the assertion fails.
300 assert(CondVal != nullptr);
301 BoolValue *AssertedVal =
302 BranchVal ? CondVal : &Copy.Env.makeNot(*CondVal);
303 Copy.Env.assume(AssertedVal->formula());
304 }
305 AC.Analysis.transferBranchTypeErased(BranchVal, Cond, Copy.Lattice,
306 Copy.Env);
307 Builder.addOwned(std::move(Copy));
308 }
309 return std::move(Builder).take();
310}
311
312/// Built-in transfer function for `CFGStmt`.
313static void
314builtinTransferStatement(unsigned CurBlockID, const CFGStmt &Elt,
316 AnalysisContext &AC) {
317 const Stmt *S = Elt.getStmt();
318 assert(S != nullptr);
319 transfer(StmtToEnvMap(AC.ACFG, AC.BlockStates, CurBlockID, InputState), *S,
320 InputState.Env, AC.Analysis);
321}
322
323/// Built-in transfer function for `CFGInitializer`.
324static void
328 assert(Init != nullptr);
329
330 auto &Env = InputState.Env;
331 auto &ThisLoc = *Env.getThisPointeeStorageLocation();
332
333 if (!Init->isAnyMemberInitializer())
334 // FIXME: Handle base initialization
335 return;
336
337 auto *InitExpr = Init->getInit();
338 assert(InitExpr != nullptr);
339
340 const FieldDecl *Member = nullptr;
341 RecordStorageLocation *ParentLoc = &ThisLoc;
342 StorageLocation *MemberLoc = nullptr;
343 if (Init->isMemberInitializer()) {
344 Member = Init->getMember();
345 MemberLoc = ThisLoc.getChild(*Member);
346 } else {
347 IndirectFieldDecl *IndirectField = Init->getIndirectMember();
348 assert(IndirectField != nullptr);
349 MemberLoc = &ThisLoc;
350 for (const auto *I : IndirectField->chain()) {
351 Member = cast<FieldDecl>(I);
352 ParentLoc = cast<RecordStorageLocation>(MemberLoc);
353 MemberLoc = ParentLoc->getChild(*Member);
354 }
355 }
356 assert(Member != nullptr);
357
358 // FIXME: Instead of these case distinctions, we would ideally want to be able
359 // to simply use `Environment::createObject()` here, the same way that we do
360 // this in `TransferVisitor::VisitInitListExpr()`. However, this would require
361 // us to be able to build a list of fields that we then use to initialize an
362 // `RecordStorageLocation` -- and the problem is that, when we get here,
363 // the `RecordStorageLocation` already exists. We should explore if there's
364 // anything that we can do to change this.
365 if (Member->getType()->isReferenceType()) {
366 auto *InitExprLoc = Env.getStorageLocation(*InitExpr);
367 if (InitExprLoc == nullptr)
368 return;
369
370 ParentLoc->setChild(*Member, InitExprLoc);
371 // Record-type initializers construct themselves directly into the result
372 // object, so there is no need to handle them here.
373 } else if (!Member->getType()->isRecordType()) {
374 assert(MemberLoc != nullptr);
375 if (auto *InitExprVal = Env.getValue(*InitExpr))
376 Env.setValue(*MemberLoc, *InitExprVal);
377 }
378}
379
380static void builtinTransfer(unsigned CurBlockID, const CFGElement &Elt,
382 AnalysisContext &AC) {
383 switch (Elt.getKind()) {
385 builtinTransferStatement(CurBlockID, Elt.castAs<CFGStmt>(), State, AC);
386 break;
389 break;
391 // Removing declarations when their lifetime ends serves two purposes:
392 // - Eliminate unnecessary clutter from `Environment::DeclToLoc`
393 // - Allow us to assert that, when joining two `Environment`s, the two
394 // `DeclToLoc` maps never contain entries that map the same declaration to
395 // different storage locations.
396 if (const ValueDecl *VD = Elt.castAs<CFGLifetimeEnds>().getVarDecl())
397 State.Env.removeDecl(*VD);
398 break;
399 default:
400 // FIXME: Evaluate other kinds of `CFGElement`
401 break;
402 }
403}
404
405/// Transfers `State` by evaluating each element in the `Block` based on the
406/// `AC.Analysis` specified.
407///
408/// Built-in transfer functions (if the option for `ApplyBuiltinTransfer` is set
409/// by the analysis) will be applied to the element before evaluation by the
410/// user-specified analysis.
411/// `PostVisitCFG` (if provided) will be applied to the element after evaluation
412/// by the user-specified analysis.
413static TypeErasedDataflowAnalysisState
414transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC,
415 const CFGEltCallbacksTypeErased &PostAnalysisCallbacks = {}) {
416 AC.Log.enterBlock(Block, PostAnalysisCallbacks.Before != nullptr ||
417 PostAnalysisCallbacks.After != nullptr);
418 auto State = computeBlockInputState(Block, AC);
419 AC.Log.recordState(State);
420 int ElementIdx = 1;
421 for (const auto &Element : Block) {
422 PrettyStackTraceCFGElement CrashInfo(Element, Block.getBlockID(),
423 ElementIdx++, "transferCFGBlock");
424
425 AC.Log.enterElement(Element);
426
427 if (PostAnalysisCallbacks.Before) {
428 PostAnalysisCallbacks.Before(Element, State);
429 }
430
431 // Built-in analysis
432 if (AC.Analysis.builtinOptions()) {
433 builtinTransfer(Block.getBlockID(), Element, State, AC);
434 }
435
436 // User-provided analysis
437 AC.Analysis.transferTypeErased(Element, State.Lattice, State.Env);
438
439 if (PostAnalysisCallbacks.After) {
440 PostAnalysisCallbacks.After(Element, State);
441 }
442
443 AC.Log.recordState(State);
444 }
445
446 // If we have a terminator, evaluate its condition.
447 // This `Expr` may not appear as a `CFGElement` anywhere else, and it's
448 // important that we evaluate it here (rather than while processing the
449 // terminator) so that we put the corresponding value in the right
450 // environment.
451 if (const Expr *TerminatorCond =
452 dyn_cast_or_null<Expr>(Block.getTerminatorCondition())) {
453 if (State.Env.getValue(*TerminatorCond) == nullptr)
454 // FIXME: This only runs the builtin transfer, not the analysis-specific
455 // transfer. Fixing this isn't trivial, as the analysis-specific transfer
456 // takes a `CFGElement` as input, but some expressions only show up as a
457 // terminator condition, but not as a `CFGElement`. The condition of an if
458 // statement is one such example.
459 transfer(StmtToEnvMap(AC.ACFG, AC.BlockStates, Block.getBlockID(), State),
460 *TerminatorCond, State.Env, AC.Analysis);
461
462 // If the transfer function didn't produce a value, create an atom so that
463 // we have *some* value for the condition expression. This ensures that
464 // when we extend the flow condition, it actually changes.
465 if (State.Env.getValue(*TerminatorCond) == nullptr)
466 State.Env.setValue(*TerminatorCond, State.Env.makeAtomicBoolValue());
467 AC.Log.recordState(State);
468 }
469
470 return State;
471}
472
476 const Environment &InitEnv,
477 const CFGEltCallbacksTypeErased &PostAnalysisCallbacks,
478 std::int32_t MaxBlockVisits) {
479 PrettyStackTraceAnalysis CrashInfo(ACFG, "runTypeErasedDataflowAnalysis");
480
481 std::optional<Environment> MaybeStartingEnv;
482 if (InitEnv.callStackSize() == 0) {
483 MaybeStartingEnv = InitEnv.fork();
484 MaybeStartingEnv->initialize();
485 }
486 const Environment &StartingEnv =
487 MaybeStartingEnv ? *MaybeStartingEnv : InitEnv;
488
489 const clang::CFG &CFG = ACFG.getCFG();
490 PostOrderCFGView POV(&CFG);
491 ForwardDataflowWorklist Worklist(CFG, &POV);
492
493 std::vector<std::optional<TypeErasedDataflowAnalysisState>> BlockStates(
494 CFG.size());
495
496 // The entry basic block doesn't contain statements so it can be skipped.
497 const CFGBlock &Entry = CFG.getEntry();
499 StartingEnv.fork()};
500 Worklist.enqueueSuccessors(&Entry);
501
502 AnalysisContext AC(ACFG, Analysis, StartingEnv, BlockStates);
503 std::int32_t BlockVisits = 0;
504 while (const CFGBlock *Block = Worklist.dequeue()) {
505 LLVM_DEBUG(llvm::dbgs()
506 << "Processing Block " << Block->getBlockID() << "\n");
507 if (++BlockVisits > MaxBlockVisits) {
508 return llvm::createStringError(std::errc::timed_out,
509 "maximum number of blocks processed");
510 }
511
512 const std::optional<TypeErasedDataflowAnalysisState> &OldBlockState =
513 BlockStates[Block->getBlockID()];
514 TypeErasedDataflowAnalysisState NewBlockState =
516 LLVM_DEBUG({
517 llvm::errs() << "New Env:\n";
518 NewBlockState.Env.dump();
519 });
520
521 if (OldBlockState) {
522 LLVM_DEBUG({
523 llvm::errs() << "Old Env:\n";
524 OldBlockState->Env.dump();
525 });
526 if (isBackedgeNode(*Block)) {
528 NewBlockState.Lattice, OldBlockState->Lattice);
529 LatticeJoinEffect Effect2 =
530 NewBlockState.Env.widen(OldBlockState->Env, Analysis);
531 if (Effect1 == LatticeJoinEffect::Unchanged &&
532 Effect2 == LatticeJoinEffect::Unchanged) {
533 // The state of `Block` didn't change from widening so there's no need
534 // to revisit its successors.
535 AC.Log.blockConverged();
536 continue;
537 }
538 } else if (Analysis.isEqualTypeErased(OldBlockState->Lattice,
539 NewBlockState.Lattice) &&
540 OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)) {
541 // The state of `Block` didn't change after transfer so there's no need
542 // to revisit its successors.
543 AC.Log.blockConverged();
544 continue;
545 }
546 }
547
548 BlockStates[Block->getBlockID()] = std::move(NewBlockState);
549
550 // Do not add unreachable successor blocks to `Worklist`.
551 if (Block->hasNoReturnElement())
552 continue;
553
554 Worklist.enqueueSuccessors(Block);
555 }
556 // FIXME: Consider evaluating unreachable basic blocks (those that have a
557 // state set to `std::nullopt` at this point) to also analyze dead code.
558
559 if (PostAnalysisCallbacks.Before || PostAnalysisCallbacks.After) {
560 for (const CFGBlock *Block : ACFG.getCFG()) {
561 // Skip blocks that were not evaluated.
562 if (!BlockStates[Block->getBlockID()])
563 continue;
564 transferCFGBlock(*Block, AC, PostAnalysisCallbacks);
565 }
566 }
567
568 return std::move(BlockStates);
569}
570
571} // namespace dataflow
572} // namespace clang
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
const Environment & Env
Definition: HTMLLogger.cpp:148
static void print(llvm::raw_ostream &OS, const T &V, ASTContext &ASTCtx, QualType Ty)
llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates
Stores the state of a CFG block if it has been evaluated by the analysis.
const Environment & InitEnv
Initial state to start the analysis.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
This class represents a potential adjacent block in the CFG.
Definition: CFG.h:819
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
succ_range succs()
Definition: CFG.h:994
succ_iterator succ_begin()
Definition: CFG.h:984
const Stmt * getLoopTarget() const
Definition: CFG.h:1098
unsigned getBlockID() const
Definition: CFG.h:1105
Represents a top-level expression in a basic block.
Definition: CFG.h:55
@ LifetimeEnds
Definition: CFG.h:63
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
Definition: CFG.h:99
Kind getKind() const
Definition: CFG.h:118
Represents C++ base or member initializer from constructor's initialization list.
Definition: CFG.h:227
CXXCtorInitializer * getInitializer() const
Definition: CFG.h:232
Represents the point where the lifetime of an automatic object ends.
Definition: CFG.h:292
const VarDecl * getVarDecl() const
Definition: CFG.h:297
const Stmt * getStmt() const
Definition: CFG.h:138
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1214
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
Definition: CFG.h:1407
CFGBlock & getEntry()
Definition: CFG.h:1322
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2304
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:195
const CFGBlock * dequeue()
This represents one expression.
Definition: Expr.h:110
Represents a member of a struct/union/class.
Definition: Decl.h:3030
IfStmt - This represents an if/then/else.
Definition: Stmt.h:2143
Represents a field injected from an anonymous union/struct into the parent scope.
Definition: Decl.h:3318
ArrayRef< NamedDecl * > chain() const
Definition: Decl.h:3340
Stmt - This represents one statement.
Definition: Stmt.h:84
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:667
Holds CFG with additional information derived from it that is needed to perform dataflow analysis.
Definition: AdornedCFG.h:47
const CFG & getCFG() const
Returns the CFG that is stored in this context.
Definition: AdornedCFG.h:64
Models a boolean.
Definition: Value.h:94
const Formula & formula() const
Definition: Value.h:107
Holds the state of the program (store and heap) at a given program point.
LatticeEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
RecordStorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
StorageLocation * getStorageLocation(const ValueDecl &D) const
Returns the storage location assigned to D in the environment, or null if D isn't assigned a storage ...
LLVM_DUMP_METHOD void dump() const
Environment fork() const
Returns a new environment that is a copy of this one.
Value * getValue(const StorageLocation &Loc) const
Returns the value assigned to Loc in the environment or null if Loc isn't assigned a value in the env...
ExprJoinBehavior
How to treat expression state (ExprToLoc and ExprToVal) in a join.
static Environment join(const Environment &EnvA, const Environment &EnvB, Environment::ValueModel &Model, ExprJoinBehavior ExprBehavior)
Joins two environments by taking the intersection of storage locations and values that are stored in ...
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
size_t callStackSize() const
Returns the size of the call stack, not counting the initial analysis target.
void initialize()
Assigns storage locations and values to all parameters, captures, global variables,...
A storage location for a record (struct, class, or union).
StorageLocation * getChild(const ValueDecl &D) const
Returns the child storage location for D.
void setChild(const ValueDecl &D, StorageLocation *Loc)
Changes the child storage location for a field D of reference type.
Maps statements to the environments of basic blocks that contain them.
Definition: Transfer.h:26
Base class for elements of the local variable store and of the heap.
Type-erased base class for dataflow analyses built on a single lattice type.
virtual LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous)=0
Chooses a lattice element that approximates the current element at a program point,...
virtual TypeErasedLattice typeErasedInitialElement()=0
Returns a type-erased lattice element that models the initial state of a basic block.
virtual bool isEqualTypeErased(const TypeErasedLattice &, const TypeErasedLattice &)=0
Returns true if and only if the two given type-erased lattice elements are equal.
constexpr XRayInstrMask All
Definition: XRayInstr.h:43
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, Environment::ValueModel &Model)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:890
static TypeErasedDataflowAnalysisState computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC)
Computes the input state for a given basic block by joining the output states of its predecessors.
static void builtinTransfer(unsigned CurBlockID, const CFGElement &Elt, TypeErasedDataflowAnalysisState &State, AnalysisContext &AC)
static void builtinTransferInitializer(const CFGInitializer &Elt, TypeErasedDataflowAnalysisState &InputState)
Built-in transfer function for CFGInitializer.
static const Expr * getTerminatorCondition(const Stmt *TerminatorStmt)
static TypeErasedDataflowAnalysisState transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, const CFGEltCallbacksTypeErased &PostAnalysisCallbacks={})
Transfers State by evaluating each element in the Block based on the AC.Analysis specified.
static int blockIndexInPredecessor(const CFGBlock &Pred, const CFGBlock &Block)
Returns the index of Block in the successors of Pred.
static bool isBackedgeNode(const CFGBlock &B)
llvm::Expected< std::vector< std::optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, const CFGEltCallbacksTypeErased &PostAnalysisCallbacks, std::int32_t MaxBlockVisits)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
static void builtinTransferStatement(unsigned CurBlockID, const CFGStmt &Elt, TypeErasedDataflowAnalysisState &InputState, AnalysisContext &AC)
Built-in transfer function for CFGStmt.
LatticeEffect
Effect indicating whether a lattice operation resulted in a new value.
The JSON file list parser is used to communicate input to InstallAPI.
@ Result
The result type of a method or function.
A worklist implementation for forward dataflow analysis.
void enqueueSuccessors(const CFGBlock *Block)
A pair of callbacks to be called with the state before and after visiting a CFG element.
Type-erased model of the program at a given program point.
TypeErasedLattice Lattice
Type-erased model of a program property.
Environment Env
Model of the state of the program (store and heap).