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  Stmt *getTerminatorCondition(bool StripParens = true);
864 
865  const Stmt *getTerminatorCondition(bool StripParens = true) const {
866  return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
867  }
868 
869  const Stmt *getLoopTarget() const { return LoopTarget; }
870 
871  Stmt *getLabel() { return Label; }
872  const Stmt *getLabel() const { return Label; }
873 
874  bool hasNoReturnElement() const { return HasNoReturnElement; }
875 
876  unsigned getBlockID() const { return BlockID; }
877 
878  CFG *getParent() const { return Parent; }
879 
880  void dump() const;
881 
882  void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
883  void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
884  bool ShowColors) const;
885 
886  void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
887  void printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
888  bool AddQuotes) const;
889 
890  void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
891  OS << "BB#" << getBlockID();
892  }
893 
894  /// Adds a (potentially unreachable) successor block to the current block.
895  void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
896 
898  Elements.push_back(CFGStmt(statement), C);
899  }
900 
902  BumpVectorContext &C) {
903  Elements.push_back(CFGConstructor(CE, CC), C);
904  }
905 
907  const ConstructionContext *CC,
908  BumpVectorContext &C) {
909  Elements.push_back(CFGCXXRecordTypedCall(E, CC), C);
910  }
911 
913  BumpVectorContext &C) {
914  Elements.push_back(CFGInitializer(initializer), C);
915  }
916 
918  BumpVectorContext &C) {
919  Elements.push_back(CFGNewAllocator(NE), C);
920  }
921 
922  void appendScopeBegin(const VarDecl *VD, const Stmt *S,
923  BumpVectorContext &C) {
924  Elements.push_back(CFGScopeBegin(VD, S), C);
925  }
926 
927  void prependScopeBegin(const VarDecl *VD, const Stmt *S,
928  BumpVectorContext &C) {
929  Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C);
930  }
931 
932  void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
933  Elements.push_back(CFGScopeEnd(VD, S), C);
934  }
935 
936  void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
937  Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C);
938  }
939 
941  Elements.push_back(CFGBaseDtor(BS), C);
942  }
943 
945  Elements.push_back(CFGMemberDtor(FD), C);
946  }
947 
949  Elements.push_back(CFGTemporaryDtor(E), C);
950  }
951 
953  Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
954  }
955 
957  Elements.push_back(CFGLifetimeEnds(VD, S), C);
958  }
959 
960  void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
961  Elements.push_back(CFGLoopExit(LoopStmt), C);
962  }
963 
965  Elements.push_back(CFGDeleteDtor(RD, DE), C);
966  }
967 
968  // Destructors must be inserted in reversed order. So insertion is in two
969  // steps. First we prepare space for some number of elements, then we insert
970  // the elements beginning at the last position in prepared space.
972  BumpVectorContext &C) {
973  return iterator(Elements.insert(I.base(), Cnt,
974  CFGAutomaticObjDtor(nullptr, nullptr), C));
975  }
977  *I = CFGAutomaticObjDtor(VD, S);
978  return ++I;
979  }
980 
981  // Scope leaving must be performed in reversed order. So insertion is in two
982  // steps. First we prepare space for some number of elements, then we insert
983  // the elements beginning at the last position in prepared space.
985  BumpVectorContext &C) {
986  return iterator(
987  Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C));
988  }
990  *I = CFGLifetimeEnds(VD, S);
991  return ++I;
992  }
993 
994  // Scope leaving must be performed in reversed order. So insertion is in two
995  // steps. First we prepare space for some number of elements, then we insert
996  // the elements beginning at the last position in prepared space.
998  return iterator(
999  Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C));
1000  }
1002  *I = CFGScopeEnd(VD, S);
1003  return ++I;
1004  }
1005 
1006 };
1007 
1008 /// CFGCallback defines methods that should be called when a logical
1009 /// operator error is found when building the CFG.
1011 public:
1012  CFGCallback() = default;
1013  virtual ~CFGCallback() = default;
1014 
1015  virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
1017  bool isAlwaysTrue) {}
1018 };
1019 
1020 /// Represents a source-level, intra-procedural CFG that represents the
1021 /// control-flow of a Stmt. The Stmt can represent an entire function body,
1022 /// or a single expression. A CFG will always contain one empty block that
1023 /// represents the Exit point of the CFG. A CFG will also contain a designated
1024 /// Entry block. The CFG solely represents control-flow; it consists of
1025 /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
1026 /// was constructed from.
1027 class CFG {
1028 public:
1029  //===--------------------------------------------------------------------===//
1030  // CFG Construction & Manipulation.
1031  //===--------------------------------------------------------------------===//
1032 
1034  std::bitset<Stmt::lastStmtConstant> alwaysAddMask;
1035 
1036  public:
1037  using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>;
1038 
1039  ForcedBlkExprs **forcedBlkExprs = nullptr;
1040  CFGCallback *Observer = nullptr;
1041  bool PruneTriviallyFalseEdges = true;
1042  bool AddEHEdges = false;
1043  bool AddInitializers = false;
1044  bool AddImplicitDtors = false;
1045  bool AddLifetime = false;
1046  bool AddLoopExit = false;
1047  bool AddTemporaryDtors = false;
1048  bool AddScopes = false;
1049  bool AddStaticInitBranches = false;
1050  bool AddCXXNewAllocator = false;
1051  bool AddCXXDefaultInitExprInCtors = false;
1052  bool AddRichCXXConstructors = false;
1053  bool MarkElidedCXXConstructors = false;
1054  bool AddVirtualBaseBranches = false;
1055 
1056  BuildOptions() = default;
1057 
1058  bool alwaysAdd(const Stmt *stmt) const {
1059  return alwaysAddMask[stmt->getStmtClass()];
1060  }
1061 
1062  BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
1063  alwaysAddMask[stmtClass] = val;
1064  return *this;
1065  }
1066 
1068  alwaysAddMask.set();
1069  return *this;
1070  }
1071  };
1072 
1073  /// Builds a CFG from an AST.
1074  static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
1075  const BuildOptions &BO);
1076 
1077  /// Create a new block in the CFG. The CFG owns the block; the caller should
1078  /// not directly free it.
1079  CFGBlock *createBlock();
1080 
1081  /// Set the entry block of the CFG. This is typically used only during CFG
1082  /// construction. Most CFG clients expect that the entry block has no
1083  /// predecessors and contains no statements.
1084  void setEntry(CFGBlock *B) { Entry = B; }
1085 
1086  /// Set the block used for indirect goto jumps. This is typically used only
1087  /// during CFG construction.
1088  void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
1089 
1090  //===--------------------------------------------------------------------===//
1091  // Block Iterators
1092  //===--------------------------------------------------------------------===//
1093 
1097  using reverse_iterator = std::reverse_iterator<iterator>;
1098  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1099 
1100  CFGBlock & front() { return *Blocks.front(); }
1101  CFGBlock & back() { return *Blocks.back(); }
1102 
1103  iterator begin() { return Blocks.begin(); }
1104  iterator end() { return Blocks.end(); }
1105  const_iterator begin() const { return Blocks.begin(); }
1106  const_iterator end() const { return Blocks.end(); }
1107 
1108  iterator nodes_begin() { return iterator(Blocks.begin()); }
1109  iterator nodes_end() { return iterator(Blocks.end()); }
1110  const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
1111  const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
1112 
1113  reverse_iterator rbegin() { return Blocks.rbegin(); }
1114  reverse_iterator rend() { return Blocks.rend(); }
1115  const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
1116  const_reverse_iterator rend() const { return Blocks.rend(); }
1117 
1118  CFGBlock & getEntry() { return *Entry; }
1119  const CFGBlock & getEntry() const { return *Entry; }
1120  CFGBlock & getExit() { return *Exit; }
1121  const CFGBlock & getExit() const { return *Exit; }
1122 
1123  CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; }
1124  const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
1125 
1126  using try_block_iterator = std::vector<const CFGBlock *>::const_iterator;
1127 
1129  return TryDispatchBlocks.begin();
1130  }
1131 
1133  return TryDispatchBlocks.end();
1134  }
1135 
1136  void addTryDispatchBlock(const CFGBlock *block) {
1137  TryDispatchBlocks.push_back(block);
1138  }
1139 
1140  /// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
1141  ///
1142  /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
1143  /// multiple decls.
1144  void addSyntheticDeclStmt(const DeclStmt *Synthetic,
1145  const DeclStmt *Source) {
1146  assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
1147  assert(Synthetic != Source && "Don't include original DeclStmts in map");
1148  assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
1149  SyntheticDeclStmts[Synthetic] = Source;
1150  }
1151 
1152  using synthetic_stmt_iterator =
1153  llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator;
1154  using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>;
1155 
1156  /// Iterates over synthetic DeclStmts in the CFG.
1157  ///
1158  /// Each element is a (synthetic statement, source statement) pair.
1159  ///
1160  /// \sa addSyntheticDeclStmt
1162  return SyntheticDeclStmts.begin();
1163  }
1164 
1165  /// \sa synthetic_stmt_begin
1167  return SyntheticDeclStmts.end();
1168  }
1169 
1170  /// \sa synthetic_stmt_begin
1172  return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end());
1173  }
1174 
1175  //===--------------------------------------------------------------------===//
1176  // Member templates useful for various batch operations over CFGs.
1177  //===--------------------------------------------------------------------===//
1178 
1179  template <typename CALLBACK>
1180  void VisitBlockStmts(CALLBACK& O) const {
1181  for (const_iterator I = begin(), E = end(); I != E; ++I)
1182  for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end();
1183  BI != BE; ++BI) {
1184  if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
1185  O(const_cast<Stmt*>(stmt->getStmt()));
1186  }
1187  }
1188 
1189  //===--------------------------------------------------------------------===//
1190  // CFG Introspection.
1191  //===--------------------------------------------------------------------===//
1192 
1193  /// Returns the total number of BlockIDs allocated (which start at 0).
1194  unsigned getNumBlockIDs() const { return NumBlockIDs; }
1195 
1196  /// Return the total number of CFGBlocks within the CFG This is simply a
1197  /// renaming of the getNumBlockIDs(). This is necessary because the dominator
1198  /// implementation needs such an interface.
1199  unsigned size() const { return NumBlockIDs; }
1200 
1201  /// Returns true if the CFG has no branches. Usually it boils down to the CFG
1202  /// having exactly three blocks (entry, the actual code, exit), but sometimes
1203  /// more blocks appear due to having control flow that can be fully
1204  /// resolved in compile time.
1205  bool isLinear() const;
1206 
1207  //===--------------------------------------------------------------------===//
1208  // CFG Debugging: Pretty-Printing and Visualization.
1209  //===--------------------------------------------------------------------===//
1210 
1211  void viewCFG(const LangOptions &LO) const;
1212  void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
1213  void dump(const LangOptions &LO, bool ShowColors) const;
1214 
1215  //===--------------------------------------------------------------------===//
1216  // Internal: constructors and data.
1217  //===--------------------------------------------------------------------===//
1218 
1219  CFG() : Blocks(BlkBVC, 10) {}
1220 
1221  llvm::BumpPtrAllocator& getAllocator() {
1222  return BlkBVC.getAllocator();
1223  }
1224 
1226  return BlkBVC;
1227  }
1228 
1229 private:
1230  CFGBlock *Entry = nullptr;
1231  CFGBlock *Exit = nullptr;
1232 
1233  // Special block to contain collective dispatch for indirect gotos
1234  CFGBlock* IndirectGotoBlock = nullptr;
1235 
1236  unsigned NumBlockIDs = 0;
1237 
1238  BumpVectorContext BlkBVC;
1239 
1240  CFGBlockListTy Blocks;
1241 
1242  /// C++ 'try' statements are modeled with an indirect dispatch block.
1243  /// This is the collection of such blocks present in the CFG.
1244  std::vector<const CFGBlock *> TryDispatchBlocks;
1245 
1246  /// Collects DeclStmts synthesized for this CFG and maps each one back to its
1247  /// source DeclStmt.
1248  llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
1249 };
1250 
1251 } // namespace clang
1252 
1253 //===----------------------------------------------------------------------===//
1254 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
1255 //===----------------------------------------------------------------------===//
1256 
1257 namespace llvm {
1258 
1259 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
1260 /// CFGTerminator to a specific Stmt class.
1261 template <> struct simplify_type< ::clang::CFGTerminator> {
1263 
1265  return Val.getStmt();
1266  }
1267 };
1268 
1269 // Traits for: CFGBlock
1270 
1271 template <> struct GraphTraits< ::clang::CFGBlock *> {
1274 
1275  static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
1277  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1278 };
1279 
1280 template <> struct GraphTraits< const ::clang::CFGBlock *> {
1281  using NodeRef = const ::clang::CFGBlock *;
1283 
1284  static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
1286  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1287 };
1288 
1289 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
1292 
1293  static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
1294  return G.Graph;
1295  }
1296 
1298  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1299 };
1300 
1301 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1302  using NodeRef = const ::clang::CFGBlock *;
1304 
1305  static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
1306  return G.Graph;
1307  }
1308 
1310  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1311 };
1312 
1313 // Traits for: CFG
1314 
1315 template <> struct GraphTraits< ::clang::CFG* >
1316  : public GraphTraits< ::clang::CFGBlock *> {
1318 
1319  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
1320  static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
1321  static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); }
1322  static unsigned size(::clang::CFG* F) { return F->size(); }
1323 };
1324 
1325 template <> struct GraphTraits<const ::clang::CFG* >
1326  : public GraphTraits<const ::clang::CFGBlock *> {
1328 
1329  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
1330 
1331  static nodes_iterator nodes_begin( const ::clang::CFG* F) {
1332  return F->nodes_begin();
1333  }
1334 
1335  static nodes_iterator nodes_end( const ::clang::CFG* F) {
1336  return F->nodes_end();
1337  }
1338 
1339  static unsigned size(const ::clang::CFG* F) {
1340  return F->size();
1341  }
1342 };
1343 
1344 template <> struct GraphTraits<Inverse< ::clang::CFG *>>
1345  : public GraphTraits<Inverse< ::clang::CFGBlock *>> {
1347 
1348  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
1349  static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
1350  static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
1351 };
1352 
1353 template <> struct GraphTraits<Inverse<const ::clang::CFG *>>
1354  : public GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1356 
1357  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
1358 
1359  static nodes_iterator nodes_begin(const ::clang::CFG* F) {
1360  return F->nodes_begin();
1361  }
1362 
1363  static nodes_iterator nodes_end(const ::clang::CFG* F) {
1364  return F->nodes_end();
1365  }
1366 };
1367 
1368 } // namespace llvm
1369 
1370 #endif // LLVM_CLANG_ANALYSIS_CFG_H
void setIndirectGotoBlock(CFGBlock *B)
Set the block used for indirect goto jumps.
Definition: CFG.h:1088
Represents C++ allocator call.
Definition: CFG.h:239
static NodeRef getEntryNode(::clang::CFG *F)
Definition: CFG.h:1319
const_iterator end() const
Definition: CFG.h:1106
succ_reverse_iterator succ_rbegin()
Definition: CFG.h:774
static unsigned size(const ::clang::CFG *F)
Definition: CFG.h:1339
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:997
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
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:29
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:1111
CFGElement front() const
Definition: CFG.h:718
CFGBlock & getEntry()
Definition: CFG.h:1118
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
Definition: CFG.h:1199
void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C)
Definition: CFG.h:932
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:927
unsigned getBlockID() const
Definition: CFG.h:876
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:917
std::reverse_iterator< iterator > reverse_iterator
Definition: CFG.h:1097
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:956
llvm::BumpPtrAllocator & getAllocator()
Definition: CFG.h:1221
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:1277
::clang::CFGBlock::succ_iterator ChildIteratorType
Definition: CFG.h:1273
Represents C++ object destructor generated from a call to delete.
Definition: CFG.h:408
const Stmt * getLoopTarget() const
Definition: CFG.h:869
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:936
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:1309
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:1286
const ConstructionContext * getConstructionContext() const
Definition: CFG.h:158
synthetic_stmt_range synthetic_stmts() const
Definition: CFG.h:1171
const_reverse_iterator rbegin() const
Definition: CFG.h:1115
CFGBlock * getReachableBlock() const
Get the reachable block, if one exists.
Definition: CFG.h:658
const CFGBlock & getEntry() const
Definition: CFG.h:1119
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:1126
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:1291
CFGScopeBegin(const VarDecl *VD, const Stmt *S)
Definition: CFG.h:312
static NodeRef getEntryNode(const clang::CFGBlock *BB)
Definition: CFG.h:1284
Represents a member of a struct/union/class.
Definition: Decl.h:2605
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:1310
bool empty() const
Definition: BumpVector.h:105
iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S)
Definition: CFG.h:976
iterator nodes_end()
Definition: CFG.h:1109
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:952
const CXXRecordDecl * getCXXRecordDecl() const
Definition: CFG.h:413
const_iterator nodes_begin() const
Definition: CFG.h:1110
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:1101
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:1105
iterator end()
Definition: CFG.h:1104
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:3407
static NodeRef getEntryNode(::clang::CFGBlock *BB)
Definition: CFG.h:1275
CFGBlockListTy::iterator iterator
Definition: CFG.h:1095
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:960
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:1153
StmtClass
Definition: Stmt.h:68
reverse_iterator rend()
Definition: CFG.h:727
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:1298
llvm::DenseMap< const Stmt *, const CFGBlock * > ForcedBlkExprs
Definition: CFG.h:1037
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:1096
CFG * getParent() const
Definition: CFG.h:878
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:901
static nodes_iterator nodes_begin(::clang::CFG *F)
Definition: CFG.h:1349
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:1297
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:940
Represents a single basic block in a source-level CFG.
Definition: CFG.h:570
CFG()
Definition: CFG.h:1219
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:1327
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:1027
::clang::CFGBlock::const_succ_iterator ChildIteratorType
Definition: CFG.h:1282
Represents a C++ destructor within a class.
Definition: DeclCXX.h:2825
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:1116
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:1264
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:1305
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:1136
reverse_iterator rbegin()
Definition: CFG.h:726
try_block_iterator try_blocks_begin() const
Definition: CFG.h:1128
const_succ_reverse_iterator succ_rend() const
Definition: CFG.h:777
void appendStmt(Stmt *statement, BumpVectorContext &C)
Definition: CFG.h:897
CFGBlock & front()
Definition: CFG.h:1100
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:6166
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:1062
Stmt * getLabel()
Definition: CFG.h:871
reverse_iterator rbegin()
Definition: CFG.h:1113
::clang::CFGBlock::const_pred_iterator ChildIteratorType
Definition: CFG.h:1303
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:1001
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1196
llvm::iterator_range< const_succ_iterator > succ_const_range
Definition: CFG.h:749
virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue)
Definition: CFG.h:1015
succ_reverse_iterator succ_rend()
Definition: CFG.h:775
static NodeRef getEntryNode(::clang::CFG *F)
Definition: CFG.h:1348
__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:1194
CFGConstructor(CXXConstructExpr *CE, const ConstructionContext *C)
Definition: CFG.h:152
BumpVectorContext & getBumpVectorContext()
Definition: CFG.h:1225
void appendScopeBegin(const VarDecl *VD, const Stmt *S, BumpVectorContext &C)
Definition: CFG.h:922
iterator begin()
Definition: CFG.h:1103
bool isValid() const
Definition: CFG.h:528
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:1276
succ_iterator succ_end()
Definition: CFG.h:770
BuildOptions & setAllAlwaysAdd()
Definition: CFG.h:1067
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:865
static NodeRef getEntryNode(const ::clang::CFG *F)
Definition: CFG.h:1357
pred_iterator pred_begin()
Definition: CFG.h:751
static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G)
Definition: CFG.h:1293
const VarDecl * getVarDecl() const
Definition: CFG.h:289
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: CFG.h:1098
Dataflow Directional Tag Classes.
llvm::PointerIntPair< void *, 2 > Data2
Definition: CFG.h:84
void VisitBlockStmts(CALLBACK &O) const
Definition: CFG.h:1180
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:1359
iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt, BumpVectorContext &C)
Definition: CFG.h:971
CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)
Definition: CFG.h:385
virtual void compareBitwiseEquality(const BinaryOperator *B, bool isAlwaysTrue)
Definition: CFG.h:1016
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:1331
void appendCXXRecordTypedCall(Expr *E, const ConstructionContext *CC, BumpVectorContext &C)
Definition: CFG.h:906
static unsigned size(::clang::CFG *F)
Definition: CFG.h:1322
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:1080
void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C)
Definition: CFG.h:964
bool isVirtualBaseBranch() const
Definition: CFG.h:539
Stmt * getTerminatorStmt()
Definition: CFG.h:860
static nodes_iterator nodes_begin(::clang::CFG *F)
Definition: CFG.h:1320
void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C)
Definition: CFG.h:944
void appendInitializer(CXXCtorInitializer *initializer, BumpVectorContext &C)
Definition: CFG.h:912
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:1114
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:1209
const Stmt * getLoopStmt() const
Definition: CFG.h:269
static nodes_iterator nodes_end(const ::clang::CFG *F)
Definition: CFG.h:1335
Represents the point where the lifetime of an automatic object ends.
Definition: CFG.h:284
::clang::CFG::iterator nodes_iterator
Definition: CFG.h:1317
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:1123
const CFGBlock * operator*() const
Definition: CFG.h:829
bool alwaysAdd(const Stmt *stmt) const
Definition: CFG.h:1058
try_block_iterator try_blocks_end() const
Definition: CFG.h:1132
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2333
const CFGBlock * getIndirectGotoBlock() const
Definition: CFG.h:1124
AdjacentBlocks::reverse_iterator succ_reverse_iterator
Definition: CFG.h:746
iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S)
Definition: CFG.h:989
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:1346
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:874
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:1321
ConstructionContext&#39;s subclasses describe different ways of constructing an object in C++...
void printAsOperand(raw_ostream &OS, bool)
Definition: CFG.h:890
Represents a C++ struct/union/class.
Definition: DeclCXX.h:300
llvm::iterator_range< synthetic_stmt_iterator > synthetic_stmt_range
Definition: CFG.h:1154
CFGCallback defines methods that should be called when a logical operator error is found when buildin...
Definition: CFG.h:1010
static nodes_iterator nodes_end(const ::clang::CFG *F)
Definition: CFG.h:1363
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:1121
const Stmt * getStmt() const
Definition: CFG.h:530
static NodeRef getEntryNode(const ::clang::CFG *F)
Definition: CFG.h:1329
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:1166
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:948
synthetic_stmt_iterator synthetic_stmt_begin() const
Iterates over synthetic DeclStmts in the CFG.
Definition: CFG.h:1161
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:1108
iterator end()
Definition: CFG.h:722
CFGTerminator getTerminator() const
Definition: CFG.h:858
const Stmt * getLabel() const
Definition: CFG.h:872
void setEntry(CFGBlock *B)
Set the entry block of the CFG.
Definition: CFG.h:1084
iterator beginLifetimeEndsInsert(iterator I, size_t Cnt, BumpVectorContext &C)
Definition: CFG.h:984
void addSyntheticDeclStmt(const DeclStmt *Synthetic, const DeclStmt *Source)
Records a synthetic DeclStmt and the DeclStmt it was constructed from.
Definition: CFG.h:1144
::clang::CFG::const_iterator nodes_iterator
Definition: CFG.h:1355
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:1350
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:1285
Represents beginning of a scope implicitly generated by the compiler on encountering a CompoundStmt...
Definition: CFG.h:309
CFGBlock & getExit()
Definition: CFG.h:1120
Represents the point where a loop ends.
Definition: CFG.h:265