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