clang 18.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 <algorithm>
15#include <optional>
16#include <system_error>
17#include <utility>
18#include <vector>
19
20#include "clang/AST/ASTDumper.h"
21#include "clang/AST/DeclCXX.h"
23#include "clang/AST/StmtCXX.h"
26#include "clang/Analysis/CFG.h"
34#include "llvm/ADT/ArrayRef.h"
35#include "llvm/ADT/STLExtras.h"
36#include "llvm/ADT/SmallBitVector.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/Error.h"
39
40#define DEBUG_TYPE "clang-dataflow"
41
42namespace clang {
43namespace dataflow {
44
45/// Returns the index of `Block` in the successors of `Pred`.
46static int blockIndexInPredecessor(const CFGBlock &Pred,
47 const CFGBlock &Block) {
48 auto BlockPos = llvm::find_if(
49 Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
50 return Succ && Succ->getBlockID() == Block.getBlockID();
51 });
52 return BlockPos - Pred.succ_begin();
53}
54
55// A "backedge" node is a block introduced in the CFG exclusively to indicate a
56// loop backedge. They are exactly identified by the presence of a non-null
57// pointer to the entry block of the loop condition. Note that this is not
58// necessarily the block with the loop statement as terminator, because
59// short-circuit operators will result in multiple blocks encoding the loop
60// condition, only one of which will contain the loop statement as terminator.
61static bool isBackedgeNode(const CFGBlock &B) {
62 return B.getLoopTarget() != nullptr;
63}
64
65namespace {
66
67// The return type of the visit functions in TerminatorVisitor. The first
68// element represents the terminator expression (that is the conditional
69// expression in case of a path split in the CFG). The second element
70// represents whether the condition was true or false.
71using TerminatorVisitorRetTy = std::pair<const Expr *, bool>;
72
73/// Extends the flow condition of an environment based on a terminator
74/// statement.
75class TerminatorVisitor
76 : public ConstStmtVisitor<TerminatorVisitor, TerminatorVisitorRetTy> {
77public:
78 TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
79 int BlockSuccIdx)
80 : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx) {}
81
82 TerminatorVisitorRetTy VisitIfStmt(const IfStmt *S) {
83 auto *Cond = S->getCond();
84 assert(Cond != nullptr);
85 return extendFlowCondition(*Cond);
86 }
87
88 TerminatorVisitorRetTy VisitWhileStmt(const WhileStmt *S) {
89 auto *Cond = S->getCond();
90 assert(Cond != nullptr);
91 return extendFlowCondition(*Cond);
92 }
93
94 TerminatorVisitorRetTy VisitDoStmt(const DoStmt *S) {
95 auto *Cond = S->getCond();
96 assert(Cond != nullptr);
97 return extendFlowCondition(*Cond);
98 }
99
100 TerminatorVisitorRetTy VisitForStmt(const ForStmt *S) {
101 auto *Cond = S->getCond();
102 if (Cond != nullptr)
103 return extendFlowCondition(*Cond);
104 return {nullptr, false};
105 }
106
107 TerminatorVisitorRetTy VisitCXXForRangeStmt(const CXXForRangeStmt *) {
108 // Don't do anything special for CXXForRangeStmt, because the condition
109 // (being implicitly generated) isn't visible from the loop body.
110 return {nullptr, false};
111 }
112
113 TerminatorVisitorRetTy VisitBinaryOperator(const BinaryOperator *S) {
114 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
115 auto *LHS = S->getLHS();
116 assert(LHS != nullptr);
117 return extendFlowCondition(*LHS);
118 }
119
120 TerminatorVisitorRetTy
121 VisitConditionalOperator(const ConditionalOperator *S) {
122 auto *Cond = S->getCond();
123 assert(Cond != nullptr);
124 return extendFlowCondition(*Cond);
125 }
126
127private:
128 TerminatorVisitorRetTy extendFlowCondition(const Expr &Cond) {
129 // The terminator sub-expression might not be evaluated.
130 if (Env.getValue(Cond) == nullptr)
131 transfer(StmtToEnv, Cond, Env);
132
133 auto *Val = cast_or_null<BoolValue>(Env.getValue(Cond));
134 // Value merging depends on flow conditions from different environments
135 // being mutually exclusive -- that is, they cannot both be true in their
136 // entirety (even if they may share some clauses). So, we need *some* value
137 // for the condition expression, even if just an atom.
138 if (Val == nullptr) {
139 Val = &Env.makeAtomicBoolValue();
140 Env.setValue(Cond, *Val);
141 }
142
143 bool ConditionValue = true;
144 // The condition must be inverted for the successor that encompasses the
145 // "else" branch, if such exists.
146 if (BlockSuccIdx == 1) {
147 Val = &Env.makeNot(*Val);
148 ConditionValue = false;
149 }
150
151 Env.assume(Val->formula());
152 return {&Cond, ConditionValue};
153 }
154
155 const StmtToEnvMap &StmtToEnv;
156 Environment &Env;
157 int BlockSuccIdx;
158};
159
160/// Holds data structures required for running dataflow analysis.
161struct AnalysisContext {
162 AnalysisContext(const ControlFlowContext &CFCtx,
163 TypeErasedDataflowAnalysis &Analysis,
164 const Environment &InitEnv,
165 llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
166 BlockStates)
168 Log(*InitEnv.getDataflowAnalysisContext().getOptions().Log),
170 Log.beginAnalysis(CFCtx, Analysis);
171 }
172 ~AnalysisContext() { Log.endAnalysis(); }
173
174 /// Contains the CFG being analyzed.
175 const ControlFlowContext &CFCtx;
176 /// The analysis to be run.
177 TypeErasedDataflowAnalysis &Analysis;
178 /// Initial state to start the analysis.
179 const Environment &InitEnv;
180 Logger &Log;
181 /// Stores the state of a CFG block if it has been evaluated by the analysis.
182 /// The indices correspond to the block IDs.
184};
185
186class PrettyStackTraceAnalysis : public llvm::PrettyStackTraceEntry {
187public:
188 PrettyStackTraceAnalysis(const ControlFlowContext &CFCtx, const char *Message)
189 : CFCtx(CFCtx), Message(Message) {}
190
191 void print(raw_ostream &OS) const override {
192 OS << Message << "\n";
193 OS << "Decl:\n";
194 CFCtx.getDecl().dump(OS);
195 OS << "CFG:\n";
196 CFCtx.getCFG().print(OS, LangOptions(), false);
197 }
198
199private:
200 const ControlFlowContext &CFCtx;
201 const char *Message;
202};
203
204class PrettyStackTraceCFGElement : public llvm::PrettyStackTraceEntry {
205public:
206 PrettyStackTraceCFGElement(const CFGElement &Element, int BlockIdx,
207 int ElementIdx, const char *Message)
208 : Element(Element), BlockIdx(BlockIdx), ElementIdx(ElementIdx),
209 Message(Message) {}
210
211 void print(raw_ostream &OS) const override {
212 OS << Message << ": Element [B" << BlockIdx << "." << ElementIdx << "]\n";
213 if (auto Stmt = Element.getAs<CFGStmt>()) {
214 OS << "Stmt:\n";
215 ASTDumper Dumper(OS, false);
216 Dumper.Visit(Stmt->getStmt());
217 }
218 }
219
220private:
221 const CFGElement &Element;
222 int BlockIdx;
223 int ElementIdx;
224 const char *Message;
225};
226
227// Builds a joined TypeErasedDataflowAnalysisState from 0 or more sources,
228// each of which may be owned (built as part of the join) or external (a
229// reference to an Environment that will outlive the builder).
230// Avoids unneccesary copies of the environment.
231class JoinedStateBuilder {
232 AnalysisContext &AC;
233 std::vector<const TypeErasedDataflowAnalysisState *> All;
234 std::deque<TypeErasedDataflowAnalysisState> Owned;
235
236 TypeErasedDataflowAnalysisState
237 join(const TypeErasedDataflowAnalysisState &L,
238 const TypeErasedDataflowAnalysisState &R) {
239 return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),
240 Environment::join(L.Env, R.Env, AC.Analysis)};
241 }
242
243public:
244 JoinedStateBuilder(AnalysisContext &AC) : AC(AC) {}
245
246 void addOwned(TypeErasedDataflowAnalysisState State) {
247 Owned.push_back(std::move(State));
248 All.push_back(&Owned.back());
249 }
250 void addUnowned(const TypeErasedDataflowAnalysisState &State) {
251 All.push_back(&State);
252 }
253 TypeErasedDataflowAnalysisState take() && {
254 if (All.empty())
255 // FIXME: Consider passing `Block` to Analysis.typeErasedInitialElement
256 // to enable building analyses like computation of dominators that
257 // initialize the state of each basic block differently.
258 return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};
259 if (All.size() == 1)
260 // Join the environment with itself so that we discard the entries from
261 // `ExprToLoc` and `ExprToVal`.
262 // FIXME: We could consider writing special-case code for this that only
263 // does the discarding, but it's not clear if this is worth it.
264 return {All[0]->Lattice,
265 Environment::join(All[0]->Env, All[0]->Env, AC.Analysis)};
266
267 auto Result = join(*All[0], *All[1]);
268 for (unsigned I = 2; I < All.size(); ++I)
269 Result = join(Result, *All[I]);
270 return Result;
271 }
272};
273
274} // namespace
275
276/// Computes the input state for a given basic block by joining the output
277/// states of its predecessors.
278///
279/// Requirements:
280///
281/// All predecessors of `Block` except those with loop back edges must have
282/// already been transferred. States in `AC.BlockStates` that are set to
283/// `std::nullopt` represent basic blocks that are not evaluated yet.
284static TypeErasedDataflowAnalysisState
285computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) {
286 std::vector<const CFGBlock *> Preds(Block.pred_begin(), Block.pred_end());
287 if (Block.getTerminator().isTemporaryDtorsBranch()) {
288 // This handles a special case where the code that produced the CFG includes
289 // a conditional operator with a branch that constructs a temporary and
290 // calls a destructor annotated as noreturn. The CFG models this as follows:
291 //
292 // B1 (contains the condition of the conditional operator) - succs: B2, B3
293 // B2 (contains code that does not call a noreturn destructor) - succs: B4
294 // B3 (contains code that calls a noreturn destructor) - succs: B4
295 // B4 (has temporary destructor terminator) - succs: B5, B6
296 // B5 (noreturn block that is associated with the noreturn destructor call)
297 // B6 (contains code that follows the conditional operator statement)
298 //
299 // The first successor (B5 above) of a basic block with a temporary
300 // destructor terminator (B4 above) is the block that evaluates the
301 // destructor. If that block has a noreturn element then the predecessor
302 // block that constructed the temporary object (B3 above) is effectively a
303 // noreturn block and its state should not be used as input for the state
304 // of the block that has a temporary destructor terminator (B4 above). This
305 // holds regardless of which branch of the ternary operator calls the
306 // noreturn destructor. However, it doesn't cases where a nested ternary
307 // operator includes a branch that contains a noreturn destructor call.
308 //
309 // See `NoreturnDestructorTest` for concrete examples.
310 if (Block.succ_begin()->getReachableBlock() != nullptr &&
311 Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
312 auto &StmtToBlock = AC.CFCtx.getStmtToBlock();
313 auto StmtBlock = StmtToBlock.find(Block.getTerminatorStmt());
314 assert(StmtBlock != StmtToBlock.end());
315 llvm::erase(Preds, StmtBlock->getSecond());
316 }
317 }
318
319 JoinedStateBuilder Builder(AC);
320 for (const CFGBlock *Pred : Preds) {
321 // Skip if the `Block` is unreachable or control flow cannot get past it.
322 if (!Pred || Pred->hasNoReturnElement())
323 continue;
324
325 // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
326 // loop back edge to `Block`.
327 const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
328 AC.BlockStates[Pred->getBlockID()];
329 if (!MaybePredState)
330 continue;
331
332 if (AC.Analysis.builtinOptions()) {
333 if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
334 // We have a terminator: we need to mutate an environment to describe
335 // when the terminator is taken. Copy now.
336 TypeErasedDataflowAnalysisState Copy = MaybePredState->fork();
337
338 const StmtToEnvMap StmtToEnv(AC.CFCtx, AC.BlockStates);
339 auto [Cond, CondValue] =
340 TerminatorVisitor(StmtToEnv, Copy.Env,
342 .Visit(PredTerminatorStmt);
343 if (Cond != nullptr)
344 // FIXME: Call transferBranchTypeErased even if BuiltinTransferOpts
345 // are not set.
346 AC.Analysis.transferBranchTypeErased(CondValue, Cond, Copy.Lattice,
347 Copy.Env);
348 Builder.addOwned(std::move(Copy));
349 continue;
350 }
351 }
352 Builder.addUnowned(*MaybePredState);
353 }
354 return std::move(Builder).take();
355}
356
357/// Built-in transfer function for `CFGStmt`.
358static void
361 AnalysisContext &AC) {
362 const Stmt *S = Elt.getStmt();
363 assert(S != nullptr);
364 transfer(StmtToEnvMap(AC.CFCtx, AC.BlockStates), *S, InputState.Env);
365}
366
367/// Built-in transfer function for `CFGInitializer`.
368static void
372 assert(Init != nullptr);
373
374 auto &Env = InputState.Env;
375 auto &ThisLoc = *Env.getThisPointeeStorageLocation();
376
377 if (!Init->isAnyMemberInitializer())
378 // FIXME: Handle base initialization
379 return;
380
381 auto *InitExpr = Init->getInit();
382 assert(InitExpr != nullptr);
383
384 const FieldDecl *Member = nullptr;
385 RecordStorageLocation *ParentLoc = &ThisLoc;
386 StorageLocation *MemberLoc = nullptr;
387 if (Init->isMemberInitializer()) {
388 Member = Init->getMember();
389 MemberLoc = ThisLoc.getChild(*Member);
390 } else {
391 IndirectFieldDecl *IndirectField = Init->getIndirectMember();
392 assert(IndirectField != nullptr);
393 MemberLoc = &ThisLoc;
394 for (const auto *I : IndirectField->chain()) {
395 Member = cast<FieldDecl>(I);
396 ParentLoc = cast<RecordStorageLocation>(MemberLoc);
397 MemberLoc = ParentLoc->getChild(*Member);
398 }
399 }
400 assert(Member != nullptr);
401 assert(MemberLoc != nullptr);
402
403 // FIXME: Instead of these case distinctions, we would ideally want to be able
404 // to simply use `Environment::createObject()` here, the same way that we do
405 // this in `TransferVisitor::VisitInitListExpr()`. However, this would require
406 // us to be able to build a list of fields that we then use to initialize an
407 // `RecordStorageLocation` -- and the problem is that, when we get here,
408 // the `RecordStorageLocation` already exists. We should explore if there's
409 // anything that we can do to change this.
410 if (Member->getType()->isReferenceType()) {
411 auto *InitExprLoc = Env.getStorageLocation(*InitExpr);
412 if (InitExprLoc == nullptr)
413 return;
414
415 ParentLoc->setChild(*Member, InitExprLoc);
416 } else if (auto *InitExprVal = Env.getValue(*InitExpr)) {
417 if (Member->getType()->isRecordType()) {
418 auto *InitValStruct = cast<RecordValue>(InitExprVal);
419 // FIXME: Rather than performing a copy here, we should really be
420 // initializing the field in place. This would require us to propagate the
421 // storage location of the field to the AST node that creates the
422 // `RecordValue`.
423 copyRecord(InitValStruct->getLoc(),
424 *cast<RecordStorageLocation>(MemberLoc), Env);
425 } else {
426 Env.setValue(*MemberLoc, *InitExprVal);
427 }
428 }
429}
430
431static void builtinTransfer(const CFGElement &Elt,
433 AnalysisContext &AC) {
434 switch (Elt.getKind()) {
436 builtinTransferStatement(Elt.castAs<CFGStmt>(), State, AC);
437 break;
440 break;
442 // Removing declarations when their lifetime ends serves two purposes:
443 // - Eliminate unnecessary clutter from `Environment::DeclToLoc`
444 // - Allow us to assert that, when joining two `Environment`s, the two
445 // `DeclToLoc` maps never contain entries that map the same declaration to
446 // different storage locations.
447 if (const ValueDecl *VD = Elt.castAs<CFGLifetimeEnds>().getVarDecl())
448 State.Env.removeDecl(*VD);
449 break;
450 default:
451 // FIXME: Evaluate other kinds of `CFGElement`
452 break;
453 }
454}
455
456/// Transfers `State` by evaluating each element in the `Block` based on the
457/// `AC.Analysis` specified.
458///
459/// Built-in transfer functions (if the option for `ApplyBuiltinTransfer` is set
460/// by the analysis) will be applied to the element before evaluation by the
461/// user-specified analysis.
462/// `PostVisitCFG` (if provided) will be applied to the element after evaluation
463/// by the user-specified analysis.
464static TypeErasedDataflowAnalysisState
465transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC,
466 std::function<void(const CFGElement &,
468 PostVisitCFG = nullptr) {
469 AC.Log.enterBlock(Block, PostVisitCFG != nullptr);
470 auto State = computeBlockInputState(Block, AC);
471 AC.Log.recordState(State);
472 int ElementIdx = 1;
473 for (const auto &Element : Block) {
474 PrettyStackTraceCFGElement CrashInfo(Element, Block.getBlockID(),
475 ElementIdx++, "transferCFGBlock");
476
477 AC.Log.enterElement(Element);
478 // Built-in analysis
479 if (AC.Analysis.builtinOptions()) {
480 builtinTransfer(Element, State, AC);
481 }
482
483 // User-provided analysis
484 AC.Analysis.transferTypeErased(Element, State.Lattice, State.Env);
485
486 // Post processing
487 if (PostVisitCFG) {
488 PostVisitCFG(Element, State);
489 }
490 AC.Log.recordState(State);
491 }
492 return State;
493}
494
498 const Environment &InitEnv,
499 std::function<void(const CFGElement &,
501 PostVisitCFG) {
502 PrettyStackTraceAnalysis CrashInfo(CFCtx, "runTypeErasedDataflowAnalysis");
503
504 std::optional<Environment> MaybeStartingEnv;
505 if (InitEnv.callStackSize() == 1) {
506 MaybeStartingEnv = InitEnv.fork();
507 MaybeStartingEnv->initialize();
508 }
509 const Environment &StartingEnv =
510 MaybeStartingEnv ? *MaybeStartingEnv : InitEnv;
511
512 const clang::CFG &CFG = CFCtx.getCFG();
513 PostOrderCFGView POV(&CFG);
514 ForwardDataflowWorklist Worklist(CFG, &POV);
515
516 std::vector<std::optional<TypeErasedDataflowAnalysisState>> BlockStates(
517 CFG.size());
518
519 // The entry basic block doesn't contain statements so it can be skipped.
520 const CFGBlock &Entry = CFG.getEntry();
522 StartingEnv.fork()};
523 Worklist.enqueueSuccessors(&Entry);
524
525 AnalysisContext AC(CFCtx, Analysis, StartingEnv, BlockStates);
526
527 // Bugs in lattices and transfer functions can prevent the analysis from
528 // converging. To limit the damage (infinite loops) that these bugs can cause,
529 // limit the number of iterations.
530 // FIXME: Consider making the maximum number of iterations configurable.
531 // FIXME: Consider restricting the number of backedges followed, rather than
532 // iterations.
533 // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
534 // of iterations, number of functions that time out, etc.
535 static constexpr uint32_t MaxAverageVisitsPerBlock = 4;
536 static constexpr uint32_t AbsoluteMaxIterations = 1 << 16;
537 const uint32_t RelativeMaxIterations =
538 MaxAverageVisitsPerBlock * BlockStates.size();
539 const uint32_t MaxIterations =
540 std::min(RelativeMaxIterations, AbsoluteMaxIterations);
541 uint32_t Iterations = 0;
542 while (const CFGBlock *Block = Worklist.dequeue()) {
543 LLVM_DEBUG(llvm::dbgs()
544 << "Processing Block " << Block->getBlockID() << "\n");
545 if (++Iterations > MaxIterations) {
546 return llvm::createStringError(std::errc::timed_out,
547 "maximum number of iterations reached");
548 }
549
550 const std::optional<TypeErasedDataflowAnalysisState> &OldBlockState =
551 BlockStates[Block->getBlockID()];
552 TypeErasedDataflowAnalysisState NewBlockState =
554 LLVM_DEBUG({
555 llvm::errs() << "New Env:\n";
556 NewBlockState.Env.dump();
557 });
558
559 if (OldBlockState) {
560 LLVM_DEBUG({
561 llvm::errs() << "Old Env:\n";
562 OldBlockState->Env.dump();
563 });
564 if (isBackedgeNode(*Block)) {
566 NewBlockState.Lattice, OldBlockState->Lattice);
567 LatticeJoinEffect Effect2 =
568 NewBlockState.Env.widen(OldBlockState->Env, Analysis);
569 if (Effect1 == LatticeJoinEffect::Unchanged &&
570 Effect2 == LatticeJoinEffect::Unchanged) {
571 // The state of `Block` didn't change from widening so there's no need
572 // to revisit its successors.
573 AC.Log.blockConverged();
574 continue;
575 }
576 } else if (Analysis.isEqualTypeErased(OldBlockState->Lattice,
577 NewBlockState.Lattice) &&
578 OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)) {
579 // The state of `Block` didn't change after transfer so there's no need
580 // to revisit its successors.
581 AC.Log.blockConverged();
582 continue;
583 }
584 }
585
586 BlockStates[Block->getBlockID()] = std::move(NewBlockState);
587
588 // Do not add unreachable successor blocks to `Worklist`.
589 if (Block->hasNoReturnElement())
590 continue;
591
592 Worklist.enqueueSuccessors(Block);
593 }
594 // FIXME: Consider evaluating unreachable basic blocks (those that have a
595 // state set to `std::nullopt` at this point) to also analyze dead code.
596
597 if (PostVisitCFG) {
598 for (const CFGBlock *Block : CFCtx.getCFG()) {
599 // Skip blocks that were not evaluated.
600 if (!BlockStates[Block->getBlockID()])
601 continue;
602 transferCFGBlock(*Block, AC, PostVisitCFG);
603 }
604 }
605
606 return std::move(BlockStates);
607}
608
609} // namespace dataflow
610} // 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 &, QualType)
llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates
Stores the state of a CFG block if it has been evaluated by the analysis.
const ControlFlowContext & CFCtx
Contains the CFG being analyzed.
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:993
succ_iterator succ_begin()
Definition: CFG.h:983
const Stmt * getLoopTarget() const
Definition: CFG.h:1095
unsigned getBlockID() const
Definition: CFG.h:1102
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:1211
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
Definition: CFG.h:1402
CFGBlock & getEntry()
Definition: CFG.h:1317
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2293
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:194
const CFGBlock * dequeue()
Represents a member of a struct/union/class.
Definition: Decl.h:3015
Represents a field injected from an anonymous union/struct into the parent scope.
Definition: Decl.h:3293
ArrayRef< NamedDecl * > chain() const
Definition: Decl.h:3314
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:704
Holds CFG and other derived context that is needed to perform dataflow analysis.
const CFG & getCFG() const
Returns the CFG that is stored in this context.
Holds the state of the program (store and heap) at a given program point.
static Environment join(const Environment &EnvA, const Environment &EnvB, Environment::ValueModel &Model)
Joins two environments by taking the intersection of storage locations and values that are stored in ...
LatticeJoinEffect 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...
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.
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
llvm::Expected< std::vector< std::optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
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 builtinTransferInitializer(const CFGInitializer &Elt, TypeErasedDataflowAnalysisState &InputState)
Built-in transfer function for CFGInitializer.
static void builtinTransfer(const CFGElement &Elt, TypeErasedDataflowAnalysisState &State, AnalysisContext &AC)
static TypeErasedDataflowAnalysisState transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Transfers State by evaluating each element in the Block based on the AC.Analysis specified.
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:824
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)
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
void copyRecord(RecordStorageLocation &Src, RecordStorageLocation &Dst, Environment &Env)
Copies a record (struct, class, or union) from Src to Dst.
Definition: RecordOps.cpp:17
static void builtinTransferStatement(const CFGStmt &Elt, TypeErasedDataflowAnalysisState &InputState, AnalysisContext &AC)
Built-in transfer function for CFGStmt.
@ Result
The result type of a method or function.
A worklist implementation for forward dataflow analysis.
void enqueueSuccessors(const CFGBlock *Block)
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).