1 //===- CFG.h - Classes for representing and building CFGs -------*- C++ -*-===// 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 the CFG and CFGBuilder classes for representing and 10 // building Control-Flow Graphs (CFGs) from ASTs. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_ANALYSIS_CFG_H 15 #define LLVM_CLANG_ANALYSIS_CFG_H 16 17 #include "clang/AST/Attr.h" 18 #include "clang/AST/ExprCXX.h" 19 #include "clang/AST/ExprObjC.h" 20 #include "clang/Analysis/ConstructionContext.h" 21 #include "clang/Analysis/Support/BumpVector.h" 22 #include "clang/Basic/LLVM.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/GraphTraits.h" 25 #include "llvm/ADT/PointerIntPair.h" 26 #include "llvm/ADT/iterator_range.h" 27 #include "llvm/Support/Allocator.h" 28 #include "llvm/Support/raw_ostream.h" 29 #include <bitset> 30 #include <cassert> 31 #include <cstddef> 32 #include <iterator> 33 #include <memory> 34 #include <optional> 35 #include <vector> 36 37 namespace clang { 38 39 class ASTContext; 40 class BinaryOperator; 41 class CFG; 42 class CXXBaseSpecifier; 43 class CXXBindTemporaryExpr; 44 class CXXCtorInitializer; 45 class CXXDeleteExpr; 46 class CXXDestructorDecl; 47 class CXXNewExpr; 48 class CXXRecordDecl; 49 class Decl; 50 class FieldDecl; 51 class LangOptions; 52 class VarDecl; 53 54 /// Represents a top-level expression in a basic block. 55 class CFGElement { 56 public: 57 enum Kind { 58 // main kind 59 Initializer, 60 ScopeBegin, 61 ScopeEnd, 62 NewAllocator, 63 LifetimeEnds, 64 LoopExit, 65 // stmt kind 66 Statement, 67 Constructor, 68 CXXRecordTypedCall, 69 STMT_BEGIN = Statement, 70 STMT_END = CXXRecordTypedCall, 71 // dtor kind 72 AutomaticObjectDtor, 73 DeleteDtor, 74 BaseDtor, 75 MemberDtor, 76 TemporaryDtor, 77 DTOR_BEGIN = AutomaticObjectDtor, 78 DTOR_END = TemporaryDtor, 79 CleanupFunction, 80 }; 81 82 protected: 83 // The int bits are used to mark the kind. 84 llvm::PointerIntPair<void *, 2> Data1; 85 llvm::PointerIntPair<void *, 2> Data2; 86 87 CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr) 88 : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3), 89 Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) { 90 assert(getKind() == kind); 91 } 92 93 CFGElement() = default; 94 95 public: 96 /// Convert to the specified CFGElement type, asserting that this 97 /// CFGElement is of the desired type. 98 template<typename T> 99 T castAs() const { 100 assert(T::isKind(*this)); 101 T t; 102 CFGElement& e = t; 103 e = *this; 104 return t; 105 } 106 107 /// Convert to the specified CFGElement type, returning std::nullopt if this 108 /// CFGElement is not of the desired type. 109 template <typename T> std::optional<T> getAs() const { 110 if (!T::isKind(*this)) 111 return std::nullopt; 112 T t; 113 CFGElement& e = t; 114 e = *this; 115 return t; 116 } 117 118 Kind getKind() const { 119 unsigned x = Data2.getInt(); 120 x <<= 2; 121 x |= Data1.getInt(); 122 return (Kind) x; 123 } 124 125 void dumpToStream(llvm::raw_ostream &OS) const; 126 127 void dump() const { 128 dumpToStream(llvm::errs()); 129 } 130 }; 131 132 class CFGStmt : public CFGElement { 133 public: 134 explicit CFGStmt(const Stmt *S, Kind K = Statement) : CFGElement(K, S) { 135 assert(isKind(*this)); 136 } 137 138 const Stmt *getStmt() const { 139 return static_cast<const Stmt *>(Data1.getPointer()); 140 } 141 142 private: 143 friend class CFGElement; 144 145 static bool isKind(const CFGElement &E) { 146 return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END; 147 } 148 149 protected: 150 CFGStmt() = default; 151 }; 152 153 /// Represents C++ constructor call. Maintains information necessary to figure 154 /// out what memory is being initialized by the constructor expression. For now 155 /// this is only used by the analyzer's CFG. 156 class CFGConstructor : public CFGStmt { 157 public: 158 explicit CFGConstructor(const CXXConstructExpr *CE, 159 const ConstructionContext *C) 160 : CFGStmt(CE, Constructor) { 161 assert(C); 162 Data2.setPointer(const_cast<ConstructionContext *>(C)); 163 } 164 165 const ConstructionContext *getConstructionContext() const { 166 return static_cast<ConstructionContext *>(Data2.getPointer()); 167 } 168 169 private: 170 friend class CFGElement; 171 172 CFGConstructor() = default; 173 174 static bool isKind(const CFGElement &E) { 175 return E.getKind() == Constructor; 176 } 177 }; 178 179 /// Represents a function call that returns a C++ object by value. This, like 180 /// constructor, requires a construction context in order to understand the 181 /// storage of the returned object . In C such tracking is not necessary because 182 /// no additional effort is required for destroying the object or modeling copy 183 /// elision. Like CFGConstructor, this element is for now only used by the 184 /// analyzer's CFG. 185 class CFGCXXRecordTypedCall : public CFGStmt { 186 public: 187 /// Returns true when call expression \p CE needs to be represented 188 /// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt. 189 static bool isCXXRecordTypedCall(const Expr *E) { 190 assert(isa<CallExpr>(E) || isa<ObjCMessageExpr>(E)); 191 // There is no such thing as reference-type expression. If the function 192 // returns a reference, it'll return the respective lvalue or xvalue 193 // instead, and we're only interested in objects. 194 return !E->isGLValue() && 195 E->getType().getCanonicalType()->getAsCXXRecordDecl(); 196 } 197 198 explicit CFGCXXRecordTypedCall(const Expr *E, const ConstructionContext *C) 199 : CFGStmt(E, CXXRecordTypedCall) { 200 assert(isCXXRecordTypedCall(E)); 201 assert(C && (isa<TemporaryObjectConstructionContext>(C) || 202 // These are possible in C++17 due to mandatory copy elision. 203 isa<ReturnedValueConstructionContext>(C) || 204 isa<VariableConstructionContext>(C) || 205 isa<ConstructorInitializerConstructionContext>(C) || 206 isa<ArgumentConstructionContext>(C) || 207 isa<LambdaCaptureConstructionContext>(C))); 208 Data2.setPointer(const_cast<ConstructionContext *>(C)); 209 } 210 211 const ConstructionContext *getConstructionContext() const { 212 return static_cast<ConstructionContext *>(Data2.getPointer()); 213 } 214 215 private: 216 friend class CFGElement; 217 218 CFGCXXRecordTypedCall() = default; 219 220 static bool isKind(const CFGElement &E) { 221 return E.getKind() == CXXRecordTypedCall; 222 } 223 }; 224 225 /// Represents C++ base or member initializer from constructor's initialization 226 /// list. 227 class CFGInitializer : public CFGElement { 228 public: 229 explicit CFGInitializer(const CXXCtorInitializer *initializer) 230 : CFGElement(Initializer, initializer) {} 231 232 CXXCtorInitializer* getInitializer() const { 233 return static_cast<CXXCtorInitializer*>(Data1.getPointer()); 234 } 235 236 private: 237 friend class CFGElement; 238 239 CFGInitializer() = default; 240 241 static bool isKind(const CFGElement &E) { 242 return E.getKind() == Initializer; 243 } 244 }; 245 246 /// Represents C++ allocator call. 247 class CFGNewAllocator : public CFGElement { 248 public: 249 explicit CFGNewAllocator(const CXXNewExpr *S) 250 : CFGElement(NewAllocator, S) {} 251 252 // Get the new expression. 253 const CXXNewExpr *getAllocatorExpr() const { 254 return static_cast<CXXNewExpr *>(Data1.getPointer()); 255 } 256 257 private: 258 friend class CFGElement; 259 260 CFGNewAllocator() = default; 261 262 static bool isKind(const CFGElement &elem) { 263 return elem.getKind() == NewAllocator; 264 } 265 }; 266 267 /// Represents the point where a loop ends. 268 /// This element is only produced when building the CFG for the static 269 /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag. 270 /// 271 /// Note: a loop exit element can be reached even when the loop body was never 272 /// entered. 273 class CFGLoopExit : public CFGElement { 274 public: 275 explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {} 276 277 const Stmt *getLoopStmt() const { 278 return static_cast<Stmt *>(Data1.getPointer()); 279 } 280 281 private: 282 friend class CFGElement; 283 284 CFGLoopExit() = default; 285 286 static bool isKind(const CFGElement &elem) { 287 return elem.getKind() == LoopExit; 288 } 289 }; 290 291 /// Represents the point where the lifetime of an automatic object ends 292 class CFGLifetimeEnds : public CFGElement { 293 public: 294 explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt) 295 : CFGElement(LifetimeEnds, var, stmt) {} 296 297 const VarDecl *getVarDecl() const { 298 return static_cast<VarDecl *>(Data1.getPointer()); 299 } 300 301 const Stmt *getTriggerStmt() const { 302 return static_cast<Stmt *>(Data2.getPointer()); 303 } 304 305 private: 306 friend class CFGElement; 307 308 CFGLifetimeEnds() = default; 309 310 static bool isKind(const CFGElement &elem) { 311 return elem.getKind() == LifetimeEnds; 312 } 313 }; 314 315 /// Represents beginning of a scope implicitly generated 316 /// by the compiler on encountering a CompoundStmt 317 class CFGScopeBegin : public CFGElement { 318 public: 319 CFGScopeBegin() {} 320 CFGScopeBegin(const VarDecl *VD, const Stmt *S) 321 : CFGElement(ScopeBegin, VD, S) {} 322 323 // Get statement that triggered a new scope. 324 const Stmt *getTriggerStmt() const { 325 return static_cast<Stmt*>(Data2.getPointer()); 326 } 327 328 // Get VD that triggered a new scope. 329 const VarDecl *getVarDecl() const { 330 return static_cast<VarDecl *>(Data1.getPointer()); 331 } 332 333 private: 334 friend class CFGElement; 335 static bool isKind(const CFGElement &E) { 336 Kind kind = E.getKind(); 337 return kind == ScopeBegin; 338 } 339 }; 340 341 /// Represents end of a scope implicitly generated by 342 /// the compiler after the last Stmt in a CompoundStmt's body 343 class CFGScopeEnd : public CFGElement { 344 public: 345 CFGScopeEnd() {} 346 CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {} 347 348 const VarDecl *getVarDecl() const { 349 return static_cast<VarDecl *>(Data1.getPointer()); 350 } 351 352 const Stmt *getTriggerStmt() const { 353 return static_cast<Stmt *>(Data2.getPointer()); 354 } 355 356 private: 357 friend class CFGElement; 358 static bool isKind(const CFGElement &E) { 359 Kind kind = E.getKind(); 360 return kind == ScopeEnd; 361 } 362 }; 363 364 /// Represents C++ object destructor implicitly generated by compiler on various 365 /// occasions. 366 class CFGImplicitDtor : public CFGElement { 367 protected: 368 CFGImplicitDtor() = default; 369 370 CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr) 371 : CFGElement(kind, data1, data2) { 372 assert(kind >= DTOR_BEGIN && kind <= DTOR_END); 373 } 374 375 public: 376 const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const; 377 bool isNoReturn(ASTContext &astContext) const; 378 379 private: 380 friend class CFGElement; 381 382 static bool isKind(const CFGElement &E) { 383 Kind kind = E.getKind(); 384 return kind >= DTOR_BEGIN && kind <= DTOR_END; 385 } 386 }; 387 388 class CFGCleanupFunction final : public CFGElement { 389 public: 390 CFGCleanupFunction() = default; 391 CFGCleanupFunction(const VarDecl *VD) 392 : CFGElement(Kind::CleanupFunction, VD) { 393 assert(VD->hasAttr<CleanupAttr>()); 394 } 395 396 const VarDecl *getVarDecl() const { 397 return static_cast<VarDecl *>(Data1.getPointer()); 398 } 399 400 /// Returns the function to be called when cleaning up the var decl. 401 const FunctionDecl *getFunctionDecl() const { 402 const CleanupAttr *A = getVarDecl()->getAttr<CleanupAttr>(); 403 return A->getFunctionDecl(); 404 } 405 406 private: 407 friend class CFGElement; 408 409 static bool isKind(const CFGElement E) { 410 return E.getKind() == Kind::CleanupFunction; 411 } 412 }; 413 414 /// Represents C++ object destructor implicitly generated for automatic object 415 /// or temporary bound to const reference at the point of leaving its local 416 /// scope. 417 class CFGAutomaticObjDtor: public CFGImplicitDtor { 418 public: 419 CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt) 420 : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {} 421 422 const VarDecl *getVarDecl() const { 423 return static_cast<VarDecl*>(Data1.getPointer()); 424 } 425 426 // Get statement end of which triggered the destructor call. 427 const Stmt *getTriggerStmt() const { 428 return static_cast<Stmt*>(Data2.getPointer()); 429 } 430 431 private: 432 friend class CFGElement; 433 434 CFGAutomaticObjDtor() = default; 435 436 static bool isKind(const CFGElement &elem) { 437 return elem.getKind() == AutomaticObjectDtor; 438 } 439 }; 440 441 /// Represents C++ object destructor generated from a call to delete. 442 class CFGDeleteDtor : public CFGImplicitDtor { 443 public: 444 CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE) 445 : CFGImplicitDtor(DeleteDtor, RD, DE) {} 446 447 const CXXRecordDecl *getCXXRecordDecl() const { 448 return static_cast<CXXRecordDecl*>(Data1.getPointer()); 449 } 450 451 // Get Delete expression which triggered the destructor call. 452 const CXXDeleteExpr *getDeleteExpr() const { 453 return static_cast<CXXDeleteExpr *>(Data2.getPointer()); 454 } 455 456 private: 457 friend class CFGElement; 458 459 CFGDeleteDtor() = default; 460 461 static bool isKind(const CFGElement &elem) { 462 return elem.getKind() == DeleteDtor; 463 } 464 }; 465 466 /// Represents C++ object destructor implicitly generated for base object in 467 /// destructor. 468 class CFGBaseDtor : public CFGImplicitDtor { 469 public: 470 CFGBaseDtor(const CXXBaseSpecifier *base) 471 : CFGImplicitDtor(BaseDtor, base) {} 472 473 const CXXBaseSpecifier *getBaseSpecifier() const { 474 return static_cast<const CXXBaseSpecifier*>(Data1.getPointer()); 475 } 476 477 private: 478 friend class CFGElement; 479 480 CFGBaseDtor() = default; 481 482 static bool isKind(const CFGElement &E) { 483 return E.getKind() == BaseDtor; 484 } 485 }; 486 487 /// Represents C++ object destructor implicitly generated for member object in 488 /// destructor. 489 class CFGMemberDtor : public CFGImplicitDtor { 490 public: 491 CFGMemberDtor(const FieldDecl *field) 492 : CFGImplicitDtor(MemberDtor, field, nullptr) {} 493 494 const FieldDecl *getFieldDecl() const { 495 return static_cast<const FieldDecl*>(Data1.getPointer()); 496 } 497 498 private: 499 friend class CFGElement; 500 501 CFGMemberDtor() = default; 502 503 static bool isKind(const CFGElement &E) { 504 return E.getKind() == MemberDtor; 505 } 506 }; 507 508 /// Represents C++ object destructor implicitly generated at the end of full 509 /// expression for temporary object. 510 class CFGTemporaryDtor : public CFGImplicitDtor { 511 public: 512 CFGTemporaryDtor(const CXXBindTemporaryExpr *expr) 513 : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {} 514 515 const CXXBindTemporaryExpr *getBindTemporaryExpr() const { 516 return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); 517 } 518 519 private: 520 friend class CFGElement; 521 522 CFGTemporaryDtor() = default; 523 524 static bool isKind(const CFGElement &E) { 525 return E.getKind() == TemporaryDtor; 526 } 527 }; 528 529 /// Represents CFGBlock terminator statement. 530 /// 531 class CFGTerminator { 532 public: 533 enum Kind { 534 /// A branch that corresponds to a statement in the code, 535 /// such as an if-statement. 536 StmtBranch, 537 /// A branch in control flow of destructors of temporaries. In this case 538 /// terminator statement is the same statement that branches control flow 539 /// in evaluation of matching full expression. 540 TemporaryDtorsBranch, 541 /// A shortcut around virtual base initializers. It gets taken when 542 /// virtual base classes have already been initialized by the constructor 543 /// of the most derived class while we're in the base class. 544 VirtualBaseBranch, 545 546 /// Number of different kinds, for assertions. We subtract 1 so that 547 /// to keep receiving compiler warnings when we don't cover all enum values 548 /// in a switch. 549 NumKindsMinusOne = VirtualBaseBranch 550 }; 551 552 private: 553 static constexpr int KindBits = 2; 554 static_assert((1 << KindBits) > NumKindsMinusOne, 555 "Not enough room for kind!"); 556 llvm::PointerIntPair<Stmt *, KindBits> Data; 557 558 public: 559 CFGTerminator() { assert(!isValid()); } 560 CFGTerminator(Stmt *S, Kind K = StmtBranch) : Data(S, K) {} 561 562 bool isValid() const { return Data.getOpaqueValue() != nullptr; } 563 Stmt *getStmt() { return Data.getPointer(); } 564 const Stmt *getStmt() const { return Data.getPointer(); } 565 Kind getKind() const { return static_cast<Kind>(Data.getInt()); } 566 567 bool isStmtBranch() const { 568 return getKind() == StmtBranch; 569 } 570 bool isTemporaryDtorsBranch() const { 571 return getKind() == TemporaryDtorsBranch; 572 } 573 bool isVirtualBaseBranch() const { 574 return getKind() == VirtualBaseBranch; 575 } 576 }; 577 578 /// Represents a single basic block in a source-level CFG. 579 /// It consists of: 580 /// 581 /// (1) A set of statements/expressions (which may contain subexpressions). 582 /// (2) A "terminator" statement (not in the set of statements). 583 /// (3) A list of successors and predecessors. 584 /// 585 /// Terminator: The terminator represents the type of control-flow that occurs 586 /// at the end of the basic block. The terminator is a Stmt* referring to an 587 /// AST node that has control-flow: if-statements, breaks, loops, etc. 588 /// If the control-flow is conditional, the condition expression will appear 589 /// within the set of statements in the block (usually the last statement). 590 /// 591 /// Predecessors: the order in the set of predecessors is arbitrary. 592 /// 593 /// Successors: the order in the set of successors is NOT arbitrary. We 594 /// currently have the following orderings based on the terminator: 595 /// 596 /// Terminator | Successor Ordering 597 /// ------------------|------------------------------------ 598 /// if | Then Block; Else Block 599 /// ? operator | LHS expression; RHS expression 600 /// logical and/or | expression that consumes the op, RHS 601 /// vbase inits | already handled by the most derived class; not yet 602 /// 603 /// But note that any of that may be NULL in case of optimized-out edges. 604 class CFGBlock { 605 class ElementList { 606 using ImplTy = BumpVector<CFGElement>; 607 608 ImplTy Impl; 609 610 public: 611 ElementList(BumpVectorContext &C) : Impl(C, 4) {} 612 613 using iterator = std::reverse_iterator<ImplTy::iterator>; 614 using const_iterator = std::reverse_iterator<ImplTy::const_iterator>; 615 using reverse_iterator = ImplTy::iterator; 616 using const_reverse_iterator = ImplTy::const_iterator; 617 using const_reference = ImplTy::const_reference; 618 619 void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); } 620 621 reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E, 622 BumpVectorContext &C) { 623 return Impl.insert(I, Cnt, E, C); 624 } 625 626 const_reference front() const { return Impl.back(); } 627 const_reference back() const { return Impl.front(); } 628 629 iterator begin() { return Impl.rbegin(); } 630 iterator end() { return Impl.rend(); } 631 const_iterator begin() const { return Impl.rbegin(); } 632 const_iterator end() const { return Impl.rend(); } 633 reverse_iterator rbegin() { return Impl.begin(); } 634 reverse_iterator rend() { return Impl.end(); } 635 const_reverse_iterator rbegin() const { return Impl.begin(); } 636 const_reverse_iterator rend() const { return Impl.end(); } 637 638 CFGElement operator[](size_t i) const { 639 assert(i < Impl.size()); 640 return Impl[Impl.size() - 1 - i]; 641 } 642 643 size_t size() const { return Impl.size(); } 644 bool empty() const { return Impl.empty(); } 645 }; 646 647 /// A convenience class for comparing CFGElements, since methods of CFGBlock 648 /// like operator[] return CFGElements by value. This is practically a wrapper 649 /// around a (CFGBlock, Index) pair. 650 template <bool IsConst> class ElementRefImpl { 651 652 template <bool IsOtherConst> friend class ElementRefImpl; 653 654 using CFGBlockPtr = 655 std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>; 656 657 using CFGElementPtr = 658 std::conditional_t<IsConst, const CFGElement *, CFGElement *>; 659 660 protected: 661 CFGBlockPtr Parent; 662 size_t Index; 663 664 public: 665 ElementRefImpl(CFGBlockPtr Parent, size_t Index) 666 : Parent(Parent), Index(Index) {} 667 668 template <bool IsOtherConst> 669 ElementRefImpl(ElementRefImpl<IsOtherConst> Other) 670 : ElementRefImpl(Other.Parent, Other.Index) {} 671 672 size_t getIndexInBlock() const { return Index; } 673 674 CFGBlockPtr getParent() { return Parent; } 675 CFGBlockPtr getParent() const { return Parent; } 676 677 bool operator<(ElementRefImpl Other) const { 678 return std::make_pair(Parent, Index) < 679 std::make_pair(Other.Parent, Other.Index); 680 } 681 682 bool operator==(ElementRefImpl Other) const { 683 return Parent == Other.Parent && Index == Other.Index; 684 } 685 686 bool operator!=(ElementRefImpl Other) const { return !(*this == Other); } 687 CFGElement operator*() const { return (*Parent)[Index]; } 688 CFGElementPtr operator->() const { return &*(Parent->begin() + Index); } 689 690 void dumpToStream(llvm::raw_ostream &OS) const { 691 OS << getIndexInBlock() + 1 << ": "; 692 (*this)->dumpToStream(OS); 693 } 694 695 void dump() const { 696 dumpToStream(llvm::errs()); 697 } 698 }; 699 700 template <bool IsReverse, bool IsConst> class ElementRefIterator { 701 702 template <bool IsOtherReverse, bool IsOtherConst> 703 friend class ElementRefIterator; 704 705 using CFGBlockRef = 706 std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>; 707 708 using UnderlayingIteratorTy = std::conditional_t< 709 IsConst, 710 std::conditional_t<IsReverse, ElementList::const_reverse_iterator, 711 ElementList::const_iterator>, 712 std::conditional_t<IsReverse, ElementList::reverse_iterator, 713 ElementList::iterator>>; 714 715 using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>; 716 using ElementRef = typename CFGBlock::ElementRefImpl<IsConst>; 717 718 public: 719 using difference_type = typename IteratorTraits::difference_type; 720 using value_type = ElementRef; 721 using pointer = ElementRef *; 722 using iterator_category = typename IteratorTraits::iterator_category; 723 724 private: 725 CFGBlockRef Parent; 726 UnderlayingIteratorTy Pos; 727 728 public: 729 ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos) 730 : Parent(Parent), Pos(Pos) {} 731 732 template <bool IsOtherConst> 733 ElementRefIterator(ElementRefIterator<false, IsOtherConst> E) 734 : ElementRefIterator(E.Parent, E.Pos.base()) {} 735 736 template <bool IsOtherConst> 737 ElementRefIterator(ElementRefIterator<true, IsOtherConst> E) 738 : ElementRefIterator(E.Parent, std::make_reverse_iterator(E.Pos)) {} 739 740 bool operator<(ElementRefIterator Other) const { 741 assert(Parent == Other.Parent); 742 return Pos < Other.Pos; 743 } 744 745 bool operator==(ElementRefIterator Other) const { 746 return Parent == Other.Parent && Pos == Other.Pos; 747 } 748 749 bool operator!=(ElementRefIterator Other) const { 750 return !(*this == Other); 751 } 752 753 private: 754 template <bool IsOtherConst> 755 static size_t 756 getIndexInBlock(CFGBlock::ElementRefIterator<true, IsOtherConst> E) { 757 return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1; 758 } 759 760 template <bool IsOtherConst> 761 static size_t 762 getIndexInBlock(CFGBlock::ElementRefIterator<false, IsOtherConst> E) { 763 return E.Pos - E.Parent->begin(); 764 } 765 766 public: 767 value_type operator*() { return {Parent, getIndexInBlock(*this)}; } 768 769 difference_type operator-(ElementRefIterator Other) const { 770 return Pos - Other.Pos; 771 } 772 773 ElementRefIterator operator++() { 774 ++this->Pos; 775 return *this; 776 } 777 ElementRefIterator operator++(int) { 778 ElementRefIterator Ret = *this; 779 ++*this; 780 return Ret; 781 } 782 ElementRefIterator operator+(size_t count) { 783 this->Pos += count; 784 return *this; 785 } 786 ElementRefIterator operator-(size_t count) { 787 this->Pos -= count; 788 return *this; 789 } 790 }; 791 792 public: 793 /// The set of statements in the basic block. 794 ElementList Elements; 795 796 /// An (optional) label that prefixes the executable statements in the block. 797 /// When this variable is non-NULL, it is either an instance of LabelStmt, 798 /// SwitchCase or CXXCatchStmt. 799 Stmt *Label = nullptr; 800 801 /// The terminator for a basic block that indicates the type of control-flow 802 /// that occurs between a block and its successors. 803 CFGTerminator Terminator; 804 805 /// Some blocks are used to represent the "loop edge" to the start of a loop 806 /// from within the loop body. This Stmt* will be refer to the loop statement 807 /// for such blocks (and be null otherwise). 808 const Stmt *LoopTarget = nullptr; 809 810 /// A numerical ID assigned to a CFGBlock during construction of the CFG. 811 unsigned BlockID; 812 813 public: 814 /// This class represents a potential adjacent block in the CFG. It encodes 815 /// whether or not the block is actually reachable, or can be proved to be 816 /// trivially unreachable. For some cases it allows one to encode scenarios 817 /// where a block was substituted because the original (now alternate) block 818 /// is unreachable. 819 class AdjacentBlock { 820 enum Kind { 821 AB_Normal, 822 AB_Unreachable, 823 AB_Alternate 824 }; 825 826 CFGBlock *ReachableBlock; 827 llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock; 828 829 public: 830 /// Construct an AdjacentBlock with a possibly unreachable block. 831 AdjacentBlock(CFGBlock *B, bool IsReachable); 832 833 /// Construct an AdjacentBlock with a reachable block and an alternate 834 /// unreachable block. 835 AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock); 836 837 /// Get the reachable block, if one exists. 838 CFGBlock *getReachableBlock() const { 839 return ReachableBlock; 840 } 841 842 /// Get the potentially unreachable block. 843 CFGBlock *getPossiblyUnreachableBlock() const { 844 return UnreachableBlock.getPointer(); 845 } 846 847 /// Provide an implicit conversion to CFGBlock* so that 848 /// AdjacentBlock can be substituted for CFGBlock*. 849 operator CFGBlock*() const { 850 return getReachableBlock(); 851 } 852 853 CFGBlock& operator *() const { 854 return *getReachableBlock(); 855 } 856 857 CFGBlock* operator ->() const { 858 return getReachableBlock(); 859 } 860 861 bool isReachable() const { 862 Kind K = (Kind) UnreachableBlock.getInt(); 863 return K == AB_Normal || K == AB_Alternate; 864 } 865 }; 866 867 private: 868 /// Keep track of the predecessor / successor CFG blocks. 869 using AdjacentBlocks = BumpVector<AdjacentBlock>; 870 AdjacentBlocks Preds; 871 AdjacentBlocks Succs; 872 873 /// This bit is set when the basic block contains a function call 874 /// or implicit destructor that is attributed as 'noreturn'. In that case, 875 /// control cannot technically ever proceed past this block. All such blocks 876 /// will have a single immediate successor: the exit block. This allows them 877 /// to be easily reached from the exit block and using this bit quickly 878 /// recognized without scanning the contents of the block. 879 /// 880 /// Optimization Note: This bit could be profitably folded with Terminator's 881 /// storage if the memory usage of CFGBlock becomes an issue. 882 unsigned HasNoReturnElement : 1; 883 884 /// The parent CFG that owns this CFGBlock. 885 CFG *Parent; 886 887 public: 888 explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent) 889 : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1), 890 Succs(C, 1), HasNoReturnElement(false), Parent(parent) {} 891 892 // Statement iterators 893 using iterator = ElementList::iterator; 894 using const_iterator = ElementList::const_iterator; 895 using reverse_iterator = ElementList::reverse_iterator; 896 using const_reverse_iterator = ElementList::const_reverse_iterator; 897 898 size_t getIndexInCFG() const; 899 900 CFGElement front() const { return Elements.front(); } 901 CFGElement back() const { return Elements.back(); } 902 903 iterator begin() { return Elements.begin(); } 904 iterator end() { return Elements.end(); } 905 const_iterator begin() const { return Elements.begin(); } 906 const_iterator end() const { return Elements.end(); } 907 908 reverse_iterator rbegin() { return Elements.rbegin(); } 909 reverse_iterator rend() { return Elements.rend(); } 910 const_reverse_iterator rbegin() const { return Elements.rbegin(); } 911 const_reverse_iterator rend() const { return Elements.rend(); } 912 913 using CFGElementRef = ElementRefImpl<false>; 914 using ConstCFGElementRef = ElementRefImpl<true>; 915 916 using ref_iterator = ElementRefIterator<false, false>; 917 using ref_iterator_range = llvm::iterator_range<ref_iterator>; 918 using const_ref_iterator = ElementRefIterator<false, true>; 919 using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>; 920 921 using reverse_ref_iterator = ElementRefIterator<true, false>; 922 using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>; 923 924 using const_reverse_ref_iterator = ElementRefIterator<true, true>; 925 using const_reverse_ref_iterator_range = 926 llvm::iterator_range<const_reverse_ref_iterator>; 927 928 ref_iterator ref_begin() { return {this, begin()}; } 929 ref_iterator ref_end() { return {this, end()}; } 930 const_ref_iterator ref_begin() const { return {this, begin()}; } 931 const_ref_iterator ref_end() const { return {this, end()}; } 932 933 reverse_ref_iterator rref_begin() { return {this, rbegin()}; } 934 reverse_ref_iterator rref_end() { return {this, rend()}; } 935 const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; } 936 const_reverse_ref_iterator rref_end() const { return {this, rend()}; } 937 938 ref_iterator_range refs() { return {ref_begin(), ref_end()}; } 939 const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; } 940 reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; } 941 const_reverse_ref_iterator_range rrefs() const { 942 return {rref_begin(), rref_end()}; 943 } 944 945 unsigned size() const { return Elements.size(); } 946 bool empty() const { return Elements.empty(); } 947 948 CFGElement operator[](size_t i) const { return Elements[i]; } 949 950 // CFG iterators 951 using pred_iterator = AdjacentBlocks::iterator; 952 using const_pred_iterator = AdjacentBlocks::const_iterator; 953 using pred_reverse_iterator = AdjacentBlocks::reverse_iterator; 954 using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator; 955 using pred_range = llvm::iterator_range<pred_iterator>; 956 using pred_const_range = llvm::iterator_range<const_pred_iterator>; 957 958 using succ_iterator = AdjacentBlocks::iterator; 959 using const_succ_iterator = AdjacentBlocks::const_iterator; 960 using succ_reverse_iterator = AdjacentBlocks::reverse_iterator; 961 using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator; 962 using succ_range = llvm::iterator_range<succ_iterator>; 963 using succ_const_range = llvm::iterator_range<const_succ_iterator>; 964 965 pred_iterator pred_begin() { return Preds.begin(); } 966 pred_iterator pred_end() { return Preds.end(); } 967 const_pred_iterator pred_begin() const { return Preds.begin(); } 968 const_pred_iterator pred_end() const { return Preds.end(); } 969 970 pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); } 971 pred_reverse_iterator pred_rend() { return Preds.rend(); } 972 const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); } 973 const_pred_reverse_iterator pred_rend() const { return Preds.rend(); } 974 975 pred_range preds() { 976 return pred_range(pred_begin(), pred_end()); 977 } 978 979 pred_const_range preds() const { 980 return pred_const_range(pred_begin(), pred_end()); 981 } 982 983 succ_iterator succ_begin() { return Succs.begin(); } 984 succ_iterator succ_end() { return Succs.end(); } 985 const_succ_iterator succ_begin() const { return Succs.begin(); } 986 const_succ_iterator succ_end() const { return Succs.end(); } 987 988 succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); } 989 succ_reverse_iterator succ_rend() { return Succs.rend(); } 990 const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); } 991 const_succ_reverse_iterator succ_rend() const { return Succs.rend(); } 992 993 succ_range succs() { 994 return succ_range(succ_begin(), succ_end()); 995 } 996 997 succ_const_range succs() const { 998 return succ_const_range(succ_begin(), succ_end()); 999 } 1000 1001 unsigned succ_size() const { return Succs.size(); } 1002 bool succ_empty() const { return Succs.empty(); } 1003 1004 unsigned pred_size() const { return Preds.size(); } 1005 bool pred_empty() const { return Preds.empty(); } 1006 1007 1008 class FilterOptions { 1009 public: 1010 unsigned IgnoreNullPredecessors : 1; 1011 unsigned IgnoreDefaultsWithCoveredEnums : 1; 1012 1013 FilterOptions() 1014 : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {} 1015 }; 1016 1017 static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src, 1018 const CFGBlock *Dst); 1019 1020 template <typename IMPL, bool IsPred> 1021 class FilteredCFGBlockIterator { 1022 private: 1023 IMPL I, E; 1024 const FilterOptions F; 1025 const CFGBlock *From; 1026 1027 public: 1028 explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e, 1029 const CFGBlock *from, 1030 const FilterOptions &f) 1031 : I(i), E(e), F(f), From(from) { 1032 while (hasMore() && Filter(*I)) 1033 ++I; 1034 } 1035 1036 bool hasMore() const { return I != E; } 1037 1038 FilteredCFGBlockIterator &operator++() { 1039 do { ++I; } while (hasMore() && Filter(*I)); 1040 return *this; 1041 } 1042 1043 const CFGBlock *operator*() const { return *I; } 1044 1045 private: 1046 bool Filter(const CFGBlock *To) { 1047 return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To); 1048 } 1049 }; 1050 1051 using filtered_pred_iterator = 1052 FilteredCFGBlockIterator<const_pred_iterator, true>; 1053 1054 using filtered_succ_iterator = 1055 FilteredCFGBlockIterator<const_succ_iterator, false>; 1056 1057 filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const { 1058 return filtered_pred_iterator(pred_begin(), pred_end(), this, f); 1059 } 1060 1061 filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const { 1062 return filtered_succ_iterator(succ_begin(), succ_end(), this, f); 1063 } 1064 1065 // Manipulation of block contents 1066 1067 void setTerminator(CFGTerminator Term) { Terminator = Term; } 1068 void setLabel(Stmt *Statement) { Label = Statement; } 1069 void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; } 1070 void setHasNoReturnElement() { HasNoReturnElement = true; } 1071 1072 /// Returns true if the block would eventually end with a sink (a noreturn 1073 /// node). 1074 bool isInevitablySinking() const; 1075 1076 CFGTerminator getTerminator() const { return Terminator; } 1077 1078 Stmt *getTerminatorStmt() { return Terminator.getStmt(); } 1079 const Stmt *getTerminatorStmt() const { return Terminator.getStmt(); } 1080 1081 /// \returns the last (\c rbegin()) condition, e.g. observe the following code 1082 /// snippet: 1083 /// if (A && B && C) 1084 /// A block would be created for \c A, \c B, and \c C. For the latter, 1085 /// \c getTerminatorStmt() would retrieve the entire condition, rather than 1086 /// C itself, while this method would only return C. 1087 const Expr *getLastCondition() const; 1088 1089 Stmt *getTerminatorCondition(bool StripParens = true); 1090 1091 const Stmt *getTerminatorCondition(bool StripParens = true) const { 1092 return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens); 1093 } 1094 1095 const Stmt *getLoopTarget() const { return LoopTarget; } 1096 1097 Stmt *getLabel() { return Label; } 1098 const Stmt *getLabel() const { return Label; } 1099 1100 bool hasNoReturnElement() const { return HasNoReturnElement; } 1101 1102 unsigned getBlockID() const { return BlockID; } 1103 1104 CFG *getParent() const { return Parent; } 1105 1106 void dump() const; 1107 1108 void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const; 1109 void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO, 1110 bool ShowColors) const; 1111 1112 void printTerminator(raw_ostream &OS, const LangOptions &LO) const; 1113 void printTerminatorJson(raw_ostream &Out, const LangOptions &LO, 1114 bool AddQuotes) const; 1115 1116 void printAsOperand(raw_ostream &OS, bool /*PrintType*/) { 1117 OS << "BB#" << getBlockID(); 1118 } 1119 1120 /// Adds a (potentially unreachable) successor block to the current block. 1121 void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C); 1122 1123 void appendStmt(Stmt *statement, BumpVectorContext &C) { 1124 Elements.push_back(CFGStmt(statement), C); 1125 } 1126 1127 void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC, 1128 BumpVectorContext &C) { 1129 Elements.push_back(CFGConstructor(CE, CC), C); 1130 } 1131 1132 void appendCXXRecordTypedCall(Expr *E, 1133 const ConstructionContext *CC, 1134 BumpVectorContext &C) { 1135 Elements.push_back(CFGCXXRecordTypedCall(E, CC), C); 1136 } 1137 1138 void appendInitializer(CXXCtorInitializer *initializer, 1139 BumpVectorContext &C) { 1140 Elements.push_back(CFGInitializer(initializer), C); 1141 } 1142 1143 void appendNewAllocator(CXXNewExpr *NE, 1144 BumpVectorContext &C) { 1145 Elements.push_back(CFGNewAllocator(NE), C); 1146 } 1147 1148 void appendScopeBegin(const VarDecl *VD, const Stmt *S, 1149 BumpVectorContext &C) { 1150 Elements.push_back(CFGScopeBegin(VD, S), C); 1151 } 1152 1153 void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { 1154 Elements.push_back(CFGScopeEnd(VD, S), C); 1155 } 1156 1157 void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { 1158 Elements.push_back(CFGBaseDtor(BS), C); 1159 } 1160 1161 void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) { 1162 Elements.push_back(CFGMemberDtor(FD), C); 1163 } 1164 1165 void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) { 1166 Elements.push_back(CFGTemporaryDtor(E), C); 1167 } 1168 1169 void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) { 1170 Elements.push_back(CFGAutomaticObjDtor(VD, S), C); 1171 } 1172 1173 void appendCleanupFunction(const VarDecl *VD, BumpVectorContext &C) { 1174 Elements.push_back(CFGCleanupFunction(VD), C); 1175 } 1176 1177 void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) { 1178 Elements.push_back(CFGLifetimeEnds(VD, S), C); 1179 } 1180 1181 void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) { 1182 Elements.push_back(CFGLoopExit(LoopStmt), C); 1183 } 1184 1185 void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { 1186 Elements.push_back(CFGDeleteDtor(RD, DE), C); 1187 } 1188 }; 1189 1190 /// CFGCallback defines methods that should be called when a logical 1191 /// operator error is found when building the CFG. 1192 class CFGCallback { 1193 public: 1194 CFGCallback() = default; 1195 virtual ~CFGCallback() = default; 1196 1197 virtual void logicAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} 1198 virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} 1199 virtual void compareBitwiseEquality(const BinaryOperator *B, 1200 bool isAlwaysTrue) {} 1201 virtual void compareBitwiseOr(const BinaryOperator *B) {} 1202 }; 1203 1204 /// Represents a source-level, intra-procedural CFG that represents the 1205 /// control-flow of a Stmt. The Stmt can represent an entire function body, 1206 /// or a single expression. A CFG will always contain one empty block that 1207 /// represents the Exit point of the CFG. A CFG will also contain a designated 1208 /// Entry block. The CFG solely represents control-flow; it consists of 1209 /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG 1210 /// was constructed from. 1211 class CFG { 1212 public: 1213 //===--------------------------------------------------------------------===// 1214 // CFG Construction & Manipulation. 1215 //===--------------------------------------------------------------------===// 1216 1217 class BuildOptions { 1218 // Stmt::lastStmtConstant has the same value as the last Stmt kind, 1219 // so make sure we add one to account for this! 1220 std::bitset<Stmt::lastStmtConstant + 1> alwaysAddMask; 1221 1222 public: 1223 using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>; 1224 1225 ForcedBlkExprs **forcedBlkExprs = nullptr; 1226 CFGCallback *Observer = nullptr; 1227 bool PruneTriviallyFalseEdges = true; 1228 bool AddEHEdges = false; 1229 bool AddInitializers = false; 1230 bool AddImplicitDtors = false; 1231 bool AddLifetime = false; 1232 bool AddLoopExit = false; 1233 bool AddTemporaryDtors = false; 1234 bool AddScopes = false; 1235 bool AddStaticInitBranches = false; 1236 bool AddCXXNewAllocator = false; 1237 bool AddCXXDefaultInitExprInCtors = false; 1238 bool AddCXXDefaultInitExprInAggregates = false; 1239 bool AddRichCXXConstructors = false; 1240 bool MarkElidedCXXConstructors = false; 1241 bool AddVirtualBaseBranches = false; 1242 bool OmitImplicitValueInitializers = false; 1243 1244 BuildOptions() = default; 1245 1246 bool alwaysAdd(const Stmt *stmt) const { 1247 return alwaysAddMask[stmt->getStmtClass()]; 1248 } 1249 1250 BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { 1251 alwaysAddMask[stmtClass] = val; 1252 return *this; 1253 } 1254 1255 BuildOptions &setAllAlwaysAdd() { 1256 alwaysAddMask.set(); 1257 return *this; 1258 } 1259 }; 1260 1261 /// Builds a CFG from an AST. 1262 static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C, 1263 const BuildOptions &BO); 1264 1265 /// Create a new block in the CFG. The CFG owns the block; the caller should 1266 /// not directly free it. 1267 CFGBlock *createBlock(); 1268 1269 /// Set the entry block of the CFG. This is typically used only during CFG 1270 /// construction. Most CFG clients expect that the entry block has no 1271 /// predecessors and contains no statements. 1272 void setEntry(CFGBlock *B) { Entry = B; } 1273 1274 /// Set the block used for indirect goto jumps. This is typically used only 1275 /// during CFG construction. 1276 void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; } 1277 1278 //===--------------------------------------------------------------------===// 1279 // Block Iterators 1280 //===--------------------------------------------------------------------===// 1281 1282 using CFGBlockListTy = BumpVector<CFGBlock *>; 1283 using iterator = CFGBlockListTy::iterator; 1284 using const_iterator = CFGBlockListTy::const_iterator; 1285 using reverse_iterator = std::reverse_iterator<iterator>; 1286 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 1287 1288 CFGBlock & front() { return *Blocks.front(); } 1289 CFGBlock & back() { return *Blocks.back(); } 1290 1291 iterator begin() { return Blocks.begin(); } 1292 iterator end() { return Blocks.end(); } 1293 const_iterator begin() const { return Blocks.begin(); } 1294 const_iterator end() const { return Blocks.end(); } 1295 1296 iterator nodes_begin() { return iterator(Blocks.begin()); } 1297 iterator nodes_end() { return iterator(Blocks.end()); } 1298 1299 llvm::iterator_range<iterator> nodes() { return {begin(), end()}; } 1300 llvm::iterator_range<const_iterator> const_nodes() const { 1301 return {begin(), end()}; 1302 } 1303 1304 const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); } 1305 const_iterator nodes_end() const { return const_iterator(Blocks.end()); } 1306 1307 reverse_iterator rbegin() { return Blocks.rbegin(); } 1308 reverse_iterator rend() { return Blocks.rend(); } 1309 const_reverse_iterator rbegin() const { return Blocks.rbegin(); } 1310 const_reverse_iterator rend() const { return Blocks.rend(); } 1311 1312 llvm::iterator_range<reverse_iterator> reverse_nodes() { 1313 return {rbegin(), rend()}; 1314 } 1315 llvm::iterator_range<const_reverse_iterator> const_reverse_nodes() const { 1316 return {rbegin(), rend()}; 1317 } 1318 1319 CFGBlock & getEntry() { return *Entry; } 1320 const CFGBlock & getEntry() const { return *Entry; } 1321 CFGBlock & getExit() { return *Exit; } 1322 const CFGBlock & getExit() const { return *Exit; } 1323 1324 CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; } 1325 const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } 1326 1327 using try_block_iterator = std::vector<const CFGBlock *>::const_iterator; 1328 using try_block_range = llvm::iterator_range<try_block_iterator>; 1329 1330 try_block_iterator try_blocks_begin() const { 1331 return TryDispatchBlocks.begin(); 1332 } 1333 1334 try_block_iterator try_blocks_end() const { 1335 return TryDispatchBlocks.end(); 1336 } 1337 1338 try_block_range try_blocks() const { 1339 return try_block_range(try_blocks_begin(), try_blocks_end()); 1340 } 1341 1342 void addTryDispatchBlock(const CFGBlock *block) { 1343 TryDispatchBlocks.push_back(block); 1344 } 1345 1346 /// Records a synthetic DeclStmt and the DeclStmt it was constructed from. 1347 /// 1348 /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains 1349 /// multiple decls. 1350 void addSyntheticDeclStmt(const DeclStmt *Synthetic, 1351 const DeclStmt *Source) { 1352 assert(Synthetic->isSingleDecl() && "Can handle single declarations only"); 1353 assert(Synthetic != Source && "Don't include original DeclStmts in map"); 1354 assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map"); 1355 SyntheticDeclStmts[Synthetic] = Source; 1356 } 1357 1358 using synthetic_stmt_iterator = 1359 llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator; 1360 using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>; 1361 1362 /// Iterates over synthetic DeclStmts in the CFG. 1363 /// 1364 /// Each element is a (synthetic statement, source statement) pair. 1365 /// 1366 /// \sa addSyntheticDeclStmt 1367 synthetic_stmt_iterator synthetic_stmt_begin() const { 1368 return SyntheticDeclStmts.begin(); 1369 } 1370 1371 /// \sa synthetic_stmt_begin 1372 synthetic_stmt_iterator synthetic_stmt_end() const { 1373 return SyntheticDeclStmts.end(); 1374 } 1375 1376 /// \sa synthetic_stmt_begin 1377 synthetic_stmt_range synthetic_stmts() const { 1378 return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end()); 1379 } 1380 1381 //===--------------------------------------------------------------------===// 1382 // Member templates useful for various batch operations over CFGs. 1383 //===--------------------------------------------------------------------===// 1384 1385 template <typename Callback> void VisitBlockStmts(Callback &O) const { 1386 for (const_iterator I = begin(), E = end(); I != E; ++I) 1387 for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end(); 1388 BI != BE; ++BI) { 1389 if (std::optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) 1390 O(const_cast<Stmt *>(stmt->getStmt())); 1391 } 1392 } 1393 1394 //===--------------------------------------------------------------------===// 1395 // CFG Introspection. 1396 //===--------------------------------------------------------------------===// 1397 1398 /// Returns the total number of BlockIDs allocated (which start at 0). 1399 unsigned getNumBlockIDs() const { return NumBlockIDs; } 1400 1401 /// Return the total number of CFGBlocks within the CFG This is simply a 1402 /// renaming of the getNumBlockIDs(). This is necessary because the dominator 1403 /// implementation needs such an interface. 1404 unsigned size() const { return NumBlockIDs; } 1405 1406 /// Returns true if the CFG has no branches. Usually it boils down to the CFG 1407 /// having exactly three blocks (entry, the actual code, exit), but sometimes 1408 /// more blocks appear due to having control flow that can be fully 1409 /// resolved in compile time. 1410 bool isLinear() const; 1411 1412 //===--------------------------------------------------------------------===// 1413 // CFG Debugging: Pretty-Printing and Visualization. 1414 //===--------------------------------------------------------------------===// 1415 1416 void viewCFG(const LangOptions &LO) const; 1417 void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const; 1418 void dump(const LangOptions &LO, bool ShowColors) const; 1419 1420 //===--------------------------------------------------------------------===// 1421 // Internal: constructors and data. 1422 //===--------------------------------------------------------------------===// 1423 1424 CFG() : Blocks(BlkBVC, 10) {} 1425 1426 llvm::BumpPtrAllocator& getAllocator() { 1427 return BlkBVC.getAllocator(); 1428 } 1429 1430 BumpVectorContext &getBumpVectorContext() { 1431 return BlkBVC; 1432 } 1433 1434 private: 1435 CFGBlock *Entry = nullptr; 1436 CFGBlock *Exit = nullptr; 1437 1438 // Special block to contain collective dispatch for indirect gotos 1439 CFGBlock* IndirectGotoBlock = nullptr; 1440 1441 unsigned NumBlockIDs = 0; 1442 1443 BumpVectorContext BlkBVC; 1444 1445 CFGBlockListTy Blocks; 1446 1447 /// C++ 'try' statements are modeled with an indirect dispatch block. 1448 /// This is the collection of such blocks present in the CFG. 1449 std::vector<const CFGBlock *> TryDispatchBlocks; 1450 1451 /// Collects DeclStmts synthesized for this CFG and maps each one back to its 1452 /// source DeclStmt. 1453 llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; 1454 }; 1455 1456 Expr *extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE); 1457 1458 } // namespace clang 1459 1460 //===----------------------------------------------------------------------===// 1461 // GraphTraits specializations for CFG basic block graphs (source-level CFGs) 1462 //===----------------------------------------------------------------------===// 1463 1464 namespace llvm { 1465 1466 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from 1467 /// CFGTerminator to a specific Stmt class. 1468 template <> struct simplify_type< ::clang::CFGTerminator> { 1469 using SimpleType = ::clang::Stmt *; 1470 1471 static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) { 1472 return Val.getStmt(); 1473 } 1474 }; 1475 1476 // Traits for: CFGBlock 1477 1478 template <> struct GraphTraits< ::clang::CFGBlock *> { 1479 using NodeRef = ::clang::CFGBlock *; 1480 using ChildIteratorType = ::clang::CFGBlock::succ_iterator; 1481 1482 static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; } 1483 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 1484 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 1485 }; 1486 1487 template <> struct GraphTraits< const ::clang::CFGBlock *> { 1488 using NodeRef = const ::clang::CFGBlock *; 1489 using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator; 1490 1491 static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; } 1492 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 1493 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 1494 }; 1495 1496 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> { 1497 using NodeRef = ::clang::CFGBlock *; 1498 using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; 1499 1500 static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) { 1501 return G.Graph; 1502 } 1503 1504 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } 1505 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } 1506 }; 1507 1508 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> { 1509 using NodeRef = const ::clang::CFGBlock *; 1510 using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; 1511 1512 static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) { 1513 return G.Graph; 1514 } 1515 1516 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } 1517 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } 1518 }; 1519 1520 // Traits for: CFG 1521 1522 template <> struct GraphTraits< ::clang::CFG* > 1523 : public GraphTraits< ::clang::CFGBlock *> { 1524 using nodes_iterator = ::clang::CFG::iterator; 1525 1526 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); } 1527 static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} 1528 static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } 1529 static unsigned size(::clang::CFG* F) { return F->size(); } 1530 }; 1531 1532 template <> struct GraphTraits<const ::clang::CFG* > 1533 : public GraphTraits<const ::clang::CFGBlock *> { 1534 using nodes_iterator = ::clang::CFG::const_iterator; 1535 1536 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); } 1537 1538 static nodes_iterator nodes_begin( const ::clang::CFG* F) { 1539 return F->nodes_begin(); 1540 } 1541 1542 static nodes_iterator nodes_end( const ::clang::CFG* F) { 1543 return F->nodes_end(); 1544 } 1545 1546 static unsigned size(const ::clang::CFG* F) { 1547 return F->size(); 1548 } 1549 }; 1550 1551 template <> struct GraphTraits<Inverse< ::clang::CFG *>> 1552 : public GraphTraits<Inverse< ::clang::CFGBlock *>> { 1553 using nodes_iterator = ::clang::CFG::iterator; 1554 1555 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); } 1556 static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} 1557 static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } 1558 }; 1559 1560 template <> struct GraphTraits<Inverse<const ::clang::CFG *>> 1561 : public GraphTraits<Inverse<const ::clang::CFGBlock *>> { 1562 using nodes_iterator = ::clang::CFG::const_iterator; 1563 1564 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); } 1565 1566 static nodes_iterator nodes_begin(const ::clang::CFG* F) { 1567 return F->nodes_begin(); 1568 } 1569 1570 static nodes_iterator nodes_end(const ::clang::CFG* F) { 1571 return F->nodes_end(); 1572 } 1573 }; 1574 1575 } // namespace llvm 1576 1577 #endif // LLVM_CLANG_ANALYSIS_CFG_H 1578