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 isa<LambdaCaptureConstructionContext>(C))); 207 Data2.setPointer(const_cast<ConstructionContext *>(C)); 208 } 209 210 const ConstructionContext *getConstructionContext() const { 211 return static_cast<ConstructionContext *>(Data2.getPointer()); 212 } 213 214 private: 215 friend class CFGElement; 216 217 CFGCXXRecordTypedCall() = default; 218 219 static bool isKind(const CFGElement &E) { 220 return E.getKind() == CXXRecordTypedCall; 221 } 222 }; 223 224 /// Represents C++ base or member initializer from constructor's initialization 225 /// list. 226 class CFGInitializer : public CFGElement { 227 public: 228 explicit CFGInitializer(CXXCtorInitializer *initializer) 229 : CFGElement(Initializer, initializer) {} 230 231 CXXCtorInitializer* getInitializer() const { 232 return static_cast<CXXCtorInitializer*>(Data1.getPointer()); 233 } 234 235 private: 236 friend class CFGElement; 237 238 CFGInitializer() = default; 239 240 static bool isKind(const CFGElement &E) { 241 return E.getKind() == Initializer; 242 } 243 }; 244 245 /// Represents C++ allocator call. 246 class CFGNewAllocator : public CFGElement { 247 public: 248 explicit CFGNewAllocator(const CXXNewExpr *S) 249 : CFGElement(NewAllocator, S) {} 250 251 // Get the new expression. 252 const CXXNewExpr *getAllocatorExpr() const { 253 return static_cast<CXXNewExpr *>(Data1.getPointer()); 254 } 255 256 private: 257 friend class CFGElement; 258 259 CFGNewAllocator() = default; 260 261 static bool isKind(const CFGElement &elem) { 262 return elem.getKind() == NewAllocator; 263 } 264 }; 265 266 /// Represents the point where a loop ends. 267 /// This element is is only produced when building the CFG for the static 268 /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag. 269 /// 270 /// Note: a loop exit element can be reached even when the loop body was never 271 /// entered. 272 class CFGLoopExit : public CFGElement { 273 public: 274 explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {} 275 276 const Stmt *getLoopStmt() const { 277 return static_cast<Stmt *>(Data1.getPointer()); 278 } 279 280 private: 281 friend class CFGElement; 282 283 CFGLoopExit() = default; 284 285 static bool isKind(const CFGElement &elem) { 286 return elem.getKind() == LoopExit; 287 } 288 }; 289 290 /// Represents the point where the lifetime of an automatic object ends 291 class CFGLifetimeEnds : public CFGElement { 292 public: 293 explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt) 294 : CFGElement(LifetimeEnds, var, stmt) {} 295 296 const VarDecl *getVarDecl() const { 297 return static_cast<VarDecl *>(Data1.getPointer()); 298 } 299 300 const Stmt *getTriggerStmt() const { 301 return static_cast<Stmt *>(Data2.getPointer()); 302 } 303 304 private: 305 friend class CFGElement; 306 307 CFGLifetimeEnds() = default; 308 309 static bool isKind(const CFGElement &elem) { 310 return elem.getKind() == LifetimeEnds; 311 } 312 }; 313 314 /// Represents beginning of a scope implicitly generated 315 /// by the compiler on encountering a CompoundStmt 316 class CFGScopeBegin : public CFGElement { 317 public: 318 CFGScopeBegin() {} 319 CFGScopeBegin(const VarDecl *VD, const Stmt *S) 320 : CFGElement(ScopeBegin, VD, S) {} 321 322 // Get statement that triggered a new scope. 323 const Stmt *getTriggerStmt() const { 324 return static_cast<Stmt*>(Data2.getPointer()); 325 } 326 327 // Get VD that triggered a new scope. 328 const VarDecl *getVarDecl() const { 329 return static_cast<VarDecl *>(Data1.getPointer()); 330 } 331 332 private: 333 friend class CFGElement; 334 static bool isKind(const CFGElement &E) { 335 Kind kind = E.getKind(); 336 return kind == ScopeBegin; 337 } 338 }; 339 340 /// Represents end of a scope implicitly generated by 341 /// the compiler after the last Stmt in a CompoundStmt's body 342 class CFGScopeEnd : public CFGElement { 343 public: 344 CFGScopeEnd() {} 345 CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {} 346 347 const VarDecl *getVarDecl() const { 348 return static_cast<VarDecl *>(Data1.getPointer()); 349 } 350 351 const Stmt *getTriggerStmt() const { 352 return static_cast<Stmt *>(Data2.getPointer()); 353 } 354 355 private: 356 friend class CFGElement; 357 static bool isKind(const CFGElement &E) { 358 Kind kind = E.getKind(); 359 return kind == ScopeEnd; 360 } 361 }; 362 363 /// Represents C++ object destructor implicitly generated by compiler on various 364 /// occasions. 365 class CFGImplicitDtor : public CFGElement { 366 protected: 367 CFGImplicitDtor() = default; 368 369 CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr) 370 : CFGElement(kind, data1, data2) { 371 assert(kind >= DTOR_BEGIN && kind <= DTOR_END); 372 } 373 374 public: 375 const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const; 376 bool isNoReturn(ASTContext &astContext) const; 377 378 private: 379 friend class CFGElement; 380 381 static bool isKind(const CFGElement &E) { 382 Kind kind = E.getKind(); 383 return kind >= DTOR_BEGIN && kind <= DTOR_END; 384 } 385 }; 386 387 /// Represents C++ object destructor implicitly generated for automatic object 388 /// or temporary bound to const reference at the point of leaving its local 389 /// scope. 390 class CFGAutomaticObjDtor: public CFGImplicitDtor { 391 public: 392 CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt) 393 : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {} 394 395 const VarDecl *getVarDecl() const { 396 return static_cast<VarDecl*>(Data1.getPointer()); 397 } 398 399 // Get statement end of which triggered the destructor call. 400 const Stmt *getTriggerStmt() const { 401 return static_cast<Stmt*>(Data2.getPointer()); 402 } 403 404 private: 405 friend class CFGElement; 406 407 CFGAutomaticObjDtor() = default; 408 409 static bool isKind(const CFGElement &elem) { 410 return elem.getKind() == AutomaticObjectDtor; 411 } 412 }; 413 414 /// Represents C++ object destructor generated from a call to delete. 415 class CFGDeleteDtor : public CFGImplicitDtor { 416 public: 417 CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE) 418 : CFGImplicitDtor(DeleteDtor, RD, DE) {} 419 420 const CXXRecordDecl *getCXXRecordDecl() const { 421 return static_cast<CXXRecordDecl*>(Data1.getPointer()); 422 } 423 424 // Get Delete expression which triggered the destructor call. 425 const CXXDeleteExpr *getDeleteExpr() const { 426 return static_cast<CXXDeleteExpr *>(Data2.getPointer()); 427 } 428 429 private: 430 friend class CFGElement; 431 432 CFGDeleteDtor() = default; 433 434 static bool isKind(const CFGElement &elem) { 435 return elem.getKind() == DeleteDtor; 436 } 437 }; 438 439 /// Represents C++ object destructor implicitly generated for base object in 440 /// destructor. 441 class CFGBaseDtor : public CFGImplicitDtor { 442 public: 443 CFGBaseDtor(const CXXBaseSpecifier *base) 444 : CFGImplicitDtor(BaseDtor, base) {} 445 446 const CXXBaseSpecifier *getBaseSpecifier() const { 447 return static_cast<const CXXBaseSpecifier*>(Data1.getPointer()); 448 } 449 450 private: 451 friend class CFGElement; 452 453 CFGBaseDtor() = default; 454 455 static bool isKind(const CFGElement &E) { 456 return E.getKind() == BaseDtor; 457 } 458 }; 459 460 /// Represents C++ object destructor implicitly generated for member object in 461 /// destructor. 462 class CFGMemberDtor : public CFGImplicitDtor { 463 public: 464 CFGMemberDtor(const FieldDecl *field) 465 : CFGImplicitDtor(MemberDtor, field, nullptr) {} 466 467 const FieldDecl *getFieldDecl() const { 468 return static_cast<const FieldDecl*>(Data1.getPointer()); 469 } 470 471 private: 472 friend class CFGElement; 473 474 CFGMemberDtor() = default; 475 476 static bool isKind(const CFGElement &E) { 477 return E.getKind() == MemberDtor; 478 } 479 }; 480 481 /// Represents C++ object destructor implicitly generated at the end of full 482 /// expression for temporary object. 483 class CFGTemporaryDtor : public CFGImplicitDtor { 484 public: 485 CFGTemporaryDtor(CXXBindTemporaryExpr *expr) 486 : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {} 487 488 const CXXBindTemporaryExpr *getBindTemporaryExpr() const { 489 return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); 490 } 491 492 private: 493 friend class CFGElement; 494 495 CFGTemporaryDtor() = default; 496 497 static bool isKind(const CFGElement &E) { 498 return E.getKind() == TemporaryDtor; 499 } 500 }; 501 502 /// Represents CFGBlock terminator statement. 503 /// 504 class CFGTerminator { 505 public: 506 enum Kind { 507 /// A branch that corresponds to a statement in the code, 508 /// such as an if-statement. 509 StmtBranch, 510 /// A branch in control flow of destructors of temporaries. In this case 511 /// terminator statement is the same statement that branches control flow 512 /// in evaluation of matching full expression. 513 TemporaryDtorsBranch, 514 /// A shortcut around virtual base initializers. It gets taken when 515 /// virtual base classes have already been initialized by the constructor 516 /// of the most derived class while we're in the base class. 517 VirtualBaseBranch, 518 519 /// Number of different kinds, for assertions. We subtract 1 so that 520 /// to keep receiving compiler warnings when we don't cover all enum values 521 /// in a switch. 522 NumKindsMinusOne = VirtualBaseBranch 523 }; 524 525 private: 526 static constexpr int KindBits = 2; 527 static_assert((1 << KindBits) > NumKindsMinusOne, 528 "Not enough room for kind!"); 529 llvm::PointerIntPair<Stmt *, KindBits> Data; 530 531 public: 532 CFGTerminator() { assert(!isValid()); } 533 CFGTerminator(Stmt *S, Kind K = StmtBranch) : Data(S, K) {} 534 535 bool isValid() const { return Data.getOpaqueValue() != nullptr; } 536 Stmt *getStmt() { return Data.getPointer(); } 537 const Stmt *getStmt() const { return Data.getPointer(); } 538 Kind getKind() const { return static_cast<Kind>(Data.getInt()); } 539 540 bool isStmtBranch() const { 541 return getKind() == StmtBranch; 542 } 543 bool isTemporaryDtorsBranch() const { 544 return getKind() == TemporaryDtorsBranch; 545 } 546 bool isVirtualBaseBranch() const { 547 return getKind() == VirtualBaseBranch; 548 } 549 }; 550 551 /// Represents a single basic block in a source-level CFG. 552 /// It consists of: 553 /// 554 /// (1) A set of statements/expressions (which may contain subexpressions). 555 /// (2) A "terminator" statement (not in the set of statements). 556 /// (3) A list of successors and predecessors. 557 /// 558 /// Terminator: The terminator represents the type of control-flow that occurs 559 /// at the end of the basic block. The terminator is a Stmt* referring to an 560 /// AST node that has control-flow: if-statements, breaks, loops, etc. 561 /// If the control-flow is conditional, the condition expression will appear 562 /// within the set of statements in the block (usually the last statement). 563 /// 564 /// Predecessors: the order in the set of predecessors is arbitrary. 565 /// 566 /// Successors: the order in the set of successors is NOT arbitrary. We 567 /// currently have the following orderings based on the terminator: 568 /// 569 /// Terminator | Successor Ordering 570 /// ------------------|------------------------------------ 571 /// if | Then Block; Else Block 572 /// ? operator | LHS expression; RHS expression 573 /// logical and/or | expression that consumes the op, RHS 574 /// vbase inits | already handled by the most derived class; not yet 575 /// 576 /// But note that any of that may be NULL in case of optimized-out edges. 577 class CFGBlock { 578 class ElementList { 579 using ImplTy = BumpVector<CFGElement>; 580 581 ImplTy Impl; 582 583 public: 584 ElementList(BumpVectorContext &C) : Impl(C, 4) {} 585 586 using iterator = std::reverse_iterator<ImplTy::iterator>; 587 using const_iterator = std::reverse_iterator<ImplTy::const_iterator>; 588 using reverse_iterator = ImplTy::iterator; 589 using const_reverse_iterator = ImplTy::const_iterator; 590 using const_reference = ImplTy::const_reference; 591 592 void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); } 593 594 reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E, 595 BumpVectorContext &C) { 596 return Impl.insert(I, Cnt, E, C); 597 } 598 599 const_reference front() const { return Impl.back(); } 600 const_reference back() const { return Impl.front(); } 601 602 iterator begin() { return Impl.rbegin(); } 603 iterator end() { return Impl.rend(); } 604 const_iterator begin() const { return Impl.rbegin(); } 605 const_iterator end() const { return Impl.rend(); } 606 reverse_iterator rbegin() { return Impl.begin(); } 607 reverse_iterator rend() { return Impl.end(); } 608 const_reverse_iterator rbegin() const { return Impl.begin(); } 609 const_reverse_iterator rend() const { return Impl.end(); } 610 611 CFGElement operator[](size_t i) const { 612 assert(i < Impl.size()); 613 return Impl[Impl.size() - 1 - i]; 614 } 615 616 size_t size() const { return Impl.size(); } 617 bool empty() const { return Impl.empty(); } 618 }; 619 620 /// A convenience class for comparing CFGElements, since methods of CFGBlock 621 /// like operator[] return CFGElements by value. This is practically a wrapper 622 /// around a (CFGBlock, Index) pair. 623 template <bool IsConst> class ElementRefImpl { 624 625 template <bool IsOtherConst> friend class ElementRefImpl; 626 627 using CFGBlockPtr = 628 std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>; 629 630 using CFGElementPtr = 631 std::conditional_t<IsConst, const CFGElement *, CFGElement *>; 632 633 protected: 634 CFGBlockPtr Parent; 635 size_t Index; 636 637 public: 638 ElementRefImpl(CFGBlockPtr Parent, size_t Index) 639 : Parent(Parent), Index(Index) {} 640 641 template <bool IsOtherConst> 642 ElementRefImpl(ElementRefImpl<IsOtherConst> Other) 643 : ElementRefImpl(Other.Parent, Other.Index) {} 644 645 size_t getIndexInBlock() const { return Index; } 646 647 CFGBlockPtr getParent() { return Parent; } 648 CFGBlockPtr getParent() const { return Parent; } 649 650 bool operator<(ElementRefImpl Other) const { 651 return std::make_pair(Parent, Index) < 652 std::make_pair(Other.Parent, Other.Index); 653 } 654 655 bool operator==(ElementRefImpl Other) const { 656 return Parent == Other.Parent && Index == Other.Index; 657 } 658 659 bool operator!=(ElementRefImpl Other) const { return !(*this == Other); } 660 CFGElement operator*() const { return (*Parent)[Index]; } 661 CFGElementPtr operator->() const { return &*(Parent->begin() + Index); } 662 663 void dumpToStream(llvm::raw_ostream &OS) const { 664 OS << getIndexInBlock() + 1 << ": "; 665 (*this)->dumpToStream(OS); 666 } 667 668 void dump() const { 669 dumpToStream(llvm::errs()); 670 } 671 }; 672 673 template <bool IsReverse, bool IsConst> class ElementRefIterator { 674 675 template <bool IsOtherReverse, bool IsOtherConst> 676 friend class ElementRefIterator; 677 678 using CFGBlockRef = 679 std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>; 680 681 using UnderlayingIteratorTy = std::conditional_t< 682 IsConst, 683 std::conditional_t<IsReverse, ElementList::const_reverse_iterator, 684 ElementList::const_iterator>, 685 std::conditional_t<IsReverse, ElementList::reverse_iterator, 686 ElementList::iterator>>; 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, std::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 AddCXXDefaultInitExprInAggregates = false; 1252 bool AddRichCXXConstructors = false; 1253 bool MarkElidedCXXConstructors = false; 1254 bool AddVirtualBaseBranches = false; 1255 bool OmitImplicitValueInitializers = false; 1256 1257 BuildOptions() = default; 1258 1259 bool alwaysAdd(const Stmt *stmt) const { 1260 return alwaysAddMask[stmt->getStmtClass()]; 1261 } 1262 1263 BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { 1264 alwaysAddMask[stmtClass] = val; 1265 return *this; 1266 } 1267 1268 BuildOptions &setAllAlwaysAdd() { 1269 alwaysAddMask.set(); 1270 return *this; 1271 } 1272 }; 1273 1274 /// Builds a CFG from an AST. 1275 static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C, 1276 const BuildOptions &BO); 1277 1278 /// Create a new block in the CFG. The CFG owns the block; the caller should 1279 /// not directly free it. 1280 CFGBlock *createBlock(); 1281 1282 /// Set the entry block of the CFG. This is typically used only during CFG 1283 /// construction. Most CFG clients expect that the entry block has no 1284 /// predecessors and contains no statements. 1285 void setEntry(CFGBlock *B) { Entry = B; } 1286 1287 /// Set the block used for indirect goto jumps. This is typically used only 1288 /// during CFG construction. 1289 void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; } 1290 1291 //===--------------------------------------------------------------------===// 1292 // Block Iterators 1293 //===--------------------------------------------------------------------===// 1294 1295 using CFGBlockListTy = BumpVector<CFGBlock *>; 1296 using iterator = CFGBlockListTy::iterator; 1297 using const_iterator = CFGBlockListTy::const_iterator; 1298 using reverse_iterator = std::reverse_iterator<iterator>; 1299 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 1300 1301 CFGBlock & front() { return *Blocks.front(); } 1302 CFGBlock & back() { return *Blocks.back(); } 1303 1304 iterator begin() { return Blocks.begin(); } 1305 iterator end() { return Blocks.end(); } 1306 const_iterator begin() const { return Blocks.begin(); } 1307 const_iterator end() const { return Blocks.end(); } 1308 1309 iterator nodes_begin() { return iterator(Blocks.begin()); } 1310 iterator nodes_end() { return iterator(Blocks.end()); } 1311 1312 llvm::iterator_range<iterator> nodes() { return {begin(), end()}; } 1313 llvm::iterator_range<const_iterator> const_nodes() const { 1314 return {begin(), end()}; 1315 } 1316 1317 const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); } 1318 const_iterator nodes_end() const { return const_iterator(Blocks.end()); } 1319 1320 reverse_iterator rbegin() { return Blocks.rbegin(); } 1321 reverse_iterator rend() { return Blocks.rend(); } 1322 const_reverse_iterator rbegin() const { return Blocks.rbegin(); } 1323 const_reverse_iterator rend() const { return Blocks.rend(); } 1324 1325 llvm::iterator_range<reverse_iterator> reverse_nodes() { 1326 return {rbegin(), rend()}; 1327 } 1328 llvm::iterator_range<const_reverse_iterator> const_reverse_nodes() const { 1329 return {rbegin(), rend()}; 1330 } 1331 1332 CFGBlock & getEntry() { return *Entry; } 1333 const CFGBlock & getEntry() const { return *Entry; } 1334 CFGBlock & getExit() { return *Exit; } 1335 const CFGBlock & getExit() const { return *Exit; } 1336 1337 CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; } 1338 const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } 1339 1340 using try_block_iterator = std::vector<const CFGBlock *>::const_iterator; 1341 using try_block_range = llvm::iterator_range<try_block_iterator>; 1342 1343 try_block_iterator try_blocks_begin() const { 1344 return TryDispatchBlocks.begin(); 1345 } 1346 1347 try_block_iterator try_blocks_end() const { 1348 return TryDispatchBlocks.end(); 1349 } 1350 1351 try_block_range try_blocks() const { 1352 return try_block_range(try_blocks_begin(), try_blocks_end()); 1353 } 1354 1355 void addTryDispatchBlock(const CFGBlock *block) { 1356 TryDispatchBlocks.push_back(block); 1357 } 1358 1359 /// Records a synthetic DeclStmt and the DeclStmt it was constructed from. 1360 /// 1361 /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains 1362 /// multiple decls. 1363 void addSyntheticDeclStmt(const DeclStmt *Synthetic, 1364 const DeclStmt *Source) { 1365 assert(Synthetic->isSingleDecl() && "Can handle single declarations only"); 1366 assert(Synthetic != Source && "Don't include original DeclStmts in map"); 1367 assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map"); 1368 SyntheticDeclStmts[Synthetic] = Source; 1369 } 1370 1371 using synthetic_stmt_iterator = 1372 llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator; 1373 using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>; 1374 1375 /// Iterates over synthetic DeclStmts in the CFG. 1376 /// 1377 /// Each element is a (synthetic statement, source statement) pair. 1378 /// 1379 /// \sa addSyntheticDeclStmt 1380 synthetic_stmt_iterator synthetic_stmt_begin() const { 1381 return SyntheticDeclStmts.begin(); 1382 } 1383 1384 /// \sa synthetic_stmt_begin 1385 synthetic_stmt_iterator synthetic_stmt_end() const { 1386 return SyntheticDeclStmts.end(); 1387 } 1388 1389 /// \sa synthetic_stmt_begin 1390 synthetic_stmt_range synthetic_stmts() const { 1391 return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end()); 1392 } 1393 1394 //===--------------------------------------------------------------------===// 1395 // Member templates useful for various batch operations over CFGs. 1396 //===--------------------------------------------------------------------===// 1397 1398 template <typename Callback> void VisitBlockStmts(Callback &O) const { 1399 for (const_iterator I = begin(), E = end(); I != E; ++I) 1400 for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end(); 1401 BI != BE; ++BI) { 1402 if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) 1403 O(const_cast<Stmt *>(stmt->getStmt())); 1404 } 1405 } 1406 1407 //===--------------------------------------------------------------------===// 1408 // CFG Introspection. 1409 //===--------------------------------------------------------------------===// 1410 1411 /// Returns the total number of BlockIDs allocated (which start at 0). 1412 unsigned getNumBlockIDs() const { return NumBlockIDs; } 1413 1414 /// Return the total number of CFGBlocks within the CFG This is simply a 1415 /// renaming of the getNumBlockIDs(). This is necessary because the dominator 1416 /// implementation needs such an interface. 1417 unsigned size() const { return NumBlockIDs; } 1418 1419 /// Returns true if the CFG has no branches. Usually it boils down to the CFG 1420 /// having exactly three blocks (entry, the actual code, exit), but sometimes 1421 /// more blocks appear due to having control flow that can be fully 1422 /// resolved in compile time. 1423 bool isLinear() const; 1424 1425 //===--------------------------------------------------------------------===// 1426 // CFG Debugging: Pretty-Printing and Visualization. 1427 //===--------------------------------------------------------------------===// 1428 1429 void viewCFG(const LangOptions &LO) const; 1430 void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const; 1431 void dump(const LangOptions &LO, bool ShowColors) const; 1432 1433 //===--------------------------------------------------------------------===// 1434 // Internal: constructors and data. 1435 //===--------------------------------------------------------------------===// 1436 1437 CFG() : Blocks(BlkBVC, 10) {} 1438 1439 llvm::BumpPtrAllocator& getAllocator() { 1440 return BlkBVC.getAllocator(); 1441 } 1442 1443 BumpVectorContext &getBumpVectorContext() { 1444 return BlkBVC; 1445 } 1446 1447 private: 1448 CFGBlock *Entry = nullptr; 1449 CFGBlock *Exit = nullptr; 1450 1451 // Special block to contain collective dispatch for indirect gotos 1452 CFGBlock* IndirectGotoBlock = nullptr; 1453 1454 unsigned NumBlockIDs = 0; 1455 1456 BumpVectorContext BlkBVC; 1457 1458 CFGBlockListTy Blocks; 1459 1460 /// C++ 'try' statements are modeled with an indirect dispatch block. 1461 /// This is the collection of such blocks present in the CFG. 1462 std::vector<const CFGBlock *> TryDispatchBlocks; 1463 1464 /// Collects DeclStmts synthesized for this CFG and maps each one back to its 1465 /// source DeclStmt. 1466 llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; 1467 }; 1468 1469 } // namespace clang 1470 1471 //===----------------------------------------------------------------------===// 1472 // GraphTraits specializations for CFG basic block graphs (source-level CFGs) 1473 //===----------------------------------------------------------------------===// 1474 1475 namespace llvm { 1476 1477 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from 1478 /// CFGTerminator to a specific Stmt class. 1479 template <> struct simplify_type< ::clang::CFGTerminator> { 1480 using SimpleType = ::clang::Stmt *; 1481 1482 static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) { 1483 return Val.getStmt(); 1484 } 1485 }; 1486 1487 // Traits for: CFGBlock 1488 1489 template <> struct GraphTraits< ::clang::CFGBlock *> { 1490 using NodeRef = ::clang::CFGBlock *; 1491 using ChildIteratorType = ::clang::CFGBlock::succ_iterator; 1492 1493 static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; } 1494 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 1495 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 1496 }; 1497 1498 template <> struct GraphTraits< const ::clang::CFGBlock *> { 1499 using NodeRef = const ::clang::CFGBlock *; 1500 using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator; 1501 1502 static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; } 1503 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 1504 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 1505 }; 1506 1507 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> { 1508 using NodeRef = ::clang::CFGBlock *; 1509 using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; 1510 1511 static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) { 1512 return G.Graph; 1513 } 1514 1515 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } 1516 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } 1517 }; 1518 1519 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> { 1520 using NodeRef = const ::clang::CFGBlock *; 1521 using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; 1522 1523 static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) { 1524 return G.Graph; 1525 } 1526 1527 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } 1528 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } 1529 }; 1530 1531 // Traits for: CFG 1532 1533 template <> struct GraphTraits< ::clang::CFG* > 1534 : public GraphTraits< ::clang::CFGBlock *> { 1535 using nodes_iterator = ::clang::CFG::iterator; 1536 1537 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); } 1538 static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} 1539 static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } 1540 static unsigned size(::clang::CFG* F) { return F->size(); } 1541 }; 1542 1543 template <> struct GraphTraits<const ::clang::CFG* > 1544 : public GraphTraits<const ::clang::CFGBlock *> { 1545 using nodes_iterator = ::clang::CFG::const_iterator; 1546 1547 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); } 1548 1549 static nodes_iterator nodes_begin( const ::clang::CFG* F) { 1550 return F->nodes_begin(); 1551 } 1552 1553 static nodes_iterator nodes_end( const ::clang::CFG* F) { 1554 return F->nodes_end(); 1555 } 1556 1557 static unsigned size(const ::clang::CFG* F) { 1558 return F->size(); 1559 } 1560 }; 1561 1562 template <> struct GraphTraits<Inverse< ::clang::CFG *>> 1563 : public GraphTraits<Inverse< ::clang::CFGBlock *>> { 1564 using nodes_iterator = ::clang::CFG::iterator; 1565 1566 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); } 1567 static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} 1568 static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } 1569 }; 1570 1571 template <> struct GraphTraits<Inverse<const ::clang::CFG *>> 1572 : public GraphTraits<Inverse<const ::clang::CFGBlock *>> { 1573 using nodes_iterator = ::clang::CFG::const_iterator; 1574 1575 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); } 1576 1577 static nodes_iterator nodes_begin(const ::clang::CFG* F) { 1578 return F->nodes_begin(); 1579 } 1580 1581 static nodes_iterator nodes_end(const ::clang::CFG* F) { 1582 return F->nodes_end(); 1583 } 1584 }; 1585 1586 } // namespace llvm 1587 1588 #endif // LLVM_CLANG_ANALYSIS_CFG_H 1589