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