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