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