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