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 ///
497 /// TemporaryDtorsBranch bit is set to true if the terminator marks a branch
498 /// in control flow of destructors of temporaries. In this case terminator
499 /// statement is the same statement that branches control flow in evaluation
500 /// of matching full expression.
502  llvm::PointerIntPair<Stmt *, 1> Data;
503 
504 public:
505  CFGTerminator() = default;
506  CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false)
507  : Data(S, TemporaryDtorsBranch) {}
508 
509  Stmt *getStmt() { return Data.getPointer(); }
510  const Stmt *getStmt() const { return Data.getPointer(); }
511 
512  bool isTemporaryDtorsBranch() const { return Data.getInt(); }
513 
514  operator Stmt *() { return getStmt(); }
515  operator const Stmt *() const { return getStmt(); }
516 
517  Stmt *operator->() { return getStmt(); }
518  const Stmt *operator->() const { return getStmt(); }
519 
520  Stmt &operator*() { return *getStmt(); }
521  const Stmt &operator*() const { return *getStmt(); }
522 
523  explicit operator bool() const { return getStmt(); }
524 };
525 
526 /// Represents a single basic block in a source-level CFG.
527 /// It consists of:
528 ///
529 /// (1) A set of statements/expressions (which may contain subexpressions).
530 /// (2) A "terminator" statement (not in the set of statements).
531 /// (3) A list of successors and predecessors.
532 ///
533 /// Terminator: The terminator represents the type of control-flow that occurs
534 /// at the end of the basic block. The terminator is a Stmt* referring to an
535 /// AST node that has control-flow: if-statements, breaks, loops, etc.
536 /// If the control-flow is conditional, the condition expression will appear
537 /// within the set of statements in the block (usually the last statement).
538 ///
539 /// Predecessors: the order in the set of predecessors is arbitrary.
540 ///
541 /// Successors: the order in the set of successors is NOT arbitrary. We
542 /// currently have the following orderings based on the terminator:
543 ///
544 /// Terminator Successor Ordering
545 /// -----------------------------------------------------
546 /// if Then Block; Else Block
547 /// ? operator LHS expression; RHS expression
548 /// &&, || expression that uses result of && or ||, RHS
549 ///
550 /// But note that any of that may be NULL in case of optimized-out edges.
551 class CFGBlock {
552  class ElementList {
553  using ImplTy = BumpVector<CFGElement>;
554 
555  ImplTy Impl;
556 
557  public:
558  ElementList(BumpVectorContext &C) : Impl(C, 4) {}
559 
560  using iterator = std::reverse_iterator<ImplTy::iterator>;
561  using const_iterator = std::reverse_iterator<ImplTy::const_iterator>;
562  using reverse_iterator = ImplTy::iterator;
563  using const_reverse_iterator = ImplTy::const_iterator;
564  using const_reference = ImplTy::const_reference;
565 
566  void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
567 
568  reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
569  BumpVectorContext &C) {
570  return Impl.insert(I, Cnt, E, C);
571  }
572 
573  const_reference front() const { return Impl.back(); }
574  const_reference back() const { return Impl.front(); }
575 
576  iterator begin() { return Impl.rbegin(); }
577  iterator end() { return Impl.rend(); }
578  const_iterator begin() const { return Impl.rbegin(); }
579  const_iterator end() const { return Impl.rend(); }
580  reverse_iterator rbegin() { return Impl.begin(); }
581  reverse_iterator rend() { return Impl.end(); }
582  const_reverse_iterator rbegin() const { return Impl.begin(); }
583  const_reverse_iterator rend() const { return Impl.end(); }
584 
585  CFGElement operator[](size_t i) const {
586  assert(i < Impl.size());
587  return Impl[Impl.size() - 1 - i];
588  }
589 
590  size_t size() const { return Impl.size(); }
591  bool empty() const { return Impl.empty(); }
592  };
593 
594  /// The set of statements in the basic block.
595  ElementList Elements;
596 
597  /// An (optional) label that prefixes the executable statements in the block.
598  /// When this variable is non-NULL, it is either an instance of LabelStmt,
599  /// SwitchCase or CXXCatchStmt.
600  Stmt *Label = nullptr;
601 
602  /// The terminator for a basic block that indicates the type of control-flow
603  /// that occurs between a block and its successors.
604  CFGTerminator Terminator;
605 
606  /// Some blocks are used to represent the "loop edge" to the start of a loop
607  /// from within the loop body. This Stmt* will be refer to the loop statement
608  /// for such blocks (and be null otherwise).
609  const Stmt *LoopTarget = nullptr;
610 
611  /// A numerical ID assigned to a CFGBlock during construction of the CFG.
612  unsigned BlockID;
613 
614 public:
615  /// This class represents a potential adjacent block in the CFG. It encodes
616  /// whether or not the block is actually reachable, or can be proved to be
617  /// trivially unreachable. For some cases it allows one to encode scenarios
618  /// where a block was substituted because the original (now alternate) block
619  /// is unreachable.
621  enum Kind {
622  AB_Normal,
623  AB_Unreachable,
624  AB_Alternate
625  };
626 
627  CFGBlock *ReachableBlock;
628  llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock;
629 
630  public:
631  /// Construct an AdjacentBlock with a possibly unreachable block.
632  AdjacentBlock(CFGBlock *B, bool IsReachable);
633 
634  /// Construct an AdjacentBlock with a reachable block and an alternate
635  /// unreachable block.
636  AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock);
637 
638  /// Get the reachable block, if one exists.
640  return ReachableBlock;
641  }
642 
643  /// Get the potentially unreachable block.
645  return UnreachableBlock.getPointer();
646  }
647 
648  /// Provide an implicit conversion to CFGBlock* so that
649  /// AdjacentBlock can be substituted for CFGBlock*.
650  operator CFGBlock*() const {
651  return getReachableBlock();
652  }
653 
654  CFGBlock& operator *() const {
655  return *getReachableBlock();
656  }
657 
658  CFGBlock* operator ->() const {
659  return getReachableBlock();
660  }
661 
662  bool isReachable() const {
663  Kind K = (Kind) UnreachableBlock.getInt();
664  return K == AB_Normal || K == AB_Alternate;
665  }
666  };
667 
668 private:
669  /// Keep track of the predecessor / successor CFG blocks.
671  AdjacentBlocks Preds;
672  AdjacentBlocks Succs;
673 
674  /// This bit is set when the basic block contains a function call
675  /// or implicit destructor that is attributed as 'noreturn'. In that case,
676  /// control cannot technically ever proceed past this block. All such blocks
677  /// will have a single immediate successor: the exit block. This allows them
678  /// to be easily reached from the exit block and using this bit quickly
679  /// recognized without scanning the contents of the block.
680  ///
681  /// Optimization Note: This bit could be profitably folded with Terminator's
682  /// storage if the memory usage of CFGBlock becomes an issue.
683  unsigned HasNoReturnElement : 1;
684 
685  /// The parent CFG that owns this CFGBlock.
686  CFG *Parent;
687 
688 public:
689  explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
690  : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1),
691  Succs(C, 1), HasNoReturnElement(false), Parent(parent) {}
692 
693  // Statement iterators
694  using iterator = ElementList::iterator;
695  using const_iterator = ElementList::const_iterator;
698 
699  CFGElement front() const { return Elements.front(); }
700  CFGElement back() const { return Elements.back(); }
701 
702  iterator begin() { return Elements.begin(); }
703  iterator end() { return Elements.end(); }
704  const_iterator begin() const { return Elements.begin(); }
705  const_iterator end() const { return Elements.end(); }
706 
707  reverse_iterator rbegin() { return Elements.rbegin(); }
708  reverse_iterator rend() { return Elements.rend(); }
709  const_reverse_iterator rbegin() const { return Elements.rbegin(); }
710  const_reverse_iterator rend() const { return Elements.rend(); }
711 
712  unsigned size() const { return Elements.size(); }
713  bool empty() const { return Elements.empty(); }
714 
715  CFGElement operator[](size_t i) const { return Elements[i]; }
716 
717  // CFG iterators
722  using pred_range = llvm::iterator_range<pred_iterator>;
723  using pred_const_range = llvm::iterator_range<const_pred_iterator>;
724 
729  using succ_range = llvm::iterator_range<succ_iterator>;
730  using succ_const_range = llvm::iterator_range<const_succ_iterator>;
731 
732  pred_iterator pred_begin() { return Preds.begin(); }
733  pred_iterator pred_end() { return Preds.end(); }
734  const_pred_iterator pred_begin() const { return Preds.begin(); }
735  const_pred_iterator pred_end() const { return Preds.end(); }
736 
738  pred_reverse_iterator pred_rend() { return Preds.rend(); }
739  const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); }
740  const_pred_reverse_iterator pred_rend() const { return Preds.rend(); }
741 
743  return pred_range(pred_begin(), pred_end());
744  }
745 
747  return pred_const_range(pred_begin(), pred_end());
748  }
749 
750  succ_iterator succ_begin() { return Succs.begin(); }
751  succ_iterator succ_end() { return Succs.end(); }
752  const_succ_iterator succ_begin() const { return Succs.begin(); }
753  const_succ_iterator succ_end() const { return Succs.end(); }
754 
756  succ_reverse_iterator succ_rend() { return Succs.rend(); }
757  const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); }
758  const_succ_reverse_iterator succ_rend() const { return Succs.rend(); }
759 
761  return succ_range(succ_begin(), succ_end());
762  }
763 
765  return succ_const_range(succ_begin(), succ_end());
766  }
767 
768  unsigned succ_size() const { return Succs.size(); }
769  bool succ_empty() const { return Succs.empty(); }
770 
771  unsigned pred_size() const { return Preds.size(); }
772  bool pred_empty() const { return Preds.empty(); }
773 
774 
776  public:
779 
781  : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {}
782  };
783 
784  static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
785  const CFGBlock *Dst);
786 
787  template <typename IMPL, bool IsPred>
789  private:
790  IMPL I, E;
791  const FilterOptions F;
792  const CFGBlock *From;
793 
794  public:
795  explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
796  const CFGBlock *from,
797  const FilterOptions &f)
798  : I(i), E(e), F(f), From(from) {
799  while (hasMore() && Filter(*I))
800  ++I;
801  }
802 
803  bool hasMore() const { return I != E; }
804 
806  do { ++I; } while (hasMore() && Filter(*I));
807  return *this;
808  }
809 
810  const CFGBlock *operator*() const { return *I; }
811 
812  private:
813  bool Filter(const CFGBlock *To) {
814  return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
815  }
816  };
817 
818  using filtered_pred_iterator =
820 
821  using filtered_succ_iterator =
823 
825  return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
826  }
827 
829  return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
830  }
831 
832  // Manipulation of block contents
833 
834  void setTerminator(CFGTerminator Term) { Terminator = Term; }
835  void setLabel(Stmt *Statement) { Label = Statement; }
836  void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
837  void setHasNoReturnElement() { HasNoReturnElement = true; }
838 
839  CFGTerminator getTerminator() { return Terminator; }
840  const CFGTerminator getTerminator() const { return Terminator; }
841 
842  Stmt *getTerminatorCondition(bool StripParens = true);
843 
844  const Stmt *getTerminatorCondition(bool StripParens = true) const {
845  return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
846  }
847 
848  const Stmt *getLoopTarget() const { return LoopTarget; }
849 
850  Stmt *getLabel() { return Label; }
851  const Stmt *getLabel() const { return Label; }
852 
853  bool hasNoReturnElement() const { return HasNoReturnElement; }
854 
855  unsigned getBlockID() const { return BlockID; }
856 
857  CFG *getParent() const { return Parent; }
858 
859  void dump() const;
860 
861  void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
862  void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
863  bool ShowColors) const;
864  void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
865  void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
866  OS << "BB#" << getBlockID();
867  }
868 
869  /// Adds a (potentially unreachable) successor block to the current block.
870  void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
871 
872  void appendStmt(Stmt *statement, BumpVectorContext &C) {
873  Elements.push_back(CFGStmt(statement), C);
874  }
875 
877  BumpVectorContext &C) {
878  Elements.push_back(CFGConstructor(CE, CC), C);
879  }
880 
882  const ConstructionContext *CC,
883  BumpVectorContext &C) {
884  Elements.push_back(CFGCXXRecordTypedCall(E, CC), C);
885  }
886 
888  BumpVectorContext &C) {
889  Elements.push_back(CFGInitializer(initializer), C);
890  }
891 
893  BumpVectorContext &C) {
894  Elements.push_back(CFGNewAllocator(NE), C);
895  }
896 
897  void appendScopeBegin(const VarDecl *VD, const Stmt *S,
898  BumpVectorContext &C) {
899  Elements.push_back(CFGScopeBegin(VD, S), C);
900  }
901 
902  void prependScopeBegin(const VarDecl *VD, const Stmt *S,
903  BumpVectorContext &C) {
904  Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C);
905  }
906 
907  void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
908  Elements.push_back(CFGScopeEnd(VD, S), C);
909  }
910 
911  void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
912  Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C);
913  }
914 
916  Elements.push_back(CFGBaseDtor(BS), C);
917  }
918 
920  Elements.push_back(CFGMemberDtor(FD), C);
921  }
922 
924  Elements.push_back(CFGTemporaryDtor(E), C);
925  }
926 
928  Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
929  }
930 
932  Elements.push_back(CFGLifetimeEnds(VD, S), C);
933  }
934 
935  void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
936  Elements.push_back(CFGLoopExit(LoopStmt), C);
937  }
938 
940  Elements.push_back(CFGDeleteDtor(RD, DE), C);
941  }
942 
943  // Destructors must be inserted in reversed order. So insertion is in two
944  // steps. First we prepare space for some number of elements, then we insert
945  // the elements beginning at the last position in prepared space.
947  BumpVectorContext &C) {
948  return iterator(Elements.insert(I.base(), Cnt,
949  CFGAutomaticObjDtor(nullptr, nullptr), C));
950  }
952  *I = CFGAutomaticObjDtor(VD, S);
953  return ++I;
954  }
955 
956  // Scope leaving must be performed in reversed order. So insertion is in two
957  // steps. First we prepare space for some number of elements, then we insert
958  // the elements beginning at the last position in prepared space.
960  BumpVectorContext &C) {
961  return iterator(
962  Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C));
963  }
965  *I = CFGLifetimeEnds(VD, S);
966  return ++I;
967  }
968 
969  // Scope leaving must be performed in reversed order. So insertion is in two
970  // steps. First we prepare space for some number of elements, then we insert
971  // the elements beginning at the last position in prepared space.
973  return iterator(
974  Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C));
975  }
977  *I = CFGScopeEnd(VD, S);
978  return ++I;
979  }
980 
981 };
982 
983 /// CFGCallback defines methods that should be called when a logical
984 /// operator error is found when building the CFG.
985 class CFGCallback {
986 public:
987  CFGCallback() = default;
988  virtual ~CFGCallback() = default;
989 
990  virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
991  virtual void compareBitwiseEquality(const BinaryOperator *B,
992  bool isAlwaysTrue) {}
993 };
994 
995 /// Represents a source-level, intra-procedural CFG that represents the
996 /// control-flow of a Stmt. The Stmt can represent an entire function body,
997 /// or a single expression. A CFG will always contain one empty block that
998 /// represents the Exit point of the CFG. A CFG will also contain a designated
999 /// Entry block. The CFG solely represents control-flow; it consists of
1000 /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
1001 /// was constructed from.
1002 class CFG {
1003 public:
1004  //===--------------------------------------------------------------------===//
1005  // CFG Construction & Manipulation.
1006  //===--------------------------------------------------------------------===//
1007 
1009  std::bitset<Stmt::lastStmtConstant> alwaysAddMask;
1010 
1011  public:
1012  using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>;
1013 
1014  ForcedBlkExprs **forcedBlkExprs = nullptr;
1015  CFGCallback *Observer = nullptr;
1016  bool PruneTriviallyFalseEdges = true;
1017  bool AddEHEdges = false;
1018  bool AddInitializers = false;
1019  bool AddImplicitDtors = false;
1020  bool AddLifetime = false;
1021  bool AddLoopExit = false;
1022  bool AddTemporaryDtors = false;
1023  bool AddScopes = false;
1024  bool AddStaticInitBranches = false;
1025  bool AddCXXNewAllocator = false;
1026  bool AddCXXDefaultInitExprInCtors = false;
1027  bool AddRichCXXConstructors = false;
1028  bool MarkElidedCXXConstructors = false;
1029 
1030  BuildOptions() = default;
1031 
1032  bool alwaysAdd(const Stmt *stmt) const {
1033  return alwaysAddMask[stmt->getStmtClass()];
1034  }
1035 
1036  BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
1037  alwaysAddMask[stmtClass] = val;
1038  return *this;
1039  }
1040 
1042  alwaysAddMask.set();
1043  return *this;
1044  }
1045  };
1046 
1047  /// Builds a CFG from an AST.
1048  static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
1049  const BuildOptions &BO);
1050 
1051  /// Create a new block in the CFG. The CFG owns the block; the caller should
1052  /// not directly free it.
1053  CFGBlock *createBlock();
1054 
1055  /// Set the entry block of the CFG. This is typically used only during CFG
1056  /// construction. Most CFG clients expect that the entry block has no
1057  /// predecessors and contains no statements.
1058  void setEntry(CFGBlock *B) { Entry = B; }
1059 
1060  /// Set the block used for indirect goto jumps. This is typically used only
1061  /// during CFG construction.
1062  void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
1063 
1064  //===--------------------------------------------------------------------===//
1065  // Block Iterators
1066  //===--------------------------------------------------------------------===//
1067 
1071  using reverse_iterator = std::reverse_iterator<iterator>;
1072  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1073 
1074  CFGBlock & front() { return *Blocks.front(); }
1075  CFGBlock & back() { return *Blocks.back(); }
1076 
1077  iterator begin() { return Blocks.begin(); }
1078  iterator end() { return Blocks.end(); }
1079  const_iterator begin() const { return Blocks.begin(); }
1080  const_iterator end() const { return Blocks.end(); }
1081 
1082  iterator nodes_begin() { return iterator(Blocks.begin()); }
1083  iterator nodes_end() { return iterator(Blocks.end()); }
1084  const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
1085  const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
1086 
1087  reverse_iterator rbegin() { return Blocks.rbegin(); }
1088  reverse_iterator rend() { return Blocks.rend(); }
1089  const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
1090  const_reverse_iterator rend() const { return Blocks.rend(); }
1091 
1092  CFGBlock & getEntry() { return *Entry; }
1093  const CFGBlock & getEntry() const { return *Entry; }
1094  CFGBlock & getExit() { return *Exit; }
1095  const CFGBlock & getExit() const { return *Exit; }
1096 
1097  CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; }
1098  const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
1099 
1100  using try_block_iterator = std::vector<const CFGBlock *>::const_iterator;
1101 
1103  return TryDispatchBlocks.begin();
1104  }
1105 
1107  return TryDispatchBlocks.end();
1108  }
1109 
1110  void addTryDispatchBlock(const CFGBlock *block) {
1111  TryDispatchBlocks.push_back(block);
1112  }
1113 
1114  /// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
1115  ///
1116  /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
1117  /// multiple decls.
1118  void addSyntheticDeclStmt(const DeclStmt *Synthetic,
1119  const DeclStmt *Source) {
1120  assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
1121  assert(Synthetic != Source && "Don't include original DeclStmts in map");
1122  assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
1123  SyntheticDeclStmts[Synthetic] = Source;
1124  }
1125 
1126  using synthetic_stmt_iterator =
1127  llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator;
1128  using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>;
1129 
1130  /// Iterates over synthetic DeclStmts in the CFG.
1131  ///
1132  /// Each element is a (synthetic statement, source statement) pair.
1133  ///
1134  /// \sa addSyntheticDeclStmt
1136  return SyntheticDeclStmts.begin();
1137  }
1138 
1139  /// \sa synthetic_stmt_begin
1141  return SyntheticDeclStmts.end();
1142  }
1143 
1144  /// \sa synthetic_stmt_begin
1146  return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end());
1147  }
1148 
1149  //===--------------------------------------------------------------------===//
1150  // Member templates useful for various batch operations over CFGs.
1151  //===--------------------------------------------------------------------===//
1152 
1153  template <typename CALLBACK>
1154  void VisitBlockStmts(CALLBACK& O) const {
1155  for (const_iterator I = begin(), E = end(); I != E; ++I)
1156  for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end();
1157  BI != BE; ++BI) {
1158  if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
1159  O(const_cast<Stmt*>(stmt->getStmt()));
1160  }
1161  }
1162 
1163  //===--------------------------------------------------------------------===//
1164  // CFG Introspection.
1165  //===--------------------------------------------------------------------===//
1166 
1167  /// Returns the total number of BlockIDs allocated (which start at 0).
1168  unsigned getNumBlockIDs() const { return NumBlockIDs; }
1169 
1170  /// Return the total number of CFGBlocks within the CFG This is simply a
1171  /// renaming of the getNumBlockIDs(). This is necessary because the dominator
1172  /// implementation needs such an interface.
1173  unsigned size() const { return NumBlockIDs; }
1174 
1175  //===--------------------------------------------------------------------===//
1176  // CFG Debugging: Pretty-Printing and Visualization.
1177  //===--------------------------------------------------------------------===//
1178 
1179  void viewCFG(const LangOptions &LO) const;
1180  void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
1181  void dump(const LangOptions &LO, bool ShowColors) const;
1182 
1183  //===--------------------------------------------------------------------===//
1184  // Internal: constructors and data.
1185  //===--------------------------------------------------------------------===//
1186 
1187  CFG() : Blocks(BlkBVC, 10) {}
1188 
1189  llvm::BumpPtrAllocator& getAllocator() {
1190  return BlkBVC.getAllocator();
1191  }
1192 
1194  return BlkBVC;
1195  }
1196 
1197 private:
1198  CFGBlock *Entry = nullptr;
1199  CFGBlock *Exit = nullptr;
1200 
1201  // Special block to contain collective dispatch for indirect gotos
1202  CFGBlock* IndirectGotoBlock = nullptr;
1203 
1204  unsigned NumBlockIDs = 0;
1205 
1206  BumpVectorContext BlkBVC;
1207 
1208  CFGBlockListTy Blocks;
1209 
1210  /// C++ 'try' statements are modeled with an indirect dispatch block.
1211  /// This is the collection of such blocks present in the CFG.
1212  std::vector<const CFGBlock *> TryDispatchBlocks;
1213 
1214  /// Collects DeclStmts synthesized for this CFG and maps each one back to its
1215  /// source DeclStmt.
1216  llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
1217 };
1218 
1219 } // namespace clang
1220 
1221 //===----------------------------------------------------------------------===//
1222 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
1223 //===----------------------------------------------------------------------===//
1224 
1225 namespace llvm {
1226 
1227 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
1228 /// CFGTerminator to a specific Stmt class.
1229 template <> struct simplify_type< ::clang::CFGTerminator> {
1231 
1233  return Val.getStmt();
1234  }
1235 };
1236 
1237 // Traits for: CFGBlock
1238 
1239 template <> struct GraphTraits< ::clang::CFGBlock *> {
1242 
1243  static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
1245  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1246 };
1247 
1248 template <> struct GraphTraits< const ::clang::CFGBlock *> {
1249  using NodeRef = const ::clang::CFGBlock *;
1251 
1252  static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
1254  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1255 };
1256 
1257 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
1260 
1261  static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
1262  return G.Graph;
1263  }
1264 
1266  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1267 };
1268 
1269 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1270  using NodeRef = const ::clang::CFGBlock *;
1272 
1273  static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
1274  return G.Graph;
1275  }
1276 
1278  static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1279 };
1280 
1281 // Traits for: CFG
1282 
1283 template <> struct GraphTraits< ::clang::CFG* >
1284  : public GraphTraits< ::clang::CFGBlock *> {
1286 
1287  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
1288  static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
1289  static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); }
1290  static unsigned size(::clang::CFG* F) { return F->size(); }
1291 };
1292 
1293 template <> struct GraphTraits<const ::clang::CFG* >
1294  : public GraphTraits<const ::clang::CFGBlock *> {
1296 
1297  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
1298 
1299  static nodes_iterator nodes_begin( const ::clang::CFG* F) {
1300  return F->nodes_begin();
1301  }
1302 
1303  static nodes_iterator nodes_end( const ::clang::CFG* F) {
1304  return F->nodes_end();
1305  }
1306 
1307  static unsigned size(const ::clang::CFG* F) {
1308  return F->size();
1309  }
1310 };
1311 
1312 template <> struct GraphTraits<Inverse< ::clang::CFG *>>
1313  : public GraphTraits<Inverse< ::clang::CFGBlock *>> {
1315 
1316  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
1317  static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
1318  static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
1319 };
1320 
1321 template <> struct GraphTraits<Inverse<const ::clang::CFG *>>
1322  : public GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1324 
1325  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
1326 
1327  static nodes_iterator nodes_begin(const ::clang::CFG* F) {
1328  return F->nodes_begin();
1329  }
1330 
1331  static nodes_iterator nodes_end(const ::clang::CFG* F) {
1332  return F->nodes_end();
1333  }
1334 };
1335 
1336 } // namespace llvm
1337 
1338 #endif // LLVM_CLANG_ANALYSIS_CFG_H
void setIndirectGotoBlock(CFGBlock *B)
Set the block used for indirect goto jumps.
Definition: CFG.h:1062
Represents C++ allocator call.
Definition: CFG.h:239
static NodeRef getEntryNode(::clang::CFG *F)
Definition: CFG.h:1287
const_iterator end() const
Definition: CFG.h:1080
succ_reverse_iterator succ_rbegin()
Definition: CFG.h:755
static unsigned size(const ::clang::CFG *F)
Definition: CFG.h:1307
bool empty() const
Definition: CFG.h:713
pred_iterator pred_end()
Definition: CFG.h:733
Stmt * operator->()
Definition: CFG.h:517
CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
Definition: CFG.h:689
iterator end()
Definition: BumpVector.h:94
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:719
iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C)
Definition: CFG.h:972
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:694
succ_iterator succ_begin()
Definition: CFG.h:750
const_pred_reverse_iterator pred_rend() const
Definition: CFG.h:740
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:29
bool isReachable() const
Definition: CFG.h:662
CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt)
Definition: CFG.h:286
Stmt - This represents one statement.
Definition: Stmt.h:65
const_iterator nodes_end() const
Definition: CFG.h:1085
CFGElement front() const
Definition: CFG.h:699
CFGBlock & getEntry()
Definition: CFG.h:1092
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
Definition: CFG.h:1173
void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C)
Definition: CFG.h:907
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:902
unsigned getBlockID() const
Definition: CFG.h:855
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
AdjacentBlocks::iterator succ_iterator
Definition: CFG.h:725
void appendNewAllocator(CXXNewExpr *NE, BumpVectorContext &C)
Definition: CFG.h:892
std::reverse_iterator< iterator > reverse_iterator
Definition: CFG.h:1071
CFGNewAllocator(const CXXNewExpr *S)
Definition: CFG.h:241
CFGElement operator[](size_t i) const
Definition: CFG.h:715
void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C)
Definition: CFG.h:931
llvm::BumpPtrAllocator & getAllocator()
Definition: CFG.h:1189
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:1245
::clang::CFGBlock::succ_iterator ChildIteratorType
Definition: CFG.h:1241
Represents C++ object destructor generated from a call to delete.
Definition: CFG.h:408
const Stmt * getLoopTarget() const
Definition: CFG.h:848
iterator begin()
Definition: CFG.h:702
Represents a call to a C++ constructor.
Definition: ExprCXX.h:1261
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:721
unsigned IgnoreDefaultsWithCoveredEnums
Definition: CFG.h:778
void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C)
Definition: CFG.h:911
Represents a point when we exit a loop.
Definition: ProgramPoint.h:714
unsigned succ_size() const
Definition: CFG.h:768
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:1277
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:1254
const ConstructionContext * getConstructionContext() const
Definition: CFG.h:158
synthetic_stmt_range synthetic_stmts() const
Definition: CFG.h:1145
const_reverse_iterator rbegin() const
Definition: CFG.h:1089
CFGBlock * getReachableBlock() const
Get the reachable block, if one exists.
Definition: CFG.h:639
const CFGBlock & getEntry() const
Definition: CFG.h:1093
const Stmt * getTriggerStmt() const
Definition: CFG.h:393
const_succ_reverse_iterator succ_rbegin() const
Definition: CFG.h:757
Defines the clang::Expr interface and subclasses for C++ expressions.
const_pred_iterator pred_begin() const
Definition: CFG.h:734
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:772
pred_const_range preds() const
Definition: CFG.h:746
const_reverse_iterator rend() const
Definition: CFG.h:710
std::vector< const CFGBlock * >::const_iterator try_block_iterator
Definition: CFG.h:1100
CFGBlock * getPossiblyUnreachableBlock() const
Get the potentially unreachable block.
Definition: CFG.h:644
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:836
::clang::CFGBlock::const_pred_iterator ChildIteratorType
Definition: CFG.h:1259
CFGScopeBegin(const VarDecl *VD, const Stmt *S)
Definition: CFG.h:312
static NodeRef getEntryNode(const clang::CFGBlock *BB)
Definition: CFG.h:1252
Represents a member of a struct/union/class.
Definition: Decl.h:2578
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:1278
bool empty() const
Definition: BumpVector.h:105
iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S)
Definition: CFG.h:951
iterator nodes_end()
Definition: CFG.h:1083
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:383
void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C)
Definition: CFG.h:927
const CXXRecordDecl * getCXXRecordDecl() const
Definition: CFG.h:413
const_iterator nodes_begin() const
Definition: CFG.h:1084
succ_range succs()
Definition: CFG.h:760
clang::CharUnits operator*(clang::CharUnits::QuantityType Scale, const clang::CharUnits &CU)
Definition: CharUnits.h:207
CFGBlock & back()
Definition: CFG.h:1075
void setTerminator(CFGTerminator Term)
Definition: CFG.h:834
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:729
const_iterator begin() const
Definition: CFG.h:1079
iterator end()
Definition: CFG.h:1078
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:726
bool isGLValue() const
Definition: Expr.h:252
const_iterator end() const
Definition: CFG.h:705
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
AdjacentBlocks::iterator pred_iterator
Definition: CFG.h:718
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:3293
static NodeRef getEntryNode(::clang::CFGBlock *BB)
Definition: CFG.h:1243
CFGBlockListTy::iterator iterator
Definition: CFG.h:1069
const VarDecl * getVarDecl() const
Definition: CFG.h:388
unsigned size() const
Definition: CFG.h:712
const CXXBaseSpecifier * getBaseSpecifier() const
Definition: CFG.h:439
void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C)
Definition: CFG.h:935
const_succ_iterator succ_end() const
Definition: CFG.h:753
FilteredCFGBlockIterator(const IMPL &i, const IMPL &e, const CFGBlock *from, const FilterOptions &f)
Definition: CFG.h:795
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1216
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:1127
StmtClass
Definition: Stmt.h:67
reverse_iterator rend()
Definition: CFG.h:708
static ChildIteratorType child_end(NodeRef N)
Definition: CFG.h:1266
llvm::DenseMap< const Stmt *, const CFGBlock * > ForcedBlkExprs
Definition: CFG.h:1012
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:1070
CFG * getParent() const
Definition: CFG.h:857
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:876
static nodes_iterator nodes_begin(::clang::CFG *F)
Definition: CFG.h:1317
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:1265
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1612
const FieldDecl * getFieldDecl() const
Definition: CFG.h:460
const_iterator begin() const
Definition: CFG.h:704
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:915
Represents a single basic block in a source-level CFG.
Definition: CFG.h:551
CFG()
Definition: CFG.h:1187
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:1295
This represents one expression.
Definition: Expr.h:106
const_succ_iterator succ_begin() const
Definition: CFG.h:752
std::string Label
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1002
::clang::CFGBlock::const_succ_iterator ChildIteratorType
Definition: CFG.h:1250
Represents a C++ destructor within a class.
Definition: DeclCXX.h:2705
bool succ_empty() const
Definition: CFG.h:769
CFGLoopExit(const Stmt *stmt)
Definition: CFG.h:267
Represents C++ constructor call.
Definition: CFG.h:150
#define bool
Definition: stdbool.h:31
const_reverse_iterator rend() const
Definition: CFG.h:1090
ElementList::const_iterator const_iterator
Definition: CFG.h:695
bool isTemporaryDtorsBranch() const
Definition: CFG.h:512
static SimpleType getSimplifiedValue(::clang::CFGTerminator Val)
Definition: CFG.h:1232
filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const
Definition: CFG.h:824
QualType getType() const
Definition: Expr.h:128
const_pred_iterator pred_end() const
Definition: CFG.h:735
succ_const_range succs() const
Definition: CFG.h:764
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: BumpVector.h:83
static NodeRef getEntryNode(Inverse< const ::clang::CFGBlock *> G)
Definition: CFG.h:1273
Represents C++ object destructor implicitly generated for base object in destructor.
Definition: CFG.h:434
CFGElement back() const
Definition: CFG.h:700
void addTryDispatchBlock(const CFGBlock *block)
Definition: CFG.h:1110
Stmt & operator*()
Definition: CFG.h:520
reverse_iterator rbegin()
Definition: CFG.h:707
try_block_iterator try_blocks_begin() const
Definition: CFG.h:1102
const_succ_reverse_iterator succ_rend() const
Definition: CFG.h:758
void appendStmt(Stmt *statement, BumpVectorContext &C)
Definition: CFG.h:872
CFGBlock & front()
Definition: CFG.h:1074
CFGTerminator getTerminator()
Definition: CFG.h:839
llvm::cl::opt< std::string > Filter
Kind getKind() const
Definition: CFG.h:118
#define false
Definition: stdbool.h:33
QualType getCanonicalType() const
Definition: Type.h:6113
CFGImplicitDtor(Kind kind, const void *data1, const void *data2=nullptr)
Definition: CFG.h:362
pred_reverse_iterator pred_rend()
Definition: CFG.h:738
BuildOptions & setAlwaysAdd(Stmt::StmtClass stmtClass, bool val=true)
Definition: CFG.h:1036
const Stmt * operator->() const
Definition: CFG.h:518
Stmt * getLabel()
Definition: CFG.h:850
reverse_iterator rbegin()
Definition: CFG.h:1087
::clang::CFGBlock::const_pred_iterator ChildIteratorType
Definition: CFG.h:1271
Represents a new-expression for memory allocation and constructor calls, e.g: "new CXXNewExpr(foo)"...
Definition: ExprCXX.h:1913
void setLabel(Stmt *Statement)
Definition: CFG.h:835
iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S)
Definition: CFG.h:976
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1142
llvm::iterator_range< const_succ_iterator > succ_const_range
Definition: CFG.h:730
virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue)
Definition: CFG.h:990
succ_reverse_iterator succ_rend()
Definition: CFG.h:756
static NodeRef getEntryNode(::clang::CFG *F)
Definition: CFG.h:1316
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:1168
CFGConstructor(CXXConstructExpr *CE, const ConstructionContext *C)
Definition: CFG.h:152
BumpVectorContext & getBumpVectorContext()
Definition: CFG.h:1193
void appendScopeBegin(const VarDecl *VD, const Stmt *S, BumpVectorContext &C)
Definition: CFG.h:897
iterator begin()
Definition: CFG.h:1077
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:1244
succ_iterator succ_end()
Definition: CFG.h:751
BuildOptions & setAllAlwaysAdd()
Definition: CFG.h:1041
const_pred_reverse_iterator pred_rbegin() const
Definition: CFG.h:739
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:805
const Stmt * getTerminatorCondition(bool StripParens=true) const
Definition: CFG.h:844
static NodeRef getEntryNode(const ::clang::CFG *F)
Definition: CFG.h:1325
const Stmt & operator*() const
Definition: CFG.h:521
pred_iterator pred_begin()
Definition: CFG.h:732
static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G)
Definition: CFG.h:1261
const VarDecl * getVarDecl() const
Definition: CFG.h:289
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: CFG.h:1072
Dataflow Directional Tag Classes.
llvm::PointerIntPair< void *, 2 > Data2
Definition: CFG.h:84
void VisitBlockStmts(CALLBACK &O) const
Definition: CFG.h:1154
Represents a delete expression for memory deallocation and destructor calls, e.g. ...
Definition: ExprCXX.h:2169
static nodes_iterator nodes_begin(const ::clang::CFG *F)
Definition: CFG.h:1327
CFGTerminator(Stmt *S, bool TemporaryDtorsBranch=false)
Definition: CFG.h:506
iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt, BumpVectorContext &C)
Definition: CFG.h:946
CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)
Definition: CFG.h:385
virtual void compareBitwiseEquality(const BinaryOperator *B, bool isAlwaysTrue)
Definition: CFG.h:991
const VarDecl * getVarDecl() const
Definition: CFG.h:340
llvm::iterator_range< const_pred_iterator > pred_const_range
Definition: CFG.h:723
static nodes_iterator nodes_begin(const ::clang::CFG *F)
Definition: CFG.h:1299
void appendCXXRecordTypedCall(Expr *E, const ConstructionContext *CC, BumpVectorContext &C)
Definition: CFG.h:881
static unsigned size(::clang::CFG *F)
Definition: CFG.h:1290
unsigned pred_size() const
Definition: CFG.h:771
StmtClass getStmtClass() const
Definition: Stmt.h:1028
void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C)
Definition: CFG.h:939
static nodes_iterator nodes_begin(::clang::CFG *F)
Definition: CFG.h:1288
void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C)
Definition: CFG.h:919
void appendInitializer(CXXCtorInitializer *initializer, BumpVectorContext &C)
Definition: CFG.h:887
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:620
reverse_iterator rend()
Definition: CFG.h:1088
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:1155
const Stmt * getLoopStmt() const
Definition: CFG.h:269
static nodes_iterator nodes_end(const ::clang::CFG *F)
Definition: CFG.h:1303
Represents the point where the lifetime of an automatic object ends.
Definition: CFG.h:284
::clang::CFG::iterator nodes_iterator
Definition: CFG.h:1285
Stmt * getStmt()
Definition: CFG.h:509
const CXXDeleteExpr * getDeleteExpr() const
Definition: CFG.h:418
pred_range preds()
Definition: CFG.h:742
pred_reverse_iterator pred_rbegin()
Definition: CFG.h:737
CFGBlock * getIndirectGotoBlock()
Definition: CFG.h:1097
const CFGBlock * operator*() const
Definition: CFG.h:810
bool alwaysAdd(const Stmt *stmt) const
Definition: CFG.h:1032
try_block_iterator try_blocks_end() const
Definition: CFG.h:1106
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2255
const CFGBlock * getIndirectGotoBlock() const
Definition: CFG.h:1098
AdjacentBlocks::reverse_iterator succ_reverse_iterator
Definition: CFG.h:727
iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S)
Definition: CFG.h:964
AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator
Definition: CFG.h:728
Represents a base class of a C++ class.
Definition: DeclCXX.h:191
::clang::CFG::iterator nodes_iterator
Definition: CFG.h:1314
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:777
bool hasNoReturnElement() const
Definition: CFG.h:853
void setHasNoReturnElement()
Definition: CFG.h:837
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:1289
ConstructionContext&#39;s subclasses describe different ways of constructing an object in C++...
void printAsOperand(raw_ostream &OS, bool)
Definition: CFG.h:865
Represents a C++ struct/union/class.
Definition: DeclCXX.h:299
llvm::iterator_range< synthetic_stmt_iterator > synthetic_stmt_range
Definition: CFG.h:1128
CFGCallback defines methods that should be called when a logical operator error is found when buildin...
Definition: CFG.h:985
static nodes_iterator nodes_end(const ::clang::CFG *F)
Definition: CFG.h:1331
llvm::iterator_range< pred_iterator > pred_range
Definition: CFG.h:722
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:1095
const Stmt * getStmt() const
Definition: CFG.h:510
static NodeRef getEntryNode(const ::clang::CFG *F)
Definition: CFG.h:1297
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:1140
Represents CFGBlock terminator statement.
Definition: CFG.h:501
Represents C++ object destructor implicitly generated for member object in destructor.
Definition: CFG.h:455
AdjacentBlocks::reverse_iterator pred_reverse_iterator
Definition: CFG.h:720
void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C)
Definition: CFG.h:923
synthetic_stmt_iterator synthetic_stmt_begin() const
Iterates over synthetic DeclStmts in the CFG.
Definition: CFG.h:1135
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:709
filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const
Definition: CFG.h:828
CFGTemporaryDtor(CXXBindTemporaryExpr *expr)
Definition: CFG.h:478
iterator nodes_begin()
Definition: CFG.h:1082
iterator end()
Definition: CFG.h:703
const Stmt * getLabel() const
Definition: CFG.h:851
void setEntry(CFGBlock *B)
Set the entry block of the CFG.
Definition: CFG.h:1058
iterator beginLifetimeEndsInsert(iterator I, size_t Cnt, BumpVectorContext &C)
Definition: CFG.h:959
void addSyntheticDeclStmt(const DeclStmt *Synthetic, const DeclStmt *Source)
Records a synthetic DeclStmt and the DeclStmt it was constructed from.
Definition: CFG.h:1118
::clang::CFG::const_iterator nodes_iterator
Definition: CFG.h:1323
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:1318
const CFGTerminator getTerminator() const
Definition: CFG.h:840
static ChildIteratorType child_begin(NodeRef N)
Definition: CFG.h:1253
Represents beginning of a scope implicitly generated by the compiler on encountering a CompoundStmt...
Definition: CFG.h:309
CFGBlock & getExit()
Definition: CFG.h:1094
Represents the point where a loop ends.
Definition: CFG.h:265