1 //===- CFG.h - Classes for representing and building CFGs -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the CFG and CFGBuilder classes for representing and
11 // building Control-Flow Graphs (CFGs) from ASTs.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_ANALYSIS_CFG_H
16 #define LLVM_CLANG_ANALYSIS_CFG_H
18 #include "clang/AST/Stmt.h"
19 #include "clang/Analysis/Support/BumpVector.h"
20 #include "clang/Basic/LLVM.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/GraphTraits.h"
23 #include "llvm/ADT/None.h"
24 #include "llvm/ADT/Optional.h"
25 #include "llvm/ADT/PointerIntPair.h"
26 #include "llvm/ADT/iterator_range.h"
27 #include "llvm/Support/Allocator.h"
28 #include "llvm/Support/raw_ostream.h"
41 class CXXBaseSpecifier;
42 class CXXBindTemporaryExpr;
43 class CXXCtorInitializer;
45 class CXXDestructorDecl;
53 /// CFGElement - Represents a top-level expression in a basic block.
69 DTOR_BEGIN = AutomaticObjectDtor,
70 DTOR_END = TemporaryDtor
74 // The int bits are used to mark the kind.
75 llvm::PointerIntPair<void *, 2> Data1;
76 llvm::PointerIntPair<void *, 2> Data2;
78 CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr)
79 : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),
80 Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {
81 assert(getKind() == kind);
84 CFGElement() = default;
87 /// \brief Convert to the specified CFGElement type, asserting that this
88 /// CFGElement is of the desired type.
91 assert(T::isKind(*this));
98 /// \brief Convert to the specified CFGElement type, returning None if this
99 /// CFGElement is not of the desired type.
101 Optional<T> getAs() const {
102 if (!T::isKind(*this))
110 Kind getKind() const {
111 unsigned x = Data2.getInt();
118 class CFGStmt : public CFGElement {
120 CFGStmt(Stmt *S) : CFGElement(Statement, S) {}
122 const Stmt *getStmt() const {
123 return static_cast<const Stmt *>(Data1.getPointer());
127 friend class CFGElement;
131 static bool isKind(const CFGElement &E) {
132 return E.getKind() == Statement;
136 /// CFGInitializer - Represents C++ base or member initializer from
137 /// constructor's initialization list.
138 class CFGInitializer : public CFGElement {
140 CFGInitializer(CXXCtorInitializer *initializer)
141 : CFGElement(Initializer, initializer) {}
143 CXXCtorInitializer* getInitializer() const {
144 return static_cast<CXXCtorInitializer*>(Data1.getPointer());
148 friend class CFGElement;
150 CFGInitializer() = default;
152 static bool isKind(const CFGElement &E) {
153 return E.getKind() == Initializer;
157 /// CFGNewAllocator - Represents C++ allocator call.
158 class CFGNewAllocator : public CFGElement {
160 explicit CFGNewAllocator(const CXXNewExpr *S)
161 : CFGElement(NewAllocator, S) {}
163 // Get the new expression.
164 const CXXNewExpr *getAllocatorExpr() const {
165 return static_cast<CXXNewExpr *>(Data1.getPointer());
169 friend class CFGElement;
171 CFGNewAllocator() = default;
173 static bool isKind(const CFGElement &elem) {
174 return elem.getKind() == NewAllocator;
178 /// Represents the point where a loop ends.
179 /// This element is is only produced when building the CFG for the static
180 /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.
182 /// Note: a loop exit element can be reached even when the loop body was never
184 class CFGLoopExit : public CFGElement {
186 explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {}
188 const Stmt *getLoopStmt() const {
189 return static_cast<Stmt *>(Data1.getPointer());
193 friend class CFGElement;
195 CFGLoopExit() = default;
197 static bool isKind(const CFGElement &elem) {
198 return elem.getKind() == LoopExit;
202 /// Represents the point where the lifetime of an automatic object ends
203 class CFGLifetimeEnds : public CFGElement {
205 explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt)
206 : CFGElement(LifetimeEnds, var, stmt) {}
208 const VarDecl *getVarDecl() const {
209 return static_cast<VarDecl *>(Data1.getPointer());
212 const Stmt *getTriggerStmt() const {
213 return static_cast<Stmt *>(Data2.getPointer());
217 friend class CFGElement;
219 CFGLifetimeEnds() = default;
221 static bool isKind(const CFGElement &elem) {
222 return elem.getKind() == LifetimeEnds;
226 /// CFGImplicitDtor - Represents C++ object destructor implicitly generated
227 /// by compiler on various occasions.
228 class CFGImplicitDtor : public CFGElement {
230 CFGImplicitDtor() = default;
232 CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr)
233 : CFGElement(kind, data1, data2) {
234 assert(kind >= DTOR_BEGIN && kind <= DTOR_END);
238 const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const;
239 bool isNoReturn(ASTContext &astContext) const;
242 friend class CFGElement;
244 static bool isKind(const CFGElement &E) {
245 Kind kind = E.getKind();
246 return kind >= DTOR_BEGIN && kind <= DTOR_END;
250 /// CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated
251 /// for automatic object or temporary bound to const reference at the point
252 /// of leaving its local scope.
253 class CFGAutomaticObjDtor: public CFGImplicitDtor {
255 CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)
256 : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {}
258 const VarDecl *getVarDecl() const {
259 return static_cast<VarDecl*>(Data1.getPointer());
262 // Get statement end of which triggered the destructor call.
263 const Stmt *getTriggerStmt() const {
264 return static_cast<Stmt*>(Data2.getPointer());
268 friend class CFGElement;
270 CFGAutomaticObjDtor() = default;
272 static bool isKind(const CFGElement &elem) {
273 return elem.getKind() == AutomaticObjectDtor;
277 /// CFGDeleteDtor - Represents C++ object destructor generated
278 /// from a call to delete.
279 class CFGDeleteDtor : public CFGImplicitDtor {
281 CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE)
282 : CFGImplicitDtor(DeleteDtor, RD, DE) {}
284 const CXXRecordDecl *getCXXRecordDecl() const {
285 return static_cast<CXXRecordDecl*>(Data1.getPointer());
288 // Get Delete expression which triggered the destructor call.
289 const CXXDeleteExpr *getDeleteExpr() const {
290 return static_cast<CXXDeleteExpr *>(Data2.getPointer());
294 friend class CFGElement;
296 CFGDeleteDtor() = default;
298 static bool isKind(const CFGElement &elem) {
299 return elem.getKind() == DeleteDtor;
303 /// CFGBaseDtor - Represents C++ object destructor implicitly generated for
304 /// base object in destructor.
305 class CFGBaseDtor : public CFGImplicitDtor {
307 CFGBaseDtor(const CXXBaseSpecifier *base)
308 : CFGImplicitDtor(BaseDtor, base) {}
310 const CXXBaseSpecifier *getBaseSpecifier() const {
311 return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());
315 friend class CFGElement;
317 CFGBaseDtor() = default;
319 static bool isKind(const CFGElement &E) {
320 return E.getKind() == BaseDtor;
324 /// CFGMemberDtor - Represents C++ object destructor implicitly generated for
325 /// member object in destructor.
326 class CFGMemberDtor : public CFGImplicitDtor {
328 CFGMemberDtor(const FieldDecl *field)
329 : CFGImplicitDtor(MemberDtor, field, nullptr) {}
331 const FieldDecl *getFieldDecl() const {
332 return static_cast<const FieldDecl*>(Data1.getPointer());
336 friend class CFGElement;
338 CFGMemberDtor() = default;
340 static bool isKind(const CFGElement &E) {
341 return E.getKind() == MemberDtor;
345 /// CFGTemporaryDtor - Represents C++ object destructor implicitly generated
346 /// at the end of full expression for temporary object.
347 class CFGTemporaryDtor : public CFGImplicitDtor {
349 CFGTemporaryDtor(CXXBindTemporaryExpr *expr)
350 : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {}
352 const CXXBindTemporaryExpr *getBindTemporaryExpr() const {
353 return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer());
357 friend class CFGElement;
359 CFGTemporaryDtor() = default;
361 static bool isKind(const CFGElement &E) {
362 return E.getKind() == TemporaryDtor;
366 /// CFGTerminator - Represents CFGBlock terminator statement.
368 /// TemporaryDtorsBranch bit is set to true if the terminator marks a branch
369 /// in control flow of destructors of temporaries. In this case terminator
370 /// statement is the same statement that branches control flow in evaluation
371 /// of matching full expression.
372 class CFGTerminator {
373 llvm::PointerIntPair<Stmt *, 1> Data;
376 CFGTerminator() = default;
377 CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false)
378 : Data(S, TemporaryDtorsBranch) {}
380 Stmt *getStmt() { return Data.getPointer(); }
381 const Stmt *getStmt() const { return Data.getPointer(); }
383 bool isTemporaryDtorsBranch() const { return Data.getInt(); }
385 operator Stmt *() { return getStmt(); }
386 operator const Stmt *() const { return getStmt(); }
388 Stmt *operator->() { return getStmt(); }
389 const Stmt *operator->() const { return getStmt(); }
391 Stmt &operator*() { return *getStmt(); }
392 const Stmt &operator*() const { return *getStmt(); }
394 explicit operator bool() const { return getStmt(); }
397 /// CFGBlock - Represents a single basic block in a source-level CFG.
400 /// (1) A set of statements/expressions (which may contain subexpressions).
401 /// (2) A "terminator" statement (not in the set of statements).
402 /// (3) A list of successors and predecessors.
404 /// Terminator: The terminator represents the type of control-flow that occurs
405 /// at the end of the basic block. The terminator is a Stmt* referring to an
406 /// AST node that has control-flow: if-statements, breaks, loops, etc.
407 /// If the control-flow is conditional, the condition expression will appear
408 /// within the set of statements in the block (usually the last statement).
410 /// Predecessors: the order in the set of predecessors is arbitrary.
412 /// Successors: the order in the set of successors is NOT arbitrary. We
413 /// currently have the following orderings based on the terminator:
415 /// Terminator Successor Ordering
416 /// -----------------------------------------------------
417 /// if Then Block; Else Block
418 /// ? operator LHS expression; RHS expression
419 /// &&, || expression that uses result of && or ||, RHS
421 /// But note that any of that may be NULL in case of optimized-out edges.
424 using ImplTy = BumpVector<CFGElement>;
429 ElementList(BumpVectorContext &C) : Impl(C, 4) {}
431 using iterator = std::reverse_iterator<ImplTy::iterator>;
432 using const_iterator = std::reverse_iterator<ImplTy::const_iterator>;
433 using reverse_iterator = ImplTy::iterator;
434 using const_reverse_iterator = ImplTy::const_iterator;
435 using const_reference = ImplTy::const_reference;
437 void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
439 reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
440 BumpVectorContext &C) {
441 return Impl.insert(I, Cnt, E, C);
444 const_reference front() const { return Impl.back(); }
445 const_reference back() const { return Impl.front(); }
447 iterator begin() { return Impl.rbegin(); }
448 iterator end() { return Impl.rend(); }
449 const_iterator begin() const { return Impl.rbegin(); }
450 const_iterator end() const { return Impl.rend(); }
451 reverse_iterator rbegin() { return Impl.begin(); }
452 reverse_iterator rend() { return Impl.end(); }
453 const_reverse_iterator rbegin() const { return Impl.begin(); }
454 const_reverse_iterator rend() const { return Impl.end(); }
456 CFGElement operator[](size_t i) const {
457 assert(i < Impl.size());
458 return Impl[Impl.size() - 1 - i];
461 size_t size() const { return Impl.size(); }
462 bool empty() const { return Impl.empty(); }
465 /// Stmts - The set of statements in the basic block.
466 ElementList Elements;
468 /// Label - An (optional) label that prefixes the executable
469 /// statements in the block. When this variable is non-NULL, it is
470 /// either an instance of LabelStmt, SwitchCase or CXXCatchStmt.
471 Stmt *Label = nullptr;
473 /// Terminator - The terminator for a basic block that
474 /// indicates the type of control-flow that occurs between a block
475 /// and its successors.
476 CFGTerminator Terminator;
478 /// LoopTarget - Some blocks are used to represent the "loop edge" to
479 /// the start of a loop from within the loop body. This Stmt* will be
480 /// refer to the loop statement for such blocks (and be null otherwise).
481 const Stmt *LoopTarget = nullptr;
483 /// BlockID - A numerical ID assigned to a CFGBlock during construction
488 /// This class represents a potential adjacent block in the CFG. It encodes
489 /// whether or not the block is actually reachable, or can be proved to be
490 /// trivially unreachable. For some cases it allows one to encode scenarios
491 /// where a block was substituted because the original (now alternate) block
493 class AdjacentBlock {
500 CFGBlock *ReachableBlock;
501 llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock;
504 /// Construct an AdjacentBlock with a possibly unreachable block.
505 AdjacentBlock(CFGBlock *B, bool IsReachable);
507 /// Construct an AdjacentBlock with a reachable block and an alternate
508 /// unreachable block.
509 AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock);
511 /// Get the reachable block, if one exists.
512 CFGBlock *getReachableBlock() const {
513 return ReachableBlock;
516 /// Get the potentially unreachable block.
517 CFGBlock *getPossiblyUnreachableBlock() const {
518 return UnreachableBlock.getPointer();
521 /// Provide an implicit conversion to CFGBlock* so that
522 /// AdjacentBlock can be substituted for CFGBlock*.
523 operator CFGBlock*() const {
524 return getReachableBlock();
527 CFGBlock& operator *() const {
528 return *getReachableBlock();
531 CFGBlock* operator ->() const {
532 return getReachableBlock();
535 bool isReachable() const {
536 Kind K = (Kind) UnreachableBlock.getInt();
537 return K == AB_Normal || K == AB_Alternate;
542 /// Predecessors/Successors - Keep track of the predecessor / successor
544 using AdjacentBlocks = BumpVector<AdjacentBlock>;
545 AdjacentBlocks Preds;
546 AdjacentBlocks Succs;
548 /// NoReturn - This bit is set when the basic block contains a function call
549 /// or implicit destructor that is attributed as 'noreturn'. In that case,
550 /// control cannot technically ever proceed past this block. All such blocks
551 /// will have a single immediate successor: the exit block. This allows them
552 /// to be easily reached from the exit block and using this bit quickly
553 /// recognized without scanning the contents of the block.
555 /// Optimization Note: This bit could be profitably folded with Terminator's
556 /// storage if the memory usage of CFGBlock becomes an issue.
557 unsigned HasNoReturnElement : 1;
559 /// Parent - The parent CFG that owns this CFGBlock.
563 explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
564 : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1),
565 Succs(C, 1), HasNoReturnElement(false), Parent(parent) {}
567 // Statement iterators
568 using iterator = ElementList::iterator;
569 using const_iterator = ElementList::const_iterator;
570 using reverse_iterator = ElementList::reverse_iterator;
571 using const_reverse_iterator = ElementList::const_reverse_iterator;
573 CFGElement front() const { return Elements.front(); }
574 CFGElement back() const { return Elements.back(); }
576 iterator begin() { return Elements.begin(); }
577 iterator end() { return Elements.end(); }
578 const_iterator begin() const { return Elements.begin(); }
579 const_iterator end() const { return Elements.end(); }
581 reverse_iterator rbegin() { return Elements.rbegin(); }
582 reverse_iterator rend() { return Elements.rend(); }
583 const_reverse_iterator rbegin() const { return Elements.rbegin(); }
584 const_reverse_iterator rend() const { return Elements.rend(); }
586 unsigned size() const { return Elements.size(); }
587 bool empty() const { return Elements.empty(); }
589 CFGElement operator[](size_t i) const { return Elements[i]; }
592 using pred_iterator = AdjacentBlocks::iterator;
593 using const_pred_iterator = AdjacentBlocks::const_iterator;
594 using pred_reverse_iterator = AdjacentBlocks::reverse_iterator;
595 using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
596 using pred_range = llvm::iterator_range<pred_iterator>;
597 using pred_const_range = llvm::iterator_range<const_pred_iterator>;
599 using succ_iterator = AdjacentBlocks::iterator;
600 using const_succ_iterator = AdjacentBlocks::const_iterator;
601 using succ_reverse_iterator = AdjacentBlocks::reverse_iterator;
602 using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
603 using succ_range = llvm::iterator_range<succ_iterator>;
604 using succ_const_range = llvm::iterator_range<const_succ_iterator>;
606 pred_iterator pred_begin() { return Preds.begin(); }
607 pred_iterator pred_end() { return Preds.end(); }
608 const_pred_iterator pred_begin() const { return Preds.begin(); }
609 const_pred_iterator pred_end() const { return Preds.end(); }
611 pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); }
612 pred_reverse_iterator pred_rend() { return Preds.rend(); }
613 const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); }
614 const_pred_reverse_iterator pred_rend() const { return Preds.rend(); }
617 return pred_range(pred_begin(), pred_end());
620 pred_const_range preds() const {
621 return pred_const_range(pred_begin(), pred_end());
624 succ_iterator succ_begin() { return Succs.begin(); }
625 succ_iterator succ_end() { return Succs.end(); }
626 const_succ_iterator succ_begin() const { return Succs.begin(); }
627 const_succ_iterator succ_end() const { return Succs.end(); }
629 succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); }
630 succ_reverse_iterator succ_rend() { return Succs.rend(); }
631 const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); }
632 const_succ_reverse_iterator succ_rend() const { return Succs.rend(); }
635 return succ_range(succ_begin(), succ_end());
638 succ_const_range succs() const {
639 return succ_const_range(succ_begin(), succ_end());
642 unsigned succ_size() const { return Succs.size(); }
643 bool succ_empty() const { return Succs.empty(); }
645 unsigned pred_size() const { return Preds.size(); }
646 bool pred_empty() const { return Preds.empty(); }
649 class FilterOptions {
651 unsigned IgnoreNullPredecessors : 1;
652 unsigned IgnoreDefaultsWithCoveredEnums : 1;
655 : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {}
658 static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
659 const CFGBlock *Dst);
661 template <typename IMPL, bool IsPred>
662 class FilteredCFGBlockIterator {
665 const FilterOptions F;
666 const CFGBlock *From;
669 explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
670 const CFGBlock *from,
671 const FilterOptions &f)
672 : I(i), E(e), F(f), From(from) {
673 while (hasMore() && Filter(*I))
677 bool hasMore() const { return I != E; }
679 FilteredCFGBlockIterator &operator++() {
680 do { ++I; } while (hasMore() && Filter(*I));
684 const CFGBlock *operator*() const { return *I; }
687 bool Filter(const CFGBlock *To) {
688 return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
692 using filtered_pred_iterator =
693 FilteredCFGBlockIterator<const_pred_iterator, true>;
695 using filtered_succ_iterator =
696 FilteredCFGBlockIterator<const_succ_iterator, false>;
698 filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
699 return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
702 filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
703 return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
706 // Manipulation of block contents
708 void setTerminator(CFGTerminator Term) { Terminator = Term; }
709 void setLabel(Stmt *Statement) { Label = Statement; }
710 void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
711 void setHasNoReturnElement() { HasNoReturnElement = true; }
713 CFGTerminator getTerminator() { return Terminator; }
714 const CFGTerminator getTerminator() const { return Terminator; }
716 Stmt *getTerminatorCondition(bool StripParens = true);
718 const Stmt *getTerminatorCondition(bool StripParens = true) const {
719 return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
722 const Stmt *getLoopTarget() const { return LoopTarget; }
724 Stmt *getLabel() { return Label; }
725 const Stmt *getLabel() const { return Label; }
727 bool hasNoReturnElement() const { return HasNoReturnElement; }
729 unsigned getBlockID() const { return BlockID; }
731 CFG *getParent() const { return Parent; }
735 void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
736 void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
737 bool ShowColors) const;
738 void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
739 void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
740 OS << "BB#" << getBlockID();
743 /// Adds a (potentially unreachable) successor block to the current block.
744 void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
746 void appendStmt(Stmt *statement, BumpVectorContext &C) {
747 Elements.push_back(CFGStmt(statement), C);
750 void appendInitializer(CXXCtorInitializer *initializer,
751 BumpVectorContext &C) {
752 Elements.push_back(CFGInitializer(initializer), C);
755 void appendNewAllocator(CXXNewExpr *NE,
756 BumpVectorContext &C) {
757 Elements.push_back(CFGNewAllocator(NE), C);
760 void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
761 Elements.push_back(CFGBaseDtor(BS), C);
764 void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
765 Elements.push_back(CFGMemberDtor(FD), C);
768 void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) {
769 Elements.push_back(CFGTemporaryDtor(E), C);
772 void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
773 Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
776 void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
777 Elements.push_back(CFGLifetimeEnds(VD, S), C);
780 void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
781 Elements.push_back(CFGLoopExit(LoopStmt), C);
784 void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) {
785 Elements.push_back(CFGDeleteDtor(RD, DE), C);
788 // Destructors must be inserted in reversed order. So insertion is in two
789 // steps. First we prepare space for some number of elements, then we insert
790 // the elements beginning at the last position in prepared space.
791 iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt,
792 BumpVectorContext &C) {
793 return iterator(Elements.insert(I.base(), Cnt,
794 CFGAutomaticObjDtor(nullptr, nullptr), C));
796 iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) {
797 *I = CFGAutomaticObjDtor(VD, S);
801 // Scope leaving must be performed in reversed order. So insertion is in two
802 // steps. First we prepare space for some number of elements, then we insert
803 // the elements beginning at the last position in prepared space.
804 iterator beginLifetimeEndsInsert(iterator I, size_t Cnt,
805 BumpVectorContext &C) {
807 Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C));
809 iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S) {
810 *I = CFGLifetimeEnds(VD, S);
815 /// \brief CFGCallback defines methods that should be called when a logical
816 /// operator error is found when building the CFG.
819 CFGCallback() = default;
820 virtual ~CFGCallback() = default;
822 virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
823 virtual void compareBitwiseEquality(const BinaryOperator *B,
824 bool isAlwaysTrue) {}
827 /// CFG - Represents a source-level, intra-procedural CFG that represents the
828 /// control-flow of a Stmt. The Stmt can represent an entire function body,
829 /// or a single expression. A CFG will always contain one empty block that
830 /// represents the Exit point of the CFG. A CFG will also contain a designated
831 /// Entry block. The CFG solely represents control-flow; it consists of
832 /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
833 /// was constructed from.
836 //===--------------------------------------------------------------------===//
837 // CFG Construction & Manipulation.
838 //===--------------------------------------------------------------------===//
841 std::bitset<Stmt::lastStmtConstant> alwaysAddMask;
844 using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>;
846 ForcedBlkExprs **forcedBlkExprs = nullptr;
847 CFGCallback *Observer = nullptr;
848 bool PruneTriviallyFalseEdges = true;
849 bool AddEHEdges = false;
850 bool AddInitializers = false;
851 bool AddImplicitDtors = false;
852 bool AddLifetime = false;
853 bool AddLoopExit = false;
854 bool AddTemporaryDtors = false;
855 bool AddStaticInitBranches = false;
856 bool AddCXXNewAllocator = false;
857 bool AddCXXDefaultInitExprInCtors = false;
859 BuildOptions() = default;
861 bool alwaysAdd(const Stmt *stmt) const {
862 return alwaysAddMask[stmt->getStmtClass()];
865 BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
866 alwaysAddMask[stmtClass] = val;
870 BuildOptions &setAllAlwaysAdd() {
876 /// buildCFG - Builds a CFG from an AST.
877 static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
878 const BuildOptions &BO);
880 /// createBlock - Create a new block in the CFG. The CFG owns the block;
881 /// the caller should not directly free it.
882 CFGBlock *createBlock();
884 /// setEntry - Set the entry block of the CFG. This is typically used
885 /// only during CFG construction. Most CFG clients expect that the
886 /// entry block has no predecessors and contains no statements.
887 void setEntry(CFGBlock *B) { Entry = B; }
889 /// setIndirectGotoBlock - Set the block used for indirect goto jumps.
890 /// This is typically used only during CFG construction.
891 void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
893 //===--------------------------------------------------------------------===//
895 //===--------------------------------------------------------------------===//
897 using CFGBlockListTy = BumpVector<CFGBlock *>;
898 using iterator = CFGBlockListTy::iterator;
899 using const_iterator = CFGBlockListTy::const_iterator;
900 using reverse_iterator = std::reverse_iterator<iterator>;
901 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
903 CFGBlock & front() { return *Blocks.front(); }
904 CFGBlock & back() { return *Blocks.back(); }
906 iterator begin() { return Blocks.begin(); }
907 iterator end() { return Blocks.end(); }
908 const_iterator begin() const { return Blocks.begin(); }
909 const_iterator end() const { return Blocks.end(); }
911 iterator nodes_begin() { return iterator(Blocks.begin()); }
912 iterator nodes_end() { return iterator(Blocks.end()); }
913 const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
914 const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
916 reverse_iterator rbegin() { return Blocks.rbegin(); }
917 reverse_iterator rend() { return Blocks.rend(); }
918 const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
919 const_reverse_iterator rend() const { return Blocks.rend(); }
921 CFGBlock & getEntry() { return *Entry; }
922 const CFGBlock & getEntry() const { return *Entry; }
923 CFGBlock & getExit() { return *Exit; }
924 const CFGBlock & getExit() const { return *Exit; }
926 CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; }
927 const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
929 using try_block_iterator = std::vector<const CFGBlock *>::const_iterator;
931 try_block_iterator try_blocks_begin() const {
932 return TryDispatchBlocks.begin();
935 try_block_iterator try_blocks_end() const {
936 return TryDispatchBlocks.end();
939 void addTryDispatchBlock(const CFGBlock *block) {
940 TryDispatchBlocks.push_back(block);
943 /// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
945 /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
947 void addSyntheticDeclStmt(const DeclStmt *Synthetic,
948 const DeclStmt *Source) {
949 assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
950 assert(Synthetic != Source && "Don't include original DeclStmts in map");
951 assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
952 SyntheticDeclStmts[Synthetic] = Source;
955 using synthetic_stmt_iterator =
956 llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator;
957 using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>;
959 /// Iterates over synthetic DeclStmts in the CFG.
961 /// Each element is a (synthetic statement, source statement) pair.
963 /// \sa addSyntheticDeclStmt
964 synthetic_stmt_iterator synthetic_stmt_begin() const {
965 return SyntheticDeclStmts.begin();
968 /// \sa synthetic_stmt_begin
969 synthetic_stmt_iterator synthetic_stmt_end() const {
970 return SyntheticDeclStmts.end();
973 /// \sa synthetic_stmt_begin
974 synthetic_stmt_range synthetic_stmts() const {
975 return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end());
978 //===--------------------------------------------------------------------===//
979 // Member templates useful for various batch operations over CFGs.
980 //===--------------------------------------------------------------------===//
982 template <typename CALLBACK>
983 void VisitBlockStmts(CALLBACK& O) const {
984 for (const_iterator I=begin(), E=end(); I != E; ++I)
985 for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
987 if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
988 O(const_cast<Stmt*>(stmt->getStmt()));
992 //===--------------------------------------------------------------------===//
993 // CFG Introspection.
994 //===--------------------------------------------------------------------===//
996 /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which
998 unsigned getNumBlockIDs() const { return NumBlockIDs; }
1000 /// size - Return the total number of CFGBlocks within the CFG
1001 /// This is simply a renaming of the getNumBlockIDs(). This is necessary
1002 /// because the dominator implementation needs such an interface.
1003 unsigned size() const { return NumBlockIDs; }
1005 //===--------------------------------------------------------------------===//
1006 // CFG Debugging: Pretty-Printing and Visualization.
1007 //===--------------------------------------------------------------------===//
1009 void viewCFG(const LangOptions &LO) const;
1010 void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
1011 void dump(const LangOptions &LO, bool ShowColors) const;
1013 //===--------------------------------------------------------------------===//
1014 // Internal: constructors and data.
1015 //===--------------------------------------------------------------------===//
1017 CFG() : Blocks(BlkBVC, 10) {}
1019 llvm::BumpPtrAllocator& getAllocator() {
1020 return BlkBVC.getAllocator();
1023 BumpVectorContext &getBumpVectorContext() {
1028 CFGBlock *Entry = nullptr;
1029 CFGBlock *Exit = nullptr;
1031 // Special block to contain collective dispatch for indirect gotos
1032 CFGBlock* IndirectGotoBlock = nullptr;
1034 unsigned NumBlockIDs = 0;
1036 BumpVectorContext BlkBVC;
1038 CFGBlockListTy Blocks;
1040 /// C++ 'try' statements are modeled with an indirect dispatch block.
1041 /// This is the collection of such blocks present in the CFG.
1042 std::vector<const CFGBlock *> TryDispatchBlocks;
1044 /// Collects DeclStmts synthesized for this CFG and maps each one back to its
1045 /// source DeclStmt.
1046 llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
1049 } // namespace clang
1051 //===----------------------------------------------------------------------===//
1052 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
1053 //===----------------------------------------------------------------------===//
1057 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
1058 /// CFGTerminator to a specific Stmt class.
1059 template <> struct simplify_type< ::clang::CFGTerminator> {
1060 using SimpleType = ::clang::Stmt *;
1062 static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) {
1063 return Val.getStmt();
1067 // Traits for: CFGBlock
1069 template <> struct GraphTraits< ::clang::CFGBlock *> {
1070 using NodeRef = ::clang::CFGBlock *;
1071 using ChildIteratorType = ::clang::CFGBlock::succ_iterator;
1073 static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
1074 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1075 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1078 template <> struct GraphTraits< const ::clang::CFGBlock *> {
1079 using NodeRef = const ::clang::CFGBlock *;
1080 using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator;
1082 static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
1083 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
1084 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
1087 template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
1088 using NodeRef = ::clang::CFGBlock *;
1089 using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1091 static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
1095 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1096 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1099 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1100 using NodeRef = const ::clang::CFGBlock *;
1101 using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
1103 static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
1107 static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
1108 static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
1113 template <> struct GraphTraits< ::clang::CFG* >
1114 : public GraphTraits< ::clang::CFGBlock *> {
1115 using nodes_iterator = ::clang::CFG::iterator;
1117 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
1118 static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
1119 static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); }
1120 static unsigned size(::clang::CFG* F) { return F->size(); }
1123 template <> struct GraphTraits<const ::clang::CFG* >
1124 : public GraphTraits<const ::clang::CFGBlock *> {
1125 using nodes_iterator = ::clang::CFG::const_iterator;
1127 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
1129 static nodes_iterator nodes_begin( const ::clang::CFG* F) {
1130 return F->nodes_begin();
1133 static nodes_iterator nodes_end( const ::clang::CFG* F) {
1134 return F->nodes_end();
1137 static unsigned size(const ::clang::CFG* F) {
1142 template <> struct GraphTraits<Inverse< ::clang::CFG *>>
1143 : public GraphTraits<Inverse< ::clang::CFGBlock *>> {
1144 using nodes_iterator = ::clang::CFG::iterator;
1146 static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
1147 static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
1148 static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
1151 template <> struct GraphTraits<Inverse<const ::clang::CFG *>>
1152 : public GraphTraits<Inverse<const ::clang::CFGBlock *>> {
1153 using nodes_iterator = ::clang::CFG::const_iterator;
1155 static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
1157 static nodes_iterator nodes_begin(const ::clang::CFG* F) {
1158 return F->nodes_begin();
1161 static nodes_iterator nodes_end(const ::clang::CFG* F) {
1162 return F->nodes_end();
1168 #endif // LLVM_CLANG_ANALYSIS_CFG_H