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 <cstddef>
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"
22#include "clang/AST/OperationKinds.h"
23#include "clang/AST/Stmt.h"
24#include "clang/AST/StmtCXX.h"
25#include "clang/AST/StmtVisitor.h"
26#include "clang/Analysis/Analyses/PostOrderCFGView.h"
27#include "clang/Analysis/CFG.h"
28#include "clang/Analysis/CFGBackEdges.h"
29#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
30#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
31#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
32#include "clang/Analysis/FlowSensitive/Transfer.h"
33#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
34#include "clang/Analysis/FlowSensitive/Value.h"
35#include "clang/Basic/LLVM.h"
36#include "clang/Support/Compiler.h"
37#include "llvm/ADT/ArrayRef.h"
38#include "llvm/ADT/BitVector.h"
39#include "llvm/ADT/DenseMap.h"
40#include "llvm/ADT/DenseSet.h"
41#include "llvm/ADT/STLExtras.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/Error.h"
44
45#define DEBUG_TYPE "clang-dataflow"
46
47namespace clang {
48namespace dataflow {
49class NoopLattice;
50}
51} // namespace clang
52
53namespace llvm {
54// This needs to be exported for ClangAnalysisFlowSensitiveTests so any_cast
55// uses the correct address of Any::TypeId from the clang shared library instead
56// of creating one in the test executable. when building with
57// CLANG_LINK_CLANG_DYLIB
58template struct CLANG_EXPORT_TEMPLATE Any::TypeId<clang::dataflow::NoopLattice>;
59} // namespace llvm
60
61namespace clang {
62namespace dataflow {
63
64/// Returns the index of `Block` in the successors of `Pred`.
65static int blockIndexInPredecessor(const CFGBlock &Pred,
66 const CFGBlock &Block) {
67 auto BlockPos = llvm::find_if(
68 Range: Pred.succs(), P: [&Block](const CFGBlock::AdjacentBlock &Succ) {
69 return Succ && Succ->getBlockID() == Block.getBlockID();
70 });
71 return BlockPos - Pred.succ_begin();
72}
73
74namespace {
75
76/// Extracts the terminator's condition expression.
77class TerminatorVisitor
78 : public ConstStmtVisitor<TerminatorVisitor, const Expr *> {
79public:
80 TerminatorVisitor() = default;
81 const Expr *VisitIfStmt(const IfStmt *S) { return S->getCond(); }
82 const Expr *VisitWhileStmt(const WhileStmt *S) { return S->getCond(); }
83 const Expr *VisitDoStmt(const DoStmt *S) { return S->getCond(); }
84 const Expr *VisitForStmt(const ForStmt *S) { return S->getCond(); }
85 const Expr *VisitCXXForRangeStmt(const CXXForRangeStmt *) {
86 // Don't do anything special for CXXForRangeStmt, because the condition
87 // (being implicitly generated) isn't visible from the loop body.
88 return nullptr;
89 }
90 const Expr *VisitBinaryOperator(const BinaryOperator *S) {
91 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
92 return S->getLHS();
93 }
94 const Expr *VisitConditionalOperator(const ConditionalOperator *S) {
95 return S->getCond();
96 }
97};
98
99/// Holds data structures required for running dataflow analysis.
100struct AnalysisContext {
101 AnalysisContext(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
102 const Environment &InitEnv,
103 llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
104 BlockStates)
105 : ACFG(ACFG), Analysis(Analysis), InitEnv(InitEnv),
106 Log(*InitEnv.getDataflowAnalysisContext().getOptions().Log),
107 BlockStates(BlockStates) {
108 Log.beginAnalysis(ACFG, Analysis);
109 }
110 ~AnalysisContext() { Log.endAnalysis(); }
111
112 /// Contains the CFG being analyzed.
113 const AdornedCFG &ACFG;
114 /// The analysis to be run.
115 TypeErasedDataflowAnalysis &Analysis;
116 /// Initial state to start the analysis.
117 const Environment &InitEnv;
118 Logger &Log;
119 /// Stores the state of a CFG block if it has been evaluated by the analysis.
120 /// The indices correspond to the block IDs.
121 llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates;
122};
123
124class PrettyStackTraceAnalysis : public llvm::PrettyStackTraceEntry {
125public:
126 PrettyStackTraceAnalysis(const AdornedCFG &ACFG, const char *Message)
127 : ACFG(ACFG), Message(Message) {}
128
129 void print(raw_ostream &OS) const override {
130 OS << Message << "\n";
131 OS << "Decl:\n";
132 ACFG.getDecl().dump(Out&: OS);
133 OS << "CFG:\n";
134 ACFG.getCFG().print(OS, LO: LangOptions(), ShowColors: false);
135 }
136
137private:
138 const AdornedCFG &ACFG;
139 const char *Message;
140};
141
142class PrettyStackTraceCFGElement : public llvm::PrettyStackTraceEntry {
143public:
144 PrettyStackTraceCFGElement(const CFGElement &Element, int BlockIdx,
145 int ElementIdx, const char *Message)
146 : Element(Element), BlockIdx(BlockIdx), ElementIdx(ElementIdx),
147 Message(Message) {}
148
149 void print(raw_ostream &OS) const override {
150 OS << Message << ": Element [B" << BlockIdx << "." << ElementIdx << "]\n";
151 if (auto Stmt = Element.getAs<CFGStmt>()) {
152 OS << "Stmt:\n";
153 ASTDumper Dumper(OS, false);
154 Dumper.Visit(Node: Stmt->getStmt());
155 }
156 }
157
158private:
159 const CFGElement &Element;
160 int BlockIdx;
161 int ElementIdx;
162 const char *Message;
163};
164
165// Builds a joined TypeErasedDataflowAnalysisState from 0 or more sources,
166// each of which may be owned (built as part of the join) or external (a
167// reference to an Environment that will outlive the builder).
168// Avoids unneccesary copies of the environment.
169class JoinedStateBuilder {
170 AnalysisContext &AC;
171 Environment::ExprJoinBehavior JoinBehavior;
172 std::vector<const TypeErasedDataflowAnalysisState *> All;
173 std::deque<TypeErasedDataflowAnalysisState> Owned;
174
175 TypeErasedDataflowAnalysisState
176 join(const TypeErasedDataflowAnalysisState &L,
177 const TypeErasedDataflowAnalysisState &R) {
178 return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),
179 Environment::join(EnvA: L.Env, EnvB: R.Env, Model&: AC.Analysis, ExprBehavior: JoinBehavior)};
180 }
181
182public:
183 JoinedStateBuilder(AnalysisContext &AC,
184 Environment::ExprJoinBehavior JoinBehavior)
185 : AC(AC), JoinBehavior(JoinBehavior) {}
186
187 void addOwned(TypeErasedDataflowAnalysisState State) {
188 Owned.push_back(x: std::move(State));
189 All.push_back(x: &Owned.back());
190 }
191 void addUnowned(const TypeErasedDataflowAnalysisState &State) {
192 All.push_back(x: &State);
193 }
194 TypeErasedDataflowAnalysisState take() && {
195 if (All.empty())
196 // FIXME: Consider passing `Block` to Analysis.typeErasedInitialElement
197 // to enable building analyses like computation of dominators that
198 // initialize the state of each basic block differently.
199 return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};
200 if (All.size() == 1)
201 // Join the environment with itself so that we discard expression state if
202 // desired.
203 // FIXME: We could consider writing special-case code for this that only
204 // does the discarding, but it's not clear if this is worth it.
205 return {All[0]->Lattice, Environment::join(EnvA: All[0]->Env, EnvB: All[0]->Env,
206 Model&: AC.Analysis, ExprBehavior: JoinBehavior)};
207
208 auto Result = join(L: *All[0], R: *All[1]);
209 for (unsigned I = 2; I < All.size(); ++I)
210 Result = join(L: Result, R: *All[I]);
211 return Result;
212 }
213};
214} // namespace
215
216static const Expr *getTerminatorCondition(const Stmt *TerminatorStmt) {
217 return TerminatorStmt == nullptr ? nullptr
218 : TerminatorVisitor().Visit(S: TerminatorStmt);
219}
220
221/// Computes the input state for a given basic block by joining the output
222/// states of its predecessors.
223///
224/// Requirements:
225///
226/// All predecessors of `Block` except those with loop back edges must have
227/// already been transferred. States in `AC.BlockStates` that are set to
228/// `std::nullopt` represent basic blocks that are not evaluated yet.
229static TypeErasedDataflowAnalysisState
230computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC) {
231 std::vector<const CFGBlock *> Preds(Block.pred_begin(), Block.pred_end());
232 if (Block.getTerminator().isTemporaryDtorsBranch()) {
233 // This handles a special case where the code that produced the CFG includes
234 // a conditional operator with a branch that constructs a temporary and
235 // calls a destructor annotated as noreturn. The CFG models this as follows:
236 //
237 // B1 (contains the condition of the conditional operator) - succs: B2, B3
238 // B2 (contains code that does not call a noreturn destructor) - succs: B4
239 // B3 (contains code that calls a noreturn destructor) - succs: B4
240 // B4 (has temporary destructor terminator) - succs: B5, B6
241 // B5 (noreturn block that is associated with the noreturn destructor call)
242 // B6 (contains code that follows the conditional operator statement)
243 //
244 // The first successor (B5 above) of a basic block with a temporary
245 // destructor terminator (B4 above) is the block that evaluates the
246 // destructor. If that block has a noreturn element then the predecessor
247 // block that constructed the temporary object (B3 above) is effectively a
248 // noreturn block and its state should not be used as input for the state
249 // of the block that has a temporary destructor terminator (B4 above). This
250 // holds regardless of which branch of the ternary operator calls the
251 // noreturn destructor. However, it doesn't cases where a nested ternary
252 // operator includes a branch that contains a noreturn destructor call.
253 //
254 // See `NoreturnDestructorTest` for concrete examples.
255 if (Block.succ_begin()->getReachableBlock() != nullptr &&
256 Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
257 const CFGBlock *StmtBlock = nullptr;
258 if (const Stmt *Terminator = Block.getTerminatorStmt())
259 StmtBlock = AC.ACFG.blockForStmt(S: *Terminator);
260 assert(StmtBlock != nullptr);
261 llvm::erase(C&: Preds, V: StmtBlock);
262 }
263 }
264
265 // If any of the predecessor blocks contains an expression consumed in a
266 // different block, we need to keep expression state.
267 // Note that in this case, we keep expression state for all predecessors,
268 // rather than only those predecessors that actually contain an expression
269 // consumed in a different block. While this is potentially suboptimal, it's
270 // actually likely, if we have control flow within a full expression, that
271 // all predecessors have expression state consumed in a different block.
272 Environment::ExprJoinBehavior JoinBehavior = Environment::DiscardExprState;
273 for (const CFGBlock *Pred : Preds) {
274 if (Pred && AC.ACFG.containsExprConsumedInDifferentBlock(B: *Pred)) {
275 JoinBehavior = Environment::KeepExprState;
276 break;
277 }
278 }
279
280 JoinedStateBuilder Builder(AC, JoinBehavior);
281 for (const CFGBlock *Pred : Preds) {
282 // Skip if the `Block` is unreachable or control flow cannot get past it.
283 if (!Pred || Pred->hasNoReturnElement())
284 continue;
285
286 // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
287 // loop back edge to `Block`.
288 const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
289 AC.BlockStates[Pred->getBlockID()];
290 if (!MaybePredState)
291 continue;
292
293 const TypeErasedDataflowAnalysisState &PredState = *MaybePredState;
294 const Expr *Cond = getTerminatorCondition(TerminatorStmt: Pred->getTerminatorStmt());
295 if (Cond == nullptr) {
296 Builder.addUnowned(State: PredState);
297 continue;
298 }
299
300 bool BranchVal = blockIndexInPredecessor(Pred: *Pred, Block) == 0;
301
302 // `transferBranch` may need to mutate the environment to describe the
303 // dynamic effect of the terminator for a given branch. Copy now.
304 TypeErasedDataflowAnalysisState Copy = MaybePredState->fork();
305 if (AC.Analysis.builtinOptions()) {
306 auto *CondVal = Copy.Env.get<BoolValue>(E: *Cond);
307 // In transferCFGBlock(), we ensure that we always have a `Value`
308 // for the terminator condition, so assert this. We consciously
309 // assert ourselves instead of asserting via `cast()` so that we get
310 // a more meaningful line number if the assertion fails.
311 assert(CondVal != nullptr);
312 BoolValue *AssertedVal =
313 BranchVal ? CondVal : &Copy.Env.makeNot(Val&: *CondVal);
314 Copy.Env.assume(AssertedVal->formula());
315 }
316 AC.Analysis.transferBranchTypeErased(Branch: BranchVal, Cond, Copy.Lattice,
317 Copy.Env);
318 Builder.addOwned(State: std::move(Copy));
319 }
320 return std::move(Builder).take();
321}
322
323/// Built-in transfer function for `CFGStmt`.
324static void
325builtinTransferStatement(unsigned CurBlockID, const CFGStmt &Elt,
326 TypeErasedDataflowAnalysisState &InputState,
327 AnalysisContext &AC) {
328 const Stmt *S = Elt.getStmt();
329 assert(S != nullptr);
330 transfer(StmtToEnv: StmtToEnvMap(AC.ACFG, AC.BlockStates, CurBlockID, InputState), S: *S,
331 Env&: InputState.Env, Model&: AC.Analysis);
332}
333
334/// Built-in transfer function for `CFGInitializer`.
335static void
336builtinTransferInitializer(const CFGInitializer &Elt,
337 TypeErasedDataflowAnalysisState &InputState) {
338 const CXXCtorInitializer *Init = Elt.getInitializer();
339 assert(Init != nullptr);
340
341 auto &Env = InputState.Env;
342 auto &ThisLoc = *Env.getThisPointeeStorageLocation();
343
344 if (!Init->isAnyMemberInitializer())
345 // FIXME: Handle base initialization
346 return;
347
348 auto *InitExpr = Init->getInit();
349 assert(InitExpr != nullptr);
350
351 const FieldDecl *Member = nullptr;
352 RecordStorageLocation *ParentLoc = &ThisLoc;
353 StorageLocation *MemberLoc = nullptr;
354 if (Init->isMemberInitializer()) {
355 Member = Init->getMember();
356 MemberLoc = ThisLoc.getChild(D: *Member);
357 } else {
358 IndirectFieldDecl *IndirectField = Init->getIndirectMember();
359 assert(IndirectField != nullptr);
360 MemberLoc = &ThisLoc;
361 for (const auto *I : IndirectField->chain()) {
362 Member = cast<FieldDecl>(Val: I);
363 ParentLoc = cast<RecordStorageLocation>(Val: MemberLoc);
364 MemberLoc = ParentLoc->getChild(D: *Member);
365 }
366 }
367 assert(Member != nullptr);
368
369 // FIXME: Instead of these case distinctions, we would ideally want to be able
370 // to simply use `Environment::createObject()` here, the same way that we do
371 // this in `TransferVisitor::VisitInitListExpr()`. However, this would require
372 // us to be able to build a list of fields that we then use to initialize an
373 // `RecordStorageLocation` -- and the problem is that, when we get here,
374 // the `RecordStorageLocation` already exists. We should explore if there's
375 // anything that we can do to change this.
376 if (Member->getType()->isReferenceType()) {
377 auto *InitExprLoc = Env.getStorageLocation(E: *InitExpr);
378 if (InitExprLoc == nullptr)
379 return;
380
381 ParentLoc->setChild(D: *Member, Loc: InitExprLoc);
382 // Record-type initializers construct themselves directly into the result
383 // object, so there is no need to handle them here.
384 } else if (!Member->getType()->isRecordType()) {
385 assert(MemberLoc != nullptr);
386 if (auto *InitExprVal = Env.getValue(E: *InitExpr))
387 Env.setValue(Loc: *MemberLoc, Val&: *InitExprVal);
388 }
389}
390
391static void builtinTransfer(unsigned CurBlockID, const CFGElement &Elt,
392 TypeErasedDataflowAnalysisState &State,
393 AnalysisContext &AC) {
394 switch (Elt.getKind()) {
395 case CFGElement::Statement:
396 builtinTransferStatement(CurBlockID, Elt: Elt.castAs<CFGStmt>(), InputState&: State, AC);
397 break;
398 case CFGElement::Initializer:
399 builtinTransferInitializer(Elt: Elt.castAs<CFGInitializer>(), InputState&: State);
400 break;
401 case CFGElement::LifetimeEnds:
402 // Removing declarations when their lifetime ends serves two purposes:
403 // - Eliminate unnecessary clutter from `Environment::DeclToLoc`
404 // - Allow us to assert that, when joining two `Environment`s, the two
405 // `DeclToLoc` maps never contain entries that map the same declaration to
406 // different storage locations.
407 if (const ValueDecl *VD = Elt.castAs<CFGLifetimeEnds>().getVarDecl())
408 State.Env.removeDecl(D: *VD);
409 break;
410 default:
411 // FIXME: Evaluate other kinds of `CFGElement`
412 break;
413 }
414}
415
416/// Transfers `State` by evaluating each element in the `Block` based on the
417/// `AC.Analysis` specified.
418///
419/// Built-in transfer functions (if the option for `ApplyBuiltinTransfer` is set
420/// by the analysis) will be applied to the element before evaluation by the
421/// user-specified analysis.
422/// `PostVisitCFG` (if provided) will be applied to the element after evaluation
423/// by the user-specified analysis.
424static TypeErasedDataflowAnalysisState
425transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC,
426 const CFGEltCallbacksTypeErased &PostAnalysisCallbacks = {}) {
427 AC.Log.enterBlock(Block, PostVisit: PostAnalysisCallbacks.Before != nullptr ||
428 PostAnalysisCallbacks.After != nullptr);
429 auto State = computeBlockInputState(Block, AC);
430 AC.Log.recordState(State);
431 int ElementIdx = 1;
432 for (const auto &Element : Block) {
433 PrettyStackTraceCFGElement CrashInfo(Element, Block.getBlockID(),
434 ElementIdx++, "transferCFGBlock");
435
436 AC.Log.enterElement(Element);
437
438 if (PostAnalysisCallbacks.Before) {
439 PostAnalysisCallbacks.Before(Element, State);
440 }
441
442 // Built-in analysis
443 if (AC.Analysis.builtinOptions()) {
444 builtinTransfer(CurBlockID: Block.getBlockID(), Elt: Element, State, AC);
445 }
446
447 // User-provided analysis
448 AC.Analysis.transferTypeErased(Element, State.Lattice, State.Env);
449
450 if (PostAnalysisCallbacks.After) {
451 PostAnalysisCallbacks.After(Element, State);
452 }
453
454 AC.Log.recordState(State);
455 }
456
457 // If we have a terminator, evaluate its condition.
458 // This `Expr` may not appear as a `CFGElement` anywhere else, and it's
459 // important that we evaluate it here (rather than while processing the
460 // terminator) so that we put the corresponding value in the right
461 // environment.
462 if (const Expr *TerminatorCond =
463 dyn_cast_or_null<Expr>(Val: Block.getTerminatorCondition())) {
464 if (State.Env.getValue(E: *TerminatorCond) == nullptr)
465 // FIXME: This only runs the builtin transfer, not the analysis-specific
466 // transfer. Fixing this isn't trivial, as the analysis-specific transfer
467 // takes a `CFGElement` as input, but some expressions only show up as a
468 // terminator condition, but not as a `CFGElement`. The condition of an if
469 // statement is one such example.
470 transfer(StmtToEnv: StmtToEnvMap(AC.ACFG, AC.BlockStates, Block.getBlockID(), State),
471 S: *TerminatorCond, Env&: State.Env, Model&: AC.Analysis);
472
473 // If the transfer function didn't produce a value, create an atom so that
474 // we have *some* value for the condition expression. This ensures that
475 // when we extend the flow condition, it actually changes.
476 if (State.Env.getValue(E: *TerminatorCond) == nullptr)
477 State.Env.setValue(E: *TerminatorCond, Val&: State.Env.makeAtomicBoolValue());
478 AC.Log.recordState(State);
479 }
480
481 return State;
482}
483
484// Returns the number of reachable blocks (would be visited if we only visit
485// each reachable block once). This is a light version of the main fixpoint loop
486// (keep in sync).
487size_t NumReachableBlocks(const CFG &CFG) {
488 PostOrderCFGView POV(&CFG);
489 ForwardDataflowWorklist Worklist(CFG, &POV);
490 llvm::BitVector VisitedBlocks(CFG.size());
491 const CFGBlock &Entry = CFG.getEntry();
492 Worklist.enqueueSuccessors(Block: &Entry);
493 while (const CFGBlock *Block = Worklist.dequeue()) {
494 if (VisitedBlocks[Block->getBlockID()])
495 continue;
496 VisitedBlocks[Block->getBlockID()] = true;
497 // Do not add unreachable successor blocks to `Worklist`.
498 if (Block->hasNoReturnElement())
499 continue;
500 Worklist.enqueueSuccessors(Block);
501 }
502 return VisitedBlocks.count();
503}
504
505llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>>
506runTypeErasedDataflowAnalysis(
507 const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
508 const Environment &InitEnv,
509 const CFGEltCallbacksTypeErased &PostAnalysisCallbacks,
510 std::int32_t MaxBlockVisits) {
511 PrettyStackTraceAnalysis CrashInfo(ACFG, "runTypeErasedDataflowAnalysis");
512
513 std::optional<Environment> MaybeStartingEnv;
514 if (InitEnv.callStackSize() == 0) {
515 MaybeStartingEnv = InitEnv.fork();
516 MaybeStartingEnv->initialize();
517 }
518 const Environment &StartingEnv =
519 MaybeStartingEnv ? *MaybeStartingEnv : InitEnv;
520
521 const clang::CFG &CFG = ACFG.getCFG();
522
523 // Bail out if the number of reachable blocks is already beyond the maximum
524 // number of block visits to save time and avoid running out of memory for
525 // massive CFGs. Note: CFG.size() could have unreachable blocks,
526 // but it is a faster to compare that to MaxBlockVisits first before doing the
527 // reachable block count.
528 if (CFG.size() > static_cast<size_t>(MaxBlockVisits) &&
529 NumReachableBlocks(CFG) > static_cast<size_t>(MaxBlockVisits)) {
530 return llvm::createStringError(EC: std::errc::timed_out,
531 Fmt: "number of blocks in cfg will lead to "
532 "exceeding maximum number of block visits");
533 }
534
535 PostOrderCFGView POV(&CFG);
536 ForwardDataflowWorklist Worklist(CFG, &POV);
537 llvm::SmallDenseSet<const CFGBlock *> NonStructLoopBackedgeNodes =
538 findNonStructuredLoopBackedgeNodes(CFG);
539
540 std::vector<std::optional<TypeErasedDataflowAnalysisState>> BlockStates(
541 CFG.size());
542
543 // The entry basic block doesn't contain statements so it can be skipped.
544 const CFGBlock &Entry = CFG.getEntry();
545 BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
546 StartingEnv.fork()};
547 Worklist.enqueueSuccessors(Block: &Entry);
548
549 AnalysisContext AC(ACFG, Analysis, StartingEnv, BlockStates);
550 std::int32_t BlockVisits = 0;
551 while (const CFGBlock *Block = Worklist.dequeue()) {
552 LLVM_DEBUG(llvm::dbgs()
553 << "Processing Block " << Block->getBlockID() << "\n");
554 if (++BlockVisits > MaxBlockVisits) {
555 return llvm::createStringError(EC: std::errc::timed_out,
556 Fmt: "maximum number of blocks processed");
557 }
558
559 const std::optional<TypeErasedDataflowAnalysisState> &OldBlockState =
560 BlockStates[Block->getBlockID()];
561 TypeErasedDataflowAnalysisState NewBlockState =
562 transferCFGBlock(Block: *Block, AC);
563 LLVM_DEBUG({
564 llvm::errs() << "New Env:\n";
565 NewBlockState.Env.dump();
566 });
567
568 if (OldBlockState) {
569 LLVM_DEBUG({
570 llvm::errs() << "Old Env:\n";
571 OldBlockState->Env.dump();
572 });
573 if (isBackedgeCFGNode(B: *Block, NonStructLoopBackedgeNodes)) {
574 LatticeJoinEffect Effect1 = Analysis.widenTypeErased(
575 Current&: NewBlockState.Lattice, Previous: OldBlockState->Lattice);
576 LatticeJoinEffect Effect2 =
577 NewBlockState.Env.widen(PrevEnv: OldBlockState->Env, Model&: Analysis);
578 if (Effect1 == LatticeJoinEffect::Unchanged &&
579 Effect2 == LatticeJoinEffect::Unchanged) {
580 // The state of `Block` didn't change from widening so there's no need
581 // to revisit its successors.
582 AC.Log.blockConverged();
583 continue;
584 }
585 } else if (Analysis.isEqualTypeErased(OldBlockState->Lattice,
586 NewBlockState.Lattice) &&
587 OldBlockState->Env.equivalentTo(Other: NewBlockState.Env, Model&: Analysis)) {
588 // The state of `Block` didn't change after transfer so there's no need
589 // to revisit its successors.
590 AC.Log.blockConverged();
591 continue;
592 }
593 }
594
595 BlockStates[Block->getBlockID()] = std::move(NewBlockState);
596
597 // Do not add unreachable successor blocks to `Worklist`.
598 if (Block->hasNoReturnElement())
599 continue;
600
601 Worklist.enqueueSuccessors(Block);
602 }
603 // FIXME: Consider evaluating unreachable basic blocks (those that have a
604 // state set to `std::nullopt` at this point) to also analyze dead code.
605
606 if (PostAnalysisCallbacks.Before || PostAnalysisCallbacks.After) {
607 for (const CFGBlock *Block : ACFG.getCFG()) {
608 // Skip blocks that were not evaluated.
609 if (!BlockStates[Block->getBlockID()])
610 continue;
611 transferCFGBlock(Block: *Block, AC, PostAnalysisCallbacks);
612 }
613 }
614
615 return std::move(BlockStates);
616}
617
618} // namespace dataflow
619} // namespace clang
620