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