1//===--- CFG.h - Classes for representing and building CFGs------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the CFG and CFGBuilder classes for representing and 11// building Control-Flow Graphs (CFGs) from ASTs. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CLANG_ANALYSIS_CFG_H 16#define LLVM_CLANG_ANALYSIS_CFG_H 17 18#include "clang/AST/Stmt.h" 19#include "clang/Analysis/Support/BumpVector.h" 20#include "clang/Basic/SourceLocation.h" 21#include "llvm/ADT/DenseMap.h" 22#include "llvm/ADT/GraphTraits.h" 23#include "llvm/ADT/Optional.h" 24#include "llvm/ADT/PointerIntPair.h" 25#include "llvm/ADT/iterator_range.h" 26#include "llvm/Support/Allocator.h" 27#include "llvm/Support/Casting.h" 28#include "llvm/Support/raw_ostream.h" 29#include <bitset> 30#include <cassert> 31#include <iterator> 32#include <memory> 33 34namespace clang { 35 class CXXDestructorDecl; 36 class Decl; 37 class Stmt; 38 class Expr; 39 class FieldDecl; 40 class VarDecl; 41 class CXXCtorInitializer; 42 class CXXBaseSpecifier; 43 class CXXBindTemporaryExpr; 44 class CFG; 45 class PrinterHelper; 46 class LangOptions; 47 class ASTContext; 48 class CXXRecordDecl; 49 class CXXDeleteExpr; 50 class CXXNewExpr; 51 class BinaryOperator; 52 53/// CFGElement - Represents a top-level expression in a basic block. 54class CFGElement { 55public: 56 enum Kind { 57 // main kind 58 Statement, 59 Initializer, 60 NewAllocator, 61 // dtor kind 62 AutomaticObjectDtor, 63 DeleteDtor, 64 BaseDtor, 65 MemberDtor, 66 TemporaryDtor, 67 DTOR_BEGIN = AutomaticObjectDtor, 68 DTOR_END = TemporaryDtor 69 }; 70 71protected: 72 // The int bits are used to mark the kind. 73 llvm::PointerIntPair<void *, 2> Data1; 74 llvm::PointerIntPair<void *, 2> Data2; 75 76 CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr) 77 : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3), 78 Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) { 79 assert(getKind() == kind); 80 } 81 82 CFGElement() {} 83public: 84 85 /// \brief Convert to the specified CFGElement type, asserting that this 86 /// CFGElement is of the desired type. 87 template<typename T> 88 T castAs() const { 89 assert(T::isKind(*this)); 90 T t; 91 CFGElement& e = t; 92 e = *this; 93 return t; 94 } 95 96 /// \brief Convert to the specified CFGElement type, returning None if this 97 /// CFGElement is not of the desired type. 98 template<typename T> 99 Optional<T> getAs() const { 100 if (!T::isKind(*this)) 101 return None; 102 T t; 103 CFGElement& e = t; 104 e = *this; 105 return t; 106 } 107 108 Kind getKind() const { 109 unsigned x = Data2.getInt(); 110 x <<= 2; 111 x |= Data1.getInt(); 112 return (Kind) x; 113 } 114}; 115 116class CFGStmt : public CFGElement { 117public: 118 CFGStmt(Stmt *S) : CFGElement(Statement, S) {} 119 120 const Stmt *getStmt() const { 121 return static_cast<const Stmt *>(Data1.getPointer()); 122 } 123 124private: 125 friend class CFGElement; 126 CFGStmt() {} 127 static bool isKind(const CFGElement &E) { 128 return E.getKind() == Statement; 129 } 130}; 131 132/// CFGInitializer - Represents C++ base or member initializer from 133/// constructor's initialization list. 134class CFGInitializer : public CFGElement { 135public: 136 CFGInitializer(CXXCtorInitializer *initializer) 137 : CFGElement(Initializer, initializer) {} 138 139 CXXCtorInitializer* getInitializer() const { 140 return static_cast<CXXCtorInitializer*>(Data1.getPointer()); 141 } 142 143private: 144 friend class CFGElement; 145 CFGInitializer() {} 146 static bool isKind(const CFGElement &E) { 147 return E.getKind() == Initializer; 148 } 149}; 150 151/// CFGNewAllocator - Represents C++ allocator call. 152class CFGNewAllocator : public CFGElement { 153public: 154 explicit CFGNewAllocator(const CXXNewExpr *S) 155 : CFGElement(NewAllocator, S) {} 156 157 // Get the new expression. 158 const CXXNewExpr *getAllocatorExpr() const { 159 return static_cast<CXXNewExpr *>(Data1.getPointer()); 160 } 161 162private: 163 friend class CFGElement; 164 CFGNewAllocator() {} 165 static bool isKind(const CFGElement &elem) { 166 return elem.getKind() == NewAllocator; 167 } 168}; 169 170/// CFGImplicitDtor - Represents C++ object destructor implicitly generated 171/// by compiler on various occasions. 172class CFGImplicitDtor : public CFGElement { 173protected: 174 CFGImplicitDtor() {} 175 CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr) 176 : CFGElement(kind, data1, data2) { 177 assert(kind >= DTOR_BEGIN && kind <= DTOR_END); 178 } 179 180public: 181 const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const; 182 bool isNoReturn(ASTContext &astContext) const; 183 184private: 185 friend class CFGElement; 186 static bool isKind(const CFGElement &E) { 187 Kind kind = E.getKind(); 188 return kind >= DTOR_BEGIN && kind <= DTOR_END; 189 } 190}; 191 192/// CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated 193/// for automatic object or temporary bound to const reference at the point 194/// of leaving its local scope. 195class CFGAutomaticObjDtor: public CFGImplicitDtor { 196public: 197 CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt) 198 : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {} 199 200 const VarDecl *getVarDecl() const { 201 return static_cast<VarDecl*>(Data1.getPointer()); 202 } 203 204 // Get statement end of which triggered the destructor call. 205 const Stmt *getTriggerStmt() const { 206 return static_cast<Stmt*>(Data2.getPointer()); 207 } 208 209private: 210 friend class CFGElement; 211 CFGAutomaticObjDtor() {} 212 static bool isKind(const CFGElement &elem) { 213 return elem.getKind() == AutomaticObjectDtor; 214 } 215}; 216 217/// CFGDeleteDtor - Represents C++ object destructor generated 218/// from a call to delete. 219class CFGDeleteDtor : public CFGImplicitDtor { 220public: 221 CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE) 222 : CFGImplicitDtor(DeleteDtor, RD, DE) {} 223 224 const CXXRecordDecl *getCXXRecordDecl() const { 225 return static_cast<CXXRecordDecl*>(Data1.getPointer()); 226 } 227 228 // Get Delete expression which triggered the destructor call. 229 const CXXDeleteExpr *getDeleteExpr() const { 230 return static_cast<CXXDeleteExpr *>(Data2.getPointer()); 231 } 232 233private: 234 friend class CFGElement; 235 CFGDeleteDtor() {} 236 static bool isKind(const CFGElement &elem) { 237 return elem.getKind() == DeleteDtor; 238 } 239}; 240 241/// CFGBaseDtor - Represents C++ object destructor implicitly generated for 242/// base object in destructor. 243class CFGBaseDtor : public CFGImplicitDtor { 244public: 245 CFGBaseDtor(const CXXBaseSpecifier *base) 246 : CFGImplicitDtor(BaseDtor, base) {} 247 248 const CXXBaseSpecifier *getBaseSpecifier() const { 249 return static_cast<const CXXBaseSpecifier*>(Data1.getPointer()); 250 } 251 252private: 253 friend class CFGElement; 254 CFGBaseDtor() {} 255 static bool isKind(const CFGElement &E) { 256 return E.getKind() == BaseDtor; 257 } 258}; 259 260/// CFGMemberDtor - Represents C++ object destructor implicitly generated for 261/// member object in destructor. 262class CFGMemberDtor : public CFGImplicitDtor { 263public: 264 CFGMemberDtor(const FieldDecl *field) 265 : CFGImplicitDtor(MemberDtor, field, nullptr) {} 266 267 const FieldDecl *getFieldDecl() const { 268 return static_cast<const FieldDecl*>(Data1.getPointer()); 269 } 270 271private: 272 friend class CFGElement; 273 CFGMemberDtor() {} 274 static bool isKind(const CFGElement &E) { 275 return E.getKind() == MemberDtor; 276 } 277}; 278 279/// CFGTemporaryDtor - Represents C++ object destructor implicitly generated 280/// at the end of full expression for temporary object. 281class CFGTemporaryDtor : public CFGImplicitDtor { 282public: 283 CFGTemporaryDtor(CXXBindTemporaryExpr *expr) 284 : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {} 285 286 const CXXBindTemporaryExpr *getBindTemporaryExpr() const { 287 return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); 288 } 289 290private: 291 friend class CFGElement; 292 CFGTemporaryDtor() {} 293 static bool isKind(const CFGElement &E) { 294 return E.getKind() == TemporaryDtor; 295 } 296}; 297 298/// CFGTerminator - Represents CFGBlock terminator statement. 299/// 300/// TemporaryDtorsBranch bit is set to true if the terminator marks a branch 301/// in control flow of destructors of temporaries. In this case terminator 302/// statement is the same statement that branches control flow in evaluation 303/// of matching full expression. 304class CFGTerminator { 305 llvm::PointerIntPair<Stmt *, 1> Data; 306public: 307 CFGTerminator() {} 308 CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false) 309 : Data(S, TemporaryDtorsBranch) {} 310 311 Stmt *getStmt() { return Data.getPointer(); } 312 const Stmt *getStmt() const { return Data.getPointer(); } 313 314 bool isTemporaryDtorsBranch() const { return Data.getInt(); } 315 316 operator Stmt *() { return getStmt(); } 317 operator const Stmt *() const { return getStmt(); } 318 319 Stmt *operator->() { return getStmt(); } 320 const Stmt *operator->() const { return getStmt(); } 321 322 Stmt &operator*() { return *getStmt(); } 323 const Stmt &operator*() const { return *getStmt(); } 324 325 explicit operator bool() const { return getStmt(); } 326}; 327 328/// CFGBlock - Represents a single basic block in a source-level CFG. 329/// It consists of: 330/// 331/// (1) A set of statements/expressions (which may contain subexpressions). 332/// (2) A "terminator" statement (not in the set of statements). 333/// (3) A list of successors and predecessors. 334/// 335/// Terminator: The terminator represents the type of control-flow that occurs 336/// at the end of the basic block. The terminator is a Stmt* referring to an 337/// AST node that has control-flow: if-statements, breaks, loops, etc. 338/// If the control-flow is conditional, the condition expression will appear 339/// within the set of statements in the block (usually the last statement). 340/// 341/// Predecessors: the order in the set of predecessors is arbitrary. 342/// 343/// Successors: the order in the set of successors is NOT arbitrary. We 344/// currently have the following orderings based on the terminator: 345/// 346/// Terminator Successor Ordering 347/// ----------------------------------------------------- 348/// if Then Block; Else Block 349/// ? operator LHS expression; RHS expression 350/// &&, || expression that uses result of && or ||, RHS 351/// 352/// But note that any of that may be NULL in case of optimized-out edges. 353/// 354class CFGBlock { 355 class ElementList { 356 typedef BumpVector<CFGElement> ImplTy; 357 ImplTy Impl; 358 public: 359 ElementList(BumpVectorContext &C) : Impl(C, 4) {} 360 361 typedef std::reverse_iterator<ImplTy::iterator> iterator; 362 typedef std::reverse_iterator<ImplTy::const_iterator> const_iterator; 363 typedef ImplTy::iterator reverse_iterator; 364 typedef ImplTy::const_iterator const_reverse_iterator; 365 typedef ImplTy::const_reference const_reference; 366 367 void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); } 368 reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E, 369 BumpVectorContext &C) { 370 return Impl.insert(I, Cnt, E, C); 371 } 372 373 const_reference front() const { return Impl.back(); } 374 const_reference back() const { return Impl.front(); } 375 376 iterator begin() { return Impl.rbegin(); } 377 iterator end() { return Impl.rend(); } 378 const_iterator begin() const { return Impl.rbegin(); } 379 const_iterator end() const { return Impl.rend(); } 380 reverse_iterator rbegin() { return Impl.begin(); } 381 reverse_iterator rend() { return Impl.end(); } 382 const_reverse_iterator rbegin() const { return Impl.begin(); } 383 const_reverse_iterator rend() const { return Impl.end(); } 384 385 CFGElement operator[](size_t i) const { 386 assert(i < Impl.size()); 387 return Impl[Impl.size() - 1 - i]; 388 } 389 390 size_t size() const { return Impl.size(); } 391 bool empty() const { return Impl.empty(); } 392 }; 393 394 /// Stmts - The set of statements in the basic block. 395 ElementList Elements; 396 397 /// Label - An (optional) label that prefixes the executable 398 /// statements in the block. When this variable is non-NULL, it is 399 /// either an instance of LabelStmt, SwitchCase or CXXCatchStmt. 400 Stmt *Label; 401 402 /// Terminator - The terminator for a basic block that 403 /// indicates the type of control-flow that occurs between a block 404 /// and its successors. 405 CFGTerminator Terminator; 406 407 /// LoopTarget - Some blocks are used to represent the "loop edge" to 408 /// the start of a loop from within the loop body. This Stmt* will be 409 /// refer to the loop statement for such blocks (and be null otherwise). 410 const Stmt *LoopTarget; 411 412 /// BlockID - A numerical ID assigned to a CFGBlock during construction 413 /// of the CFG. 414 unsigned BlockID; 415 416public: 417 /// This class represents a potential adjacent block in the CFG. It encodes 418 /// whether or not the block is actually reachable, or can be proved to be 419 /// trivially unreachable. For some cases it allows one to encode scenarios 420 /// where a block was substituted because the original (now alternate) block 421 /// is unreachable. 422 class AdjacentBlock { 423 enum Kind { 424 AB_Normal, 425 AB_Unreachable, 426 AB_Alternate 427 }; 428 429 CFGBlock *ReachableBlock; 430 llvm::PointerIntPair<CFGBlock*, 2> UnreachableBlock; 431 432 public: 433 /// Construct an AdjacentBlock with a possibly unreachable block. 434 AdjacentBlock(CFGBlock *B, bool IsReachable); 435 436 /// Construct an AdjacentBlock with a reachable block and an alternate 437 /// unreachable block. 438 AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock); 439 440 /// Get the reachable block, if one exists. 441 CFGBlock *getReachableBlock() const { 442 return ReachableBlock; 443 } 444 445 /// Get the potentially unreachable block. 446 CFGBlock *getPossiblyUnreachableBlock() const { 447 return UnreachableBlock.getPointer(); 448 } 449 450 /// Provide an implicit conversion to CFGBlock* so that 451 /// AdjacentBlock can be substituted for CFGBlock*. 452 operator CFGBlock*() const { 453 return getReachableBlock(); 454 } 455 456 CFGBlock& operator *() const { 457 return *getReachableBlock(); 458 } 459 460 CFGBlock* operator ->() const { 461 return getReachableBlock(); 462 } 463 464 bool isReachable() const { 465 Kind K = (Kind) UnreachableBlock.getInt(); 466 return K == AB_Normal || K == AB_Alternate; 467 } 468 }; 469 470private: 471 /// Predecessors/Successors - Keep track of the predecessor / successor 472 /// CFG blocks. 473 typedef BumpVector<AdjacentBlock> AdjacentBlocks; 474 AdjacentBlocks Preds; 475 AdjacentBlocks Succs; 476 477 /// NoReturn - This bit is set when the basic block contains a function call 478 /// or implicit destructor that is attributed as 'noreturn'. In that case, 479 /// control cannot technically ever proceed past this block. All such blocks 480 /// will have a single immediate successor: the exit block. This allows them 481 /// to be easily reached from the exit block and using this bit quickly 482 /// recognized without scanning the contents of the block. 483 /// 484 /// Optimization Note: This bit could be profitably folded with Terminator's 485 /// storage if the memory usage of CFGBlock becomes an issue. 486 unsigned HasNoReturnElement : 1; 487 488 /// Parent - The parent CFG that owns this CFGBlock. 489 CFG *Parent; 490 491public: 492 explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent) 493 : Elements(C), Label(nullptr), Terminator(nullptr), LoopTarget(nullptr), 494 BlockID(blockid), Preds(C, 1), Succs(C, 1), HasNoReturnElement(false), 495 Parent(parent) {} 496 497 // Statement iterators 498 typedef ElementList::iterator iterator; 499 typedef ElementList::const_iterator const_iterator; 500 typedef ElementList::reverse_iterator reverse_iterator; 501 typedef ElementList::const_reverse_iterator const_reverse_iterator; 502 503 CFGElement front() const { return Elements.front(); } 504 CFGElement back() const { return Elements.back(); } 505 506 iterator begin() { return Elements.begin(); } 507 iterator end() { return Elements.end(); } 508 const_iterator begin() const { return Elements.begin(); } 509 const_iterator end() const { return Elements.end(); } 510 511 reverse_iterator rbegin() { return Elements.rbegin(); } 512 reverse_iterator rend() { return Elements.rend(); } 513 const_reverse_iterator rbegin() const { return Elements.rbegin(); } 514 const_reverse_iterator rend() const { return Elements.rend(); } 515 516 unsigned size() const { return Elements.size(); } 517 bool empty() const { return Elements.empty(); } 518 519 CFGElement operator[](size_t i) const { return Elements[i]; } 520 521 // CFG iterators 522 typedef AdjacentBlocks::iterator pred_iterator; 523 typedef AdjacentBlocks::const_iterator const_pred_iterator; 524 typedef AdjacentBlocks::reverse_iterator pred_reverse_iterator; 525 typedef AdjacentBlocks::const_reverse_iterator const_pred_reverse_iterator; 526 typedef llvm::iterator_range<pred_iterator> pred_range; 527 typedef llvm::iterator_range<const_pred_iterator> pred_const_range; 528 529 typedef AdjacentBlocks::iterator succ_iterator; 530 typedef AdjacentBlocks::const_iterator const_succ_iterator; 531 typedef AdjacentBlocks::reverse_iterator succ_reverse_iterator; 532 typedef AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator; 533 typedef llvm::iterator_range<succ_iterator> succ_range; 534 typedef llvm::iterator_range<const_succ_iterator> succ_const_range; 535 536 pred_iterator pred_begin() { return Preds.begin(); } 537 pred_iterator pred_end() { return Preds.end(); } 538 const_pred_iterator pred_begin() const { return Preds.begin(); } 539 const_pred_iterator pred_end() const { return Preds.end(); } 540 541 pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); } 542 pred_reverse_iterator pred_rend() { return Preds.rend(); } 543 const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); } 544 const_pred_reverse_iterator pred_rend() const { return Preds.rend(); } 545 546 pred_range preds() { 547 return pred_range(pred_begin(), pred_end()); 548 } 549 pred_const_range preds() const { 550 return pred_const_range(pred_begin(), pred_end()); 551 } 552 553 succ_iterator succ_begin() { return Succs.begin(); } 554 succ_iterator succ_end() { return Succs.end(); } 555 const_succ_iterator succ_begin() const { return Succs.begin(); } 556 const_succ_iterator succ_end() const { return Succs.end(); } 557 558 succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); } 559 succ_reverse_iterator succ_rend() { return Succs.rend(); } 560 const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); } 561 const_succ_reverse_iterator succ_rend() const { return Succs.rend(); } 562 563 succ_range succs() { 564 return succ_range(succ_begin(), succ_end()); 565 } 566 succ_const_range succs() const { 567 return succ_const_range(succ_begin(), succ_end()); 568 } 569 570 unsigned succ_size() const { return Succs.size(); } 571 bool succ_empty() const { return Succs.empty(); } 572 573 unsigned pred_size() const { return Preds.size(); } 574 bool pred_empty() const { return Preds.empty(); } 575 576 577 class FilterOptions { 578 public: 579 FilterOptions() { 580 IgnoreNullPredecessors = 1; 581 IgnoreDefaultsWithCoveredEnums = 0; 582 } 583 584 unsigned IgnoreNullPredecessors : 1; 585 unsigned IgnoreDefaultsWithCoveredEnums : 1; 586 }; 587 588 static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src, 589 const CFGBlock *Dst); 590 591 template <typename IMPL, bool IsPred> 592 class FilteredCFGBlockIterator { 593 private: 594 IMPL I, E; 595 const FilterOptions F; 596 const CFGBlock *From; 597 public: 598 explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e, 599 const CFGBlock *from, 600 const FilterOptions &f) 601 : I(i), E(e), F(f), From(from) { 602 while (hasMore() && Filter(*I)) 603 ++I; 604 } 605 606 bool hasMore() const { return I != E; } 607 608 FilteredCFGBlockIterator &operator++() { 609 do { ++I; } while (hasMore() && Filter(*I)); 610 return *this; 611 } 612 613 const CFGBlock *operator*() const { return *I; } 614 private: 615 bool Filter(const CFGBlock *To) { 616 return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To); 617 } 618 }; 619 620 typedef FilteredCFGBlockIterator<const_pred_iterator, true> 621 filtered_pred_iterator; 622 623 typedef FilteredCFGBlockIterator<const_succ_iterator, false> 624 filtered_succ_iterator; 625 626 filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const { 627 return filtered_pred_iterator(pred_begin(), pred_end(), this, f); 628 } 629 630 filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const { 631 return filtered_succ_iterator(succ_begin(), succ_end(), this, f); 632 } 633 634 // Manipulation of block contents 635 636 void setTerminator(CFGTerminator Term) { Terminator = Term; } 637 void setLabel(Stmt *Statement) { Label = Statement; } 638 void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; } 639 void setHasNoReturnElement() { HasNoReturnElement = true; } 640 641 CFGTerminator getTerminator() { return Terminator; } 642 const CFGTerminator getTerminator() const { return Terminator; } 643 644 Stmt *getTerminatorCondition(bool StripParens = true); 645 646 const Stmt *getTerminatorCondition(bool StripParens = true) const { 647 return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens); 648 } 649 650 const Stmt *getLoopTarget() const { return LoopTarget; } 651 652 Stmt *getLabel() { return Label; } 653 const Stmt *getLabel() const { return Label; } 654 655 bool hasNoReturnElement() const { return HasNoReturnElement; } 656 657 unsigned getBlockID() const { return BlockID; } 658 659 CFG *getParent() const { return Parent; } 660 661 void dump() const; 662 663 void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const; 664 void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO, 665 bool ShowColors) const; 666 void printTerminator(raw_ostream &OS, const LangOptions &LO) const; 667 void printAsOperand(raw_ostream &OS, bool /*PrintType*/) { 668 OS << "BB#" << getBlockID(); 669 } 670 671 /// Adds a (potentially unreachable) successor block to the current block. 672 void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C); 673 674 void appendStmt(Stmt *statement, BumpVectorContext &C) { 675 Elements.push_back(CFGStmt(statement), C); 676 } 677 678 void appendInitializer(CXXCtorInitializer *initializer, 679 BumpVectorContext &C) { 680 Elements.push_back(CFGInitializer(initializer), C); 681 } 682 683 void appendNewAllocator(CXXNewExpr *NE, 684 BumpVectorContext &C) { 685 Elements.push_back(CFGNewAllocator(NE), C); 686 } 687 688 void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { 689 Elements.push_back(CFGBaseDtor(BS), C); 690 } 691 692 void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) { 693 Elements.push_back(CFGMemberDtor(FD), C); 694 } 695 696 void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) { 697 Elements.push_back(CFGTemporaryDtor(E), C); 698 } 699 700 void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) { 701 Elements.push_back(CFGAutomaticObjDtor(VD, S), C); 702 } 703 704 void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { 705 Elements.push_back(CFGDeleteDtor(RD, DE), C); 706 } 707 708 // Destructors must be inserted in reversed order. So insertion is in two 709 // steps. First we prepare space for some number of elements, then we insert 710 // the elements beginning at the last position in prepared space. 711 iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt, 712 BumpVectorContext &C) { 713 return iterator(Elements.insert(I.base(), Cnt, 714 CFGAutomaticObjDtor(nullptr, nullptr), C)); 715 } 716 iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) { 717 *I = CFGAutomaticObjDtor(VD, S); 718 return ++I; 719 } 720}; 721 722/// \brief CFGCallback defines methods that should be called when a logical 723/// operator error is found when building the CFG. 724class CFGCallback { 725public: 726 CFGCallback() {} 727 virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} 728 virtual void compareBitwiseEquality(const BinaryOperator *B, 729 bool isAlwaysTrue) {} 730 virtual ~CFGCallback() {} 731}; 732 733/// CFG - Represents a source-level, intra-procedural CFG that represents the 734/// control-flow of a Stmt. The Stmt can represent an entire function body, 735/// or a single expression. A CFG will always contain one empty block that 736/// represents the Exit point of the CFG. A CFG will also contain a designated 737/// Entry block. The CFG solely represents control-flow; it consists of 738/// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG 739/// was constructed from. 740class CFG { 741public: 742 //===--------------------------------------------------------------------===// 743 // CFG Construction & Manipulation. 744 //===--------------------------------------------------------------------===// 745 746 class BuildOptions { 747 std::bitset<Stmt::lastStmtConstant> alwaysAddMask; 748 public: 749 typedef llvm::DenseMap<const Stmt *, const CFGBlock*> ForcedBlkExprs; 750 ForcedBlkExprs **forcedBlkExprs; 751 CFGCallback *Observer; 752 bool PruneTriviallyFalseEdges; 753 bool AddEHEdges; 754 bool AddInitializers; 755 bool AddImplicitDtors; 756 bool AddTemporaryDtors; 757 bool AddStaticInitBranches; 758 bool AddCXXNewAllocator; 759 bool AddCXXDefaultInitExprInCtors; 760 761 bool alwaysAdd(const Stmt *stmt) const { 762 return alwaysAddMask[stmt->getStmtClass()]; 763 } 764 765 BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { 766 alwaysAddMask[stmtClass] = val; 767 return *this; 768 } 769 770 BuildOptions &setAllAlwaysAdd() { 771 alwaysAddMask.set(); 772 return *this; 773 } 774 775 BuildOptions() 776 : forcedBlkExprs(nullptr), Observer(nullptr), 777 PruneTriviallyFalseEdges(true), AddEHEdges(false), 778 AddInitializers(false), AddImplicitDtors(false), 779 AddTemporaryDtors(false), AddStaticInitBranches(false), 780 AddCXXNewAllocator(false), AddCXXDefaultInitExprInCtors(false) {} 781 }; 782 783 /// buildCFG - Builds a CFG from an AST. 784 static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C, 785 const BuildOptions &BO); 786 787 /// createBlock - Create a new block in the CFG. The CFG owns the block; 788 /// the caller should not directly free it. 789 CFGBlock *createBlock(); 790 791 /// setEntry - Set the entry block of the CFG. This is typically used 792 /// only during CFG construction. Most CFG clients expect that the 793 /// entry block has no predecessors and contains no statements. 794 void setEntry(CFGBlock *B) { Entry = B; } 795 796 /// setIndirectGotoBlock - Set the block used for indirect goto jumps. 797 /// This is typically used only during CFG construction. 798 void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; } 799 800 //===--------------------------------------------------------------------===// 801 // Block Iterators 802 //===--------------------------------------------------------------------===// 803 804 typedef BumpVector<CFGBlock*> CFGBlockListTy; 805 typedef CFGBlockListTy::iterator iterator; 806 typedef CFGBlockListTy::const_iterator const_iterator; 807 typedef std::reverse_iterator<iterator> reverse_iterator; 808 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 809 810 CFGBlock & front() { return *Blocks.front(); } 811 CFGBlock & back() { return *Blocks.back(); } 812 813 iterator begin() { return Blocks.begin(); } 814 iterator end() { return Blocks.end(); } 815 const_iterator begin() const { return Blocks.begin(); } 816 const_iterator end() const { return Blocks.end(); } 817 818 iterator nodes_begin() { return iterator(Blocks.begin()); } 819 iterator nodes_end() { return iterator(Blocks.end()); } 820 const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); } 821 const_iterator nodes_end() const { return const_iterator(Blocks.end()); } 822 823 reverse_iterator rbegin() { return Blocks.rbegin(); } 824 reverse_iterator rend() { return Blocks.rend(); } 825 const_reverse_iterator rbegin() const { return Blocks.rbegin(); } 826 const_reverse_iterator rend() const { return Blocks.rend(); } 827 828 CFGBlock & getEntry() { return *Entry; } 829 const CFGBlock & getEntry() const { return *Entry; } 830 CFGBlock & getExit() { return *Exit; } 831 const CFGBlock & getExit() const { return *Exit; } 832 833 CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; } 834 const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } 835 836 typedef std::vector<const CFGBlock*>::const_iterator try_block_iterator; 837 try_block_iterator try_blocks_begin() const { 838 return TryDispatchBlocks.begin(); 839 } 840 try_block_iterator try_blocks_end() const { 841 return TryDispatchBlocks.end(); 842 } 843 844 void addTryDispatchBlock(const CFGBlock *block) { 845 TryDispatchBlocks.push_back(block); 846 } 847 848 /// Records a synthetic DeclStmt and the DeclStmt it was constructed from. 849 /// 850 /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains 851 /// multiple decls. 852 void addSyntheticDeclStmt(const DeclStmt *Synthetic, 853 const DeclStmt *Source) { 854 assert(Synthetic->isSingleDecl() && "Can handle single declarations only"); 855 assert(Synthetic != Source && "Don't include original DeclStmts in map"); 856 assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map"); 857 SyntheticDeclStmts[Synthetic] = Source; 858 } 859 860 typedef llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator 861 synthetic_stmt_iterator; 862 typedef llvm::iterator_range<synthetic_stmt_iterator> synthetic_stmt_range; 863 864 /// Iterates over synthetic DeclStmts in the CFG. 865 /// 866 /// Each element is a (synthetic statement, source statement) pair. 867 /// 868 /// \sa addSyntheticDeclStmt 869 synthetic_stmt_iterator synthetic_stmt_begin() const { 870 return SyntheticDeclStmts.begin(); 871 } 872 873 /// \sa synthetic_stmt_begin 874 synthetic_stmt_iterator synthetic_stmt_end() const { 875 return SyntheticDeclStmts.end(); 876 } 877 878 /// \sa synthetic_stmt_begin 879 synthetic_stmt_range synthetic_stmts() const { 880 return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end()); 881 } 882 883 //===--------------------------------------------------------------------===// 884 // Member templates useful for various batch operations over CFGs. 885 //===--------------------------------------------------------------------===// 886 887 template <typename CALLBACK> 888 void VisitBlockStmts(CALLBACK& O) const { 889 for (const_iterator I=begin(), E=end(); I != E; ++I) 890 for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end(); 891 BI != BE; ++BI) { 892 if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) 893 O(const_cast<Stmt*>(stmt->getStmt())); 894 } 895 } 896 897 //===--------------------------------------------------------------------===// 898 // CFG Introspection. 899 //===--------------------------------------------------------------------===// 900 901 /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which 902 /// start at 0). 903 unsigned getNumBlockIDs() const { return NumBlockIDs; } 904 905 /// size - Return the total number of CFGBlocks within the CFG 906 /// This is simply a renaming of the getNumBlockIDs(). This is necessary 907 /// because the dominator implementation needs such an interface. 908 unsigned size() const { return NumBlockIDs; } 909 910 //===--------------------------------------------------------------------===// 911 // CFG Debugging: Pretty-Printing and Visualization. 912 //===--------------------------------------------------------------------===// 913 914 void viewCFG(const LangOptions &LO) const; 915 void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const; 916 void dump(const LangOptions &LO, bool ShowColors) const; 917 918 //===--------------------------------------------------------------------===// 919 // Internal: constructors and data. 920 //===--------------------------------------------------------------------===// 921 922 CFG() 923 : Entry(nullptr), Exit(nullptr), IndirectGotoBlock(nullptr), NumBlockIDs(0), 924 Blocks(BlkBVC, 10) {} 925 926 llvm::BumpPtrAllocator& getAllocator() { 927 return BlkBVC.getAllocator(); 928 } 929 930 BumpVectorContext &getBumpVectorContext() { 931 return BlkBVC; 932 } 933 934private: 935 CFGBlock *Entry; 936 CFGBlock *Exit; 937 CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch 938 // for indirect gotos 939 unsigned NumBlockIDs; 940 941 BumpVectorContext BlkBVC; 942 943 CFGBlockListTy Blocks; 944 945 /// C++ 'try' statements are modeled with an indirect dispatch block. 946 /// This is the collection of such blocks present in the CFG. 947 std::vector<const CFGBlock *> TryDispatchBlocks; 948 949 /// Collects DeclStmts synthesized for this CFG and maps each one back to its 950 /// source DeclStmt. 951 llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; 952}; 953} // end namespace clang 954 955//===----------------------------------------------------------------------===// 956// GraphTraits specializations for CFG basic block graphs (source-level CFGs) 957//===----------------------------------------------------------------------===// 958 959namespace llvm { 960 961/// Implement simplify_type for CFGTerminator, so that we can dyn_cast from 962/// CFGTerminator to a specific Stmt class. 963template <> struct simplify_type< ::clang::CFGTerminator> { 964 typedef ::clang::Stmt *SimpleType; 965 static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) { 966 return Val.getStmt(); 967 } 968}; 969 970// Traits for: CFGBlock 971 972template <> struct GraphTraits< ::clang::CFGBlock *> { 973 typedef ::clang::CFGBlock *NodeRef; 974 typedef ::clang::CFGBlock::succ_iterator ChildIteratorType; 975 976 static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; } 977 978 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 979 980 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 981}; 982 983template <> struct GraphTraits< const ::clang::CFGBlock *> { 984 typedef const ::clang::CFGBlock *NodeRef; 985 typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType; 986 987 static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; } 988 989 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 990 991 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 992}; 993 994template <> struct GraphTraits<Inverse< ::clang::CFGBlock*> > { 995 typedef ::clang::CFGBlock *NodeRef; 996 typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType; 997 998 static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) { 999 return G.Graph; 1000 } 1001 1002 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } 1003 1004 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } 1005}; 1006 1007template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > { 1008 typedef const ::clang::CFGBlock *NodeRef; 1009 typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType; 1010 1011 static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) { 1012 return G.Graph; 1013 } 1014 1015 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } 1016 1017 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } 1018}; 1019 1020// Traits for: CFG 1021 1022template <> struct GraphTraits< ::clang::CFG* > 1023 : public GraphTraits< ::clang::CFGBlock *> { 1024 1025 typedef ::clang::CFG::iterator nodes_iterator; 1026 1027 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); } 1028 static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} 1029 static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } 1030 static unsigned size(::clang::CFG* F) { return F->size(); } 1031}; 1032 1033template <> struct GraphTraits<const ::clang::CFG* > 1034 : public GraphTraits<const ::clang::CFGBlock *> { 1035 1036 typedef ::clang::CFG::const_iterator nodes_iterator; 1037 1038 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); } 1039 static nodes_iterator nodes_begin( const ::clang::CFG* F) { 1040 return F->nodes_begin(); 1041 } 1042 static nodes_iterator nodes_end( const ::clang::CFG* F) { 1043 return F->nodes_end(); 1044 } 1045 static unsigned size(const ::clang::CFG* F) { 1046 return F->size(); 1047 } 1048}; 1049 1050template <> struct GraphTraits<Inverse< ::clang::CFG*> > 1051 : public GraphTraits<Inverse< ::clang::CFGBlock*> > { 1052 1053 typedef ::clang::CFG::iterator nodes_iterator; 1054 1055 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); } 1056 static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} 1057 static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } 1058}; 1059 1060template <> struct GraphTraits<Inverse<const ::clang::CFG*> > 1061 : public GraphTraits<Inverse<const ::clang::CFGBlock*> > { 1062 1063 typedef ::clang::CFG::const_iterator nodes_iterator; 1064 1065 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); } 1066 static nodes_iterator nodes_begin(const ::clang::CFG* F) { 1067 return F->nodes_begin(); 1068 } 1069 static nodes_iterator nodes_end(const ::clang::CFG* F) { 1070 return F->nodes_end(); 1071 } 1072}; 1073} // end llvm namespace 1074 1075#endif // LLVM_CLANG_ANALYSIS_CFG_H 1076