contrib/llvm/tools/clang/include/clang/Analysis/CFG.h

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