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_CFG_H
16 #define LLVM_CLANG_CFG_H
18 #include "clang/AST/Stmt.h"
19 #include "clang/Analysis/Support/BumpVector.h"
20 #include "clang/Basic/SourceLocation.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/GraphTraits.h"
23 #include "llvm/ADT/Optional.h"
24 #include "llvm/ADT/OwningPtr.h"
25 #include "llvm/ADT/PointerIntPair.h"
26 #include "llvm/Support/Allocator.h"
27 #include "llvm/Support/Casting.h"
33 class CXXDestructorDecl;
39 class CXXCtorInitializer;
40 class CXXBaseSpecifier;
41 class CXXBindTemporaryExpr;
49 /// CFGElement - Represents a top-level expression in a basic block.
62 DTOR_BEGIN = AutomaticObjectDtor,
63 DTOR_END = TemporaryDtor
67 // The int bits are used to mark the kind.
68 llvm::PointerIntPair<void *, 2> Data1;
69 llvm::PointerIntPair<void *, 2> Data2;
71 CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = 0)
72 : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),
73 Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {}
78 /// \brief Convert to the specified CFGElement type, asserting that this
79 /// CFGElement is of the desired type.
82 assert(T::isKind(*this));
89 /// \brief Convert to the specified CFGElement type, returning None if this
90 /// CFGElement is not of the desired type.
92 Optional<T> getAs() const {
93 if (!T::isKind(*this))
101 Kind getKind() const {
102 unsigned x = Data2.getInt();
109 class CFGStmt : public CFGElement {
111 CFGStmt(Stmt *S) : CFGElement(Statement, S) {}
113 const Stmt *getStmt() const {
114 return static_cast<const Stmt *>(Data1.getPointer());
118 friend class CFGElement;
120 static bool isKind(const CFGElement &E) {
121 return E.getKind() == Statement;
125 /// CFGInitializer - Represents C++ base or member initializer from
126 /// constructor's initialization list.
127 class CFGInitializer : public CFGElement {
129 CFGInitializer(CXXCtorInitializer *initializer)
130 : CFGElement(Initializer, initializer) {}
132 CXXCtorInitializer* getInitializer() const {
133 return static_cast<CXXCtorInitializer*>(Data1.getPointer());
137 friend class CFGElement;
139 static bool isKind(const CFGElement &E) {
140 return E.getKind() == Initializer;
144 /// CFGImplicitDtor - Represents C++ object destructor implicitly generated
145 /// by compiler on various occasions.
146 class CFGImplicitDtor : public CFGElement {
149 CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = 0)
150 : CFGElement(kind, data1, data2) {
151 assert(kind >= DTOR_BEGIN && kind <= DTOR_END);
155 const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const;
156 bool isNoReturn(ASTContext &astContext) const;
159 friend class CFGElement;
160 static bool isKind(const CFGElement &E) {
161 Kind kind = E.getKind();
162 return kind >= DTOR_BEGIN && kind <= DTOR_END;
166 /// CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated
167 /// for automatic object or temporary bound to const reference at the point
168 /// of leaving its local scope.
169 class CFGAutomaticObjDtor: public CFGImplicitDtor {
171 CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)
172 : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {}
174 const VarDecl *getVarDecl() const {
175 return static_cast<VarDecl*>(Data1.getPointer());
178 // Get statement end of which triggered the destructor call.
179 const Stmt *getTriggerStmt() const {
180 return static_cast<Stmt*>(Data2.getPointer());
184 friend class CFGElement;
185 CFGAutomaticObjDtor() {}
186 static bool isKind(const CFGElement &elem) {
187 return elem.getKind() == AutomaticObjectDtor;
191 /// CFGDeleteDtor - Represents C++ object destructor generated
192 /// from a call to delete.
193 class CFGDeleteDtor : public CFGImplicitDtor {
195 CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE)
196 : CFGImplicitDtor(DeleteDtor, RD, DE) {}
198 const CXXRecordDecl *getCXXRecordDecl() const {
199 return static_cast<CXXRecordDecl*>(Data1.getPointer());
202 // Get Delete expression which triggered the destructor call.
203 const CXXDeleteExpr *getDeleteExpr() {
204 return static_cast<CXXDeleteExpr *>(Data2.getPointer());
209 friend class CFGElement;
211 static bool isKind(const CFGElement &elem) {
212 return elem.getKind() == DeleteDtor;
216 /// CFGBaseDtor - Represents C++ object destructor implicitly generated for
217 /// base object in destructor.
218 class CFGBaseDtor : public CFGImplicitDtor {
220 CFGBaseDtor(const CXXBaseSpecifier *base)
221 : CFGImplicitDtor(BaseDtor, base) {}
223 const CXXBaseSpecifier *getBaseSpecifier() const {
224 return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());
228 friend class CFGElement;
230 static bool isKind(const CFGElement &E) {
231 return E.getKind() == BaseDtor;
235 /// CFGMemberDtor - Represents C++ object destructor implicitly generated for
236 /// member object in destructor.
237 class CFGMemberDtor : public CFGImplicitDtor {
239 CFGMemberDtor(const FieldDecl *field)
240 : CFGImplicitDtor(MemberDtor, field, 0) {}
242 const FieldDecl *getFieldDecl() const {
243 return static_cast<const FieldDecl*>(Data1.getPointer());
247 friend class CFGElement;
249 static bool isKind(const CFGElement &E) {
250 return E.getKind() == MemberDtor;
254 /// CFGTemporaryDtor - Represents C++ object destructor implicitly generated
255 /// at the end of full expression for temporary object.
256 class CFGTemporaryDtor : public CFGImplicitDtor {
258 CFGTemporaryDtor(CXXBindTemporaryExpr *expr)
259 : CFGImplicitDtor(TemporaryDtor, expr, 0) {}
261 const CXXBindTemporaryExpr *getBindTemporaryExpr() const {
262 return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer());
266 friend class CFGElement;
267 CFGTemporaryDtor() {}
268 static bool isKind(const CFGElement &E) {
269 return E.getKind() == TemporaryDtor;
273 /// CFGTerminator - Represents CFGBlock terminator statement.
275 /// TemporaryDtorsBranch bit is set to true if the terminator marks a branch
276 /// in control flow of destructors of temporaries. In this case terminator
277 /// statement is the same statement that branches control flow in evaluation
278 /// of matching full expression.
279 class CFGTerminator {
280 llvm::PointerIntPair<Stmt *, 1> Data;
283 CFGTerminator(Stmt *S, bool TemporaryDtorsBranch = false)
284 : Data(S, TemporaryDtorsBranch) {}
286 Stmt *getStmt() { return Data.getPointer(); }
287 const Stmt *getStmt() const { return Data.getPointer(); }
289 bool isTemporaryDtorsBranch() const { return Data.getInt(); }
291 operator Stmt *() { return getStmt(); }
292 operator const Stmt *() const { return getStmt(); }
294 Stmt *operator->() { return getStmt(); }
295 const Stmt *operator->() const { return getStmt(); }
297 Stmt &operator*() { return *getStmt(); }
298 const Stmt &operator*() const { return *getStmt(); }
300 LLVM_EXPLICIT operator bool() const { return getStmt(); }
303 /// CFGBlock - Represents a single basic block in a source-level CFG.
306 /// (1) A set of statements/expressions (which may contain subexpressions).
307 /// (2) A "terminator" statement (not in the set of statements).
308 /// (3) A list of successors and predecessors.
310 /// Terminator: The terminator represents the type of control-flow that occurs
311 /// at the end of the basic block. The terminator is a Stmt* referring to an
312 /// AST node that has control-flow: if-statements, breaks, loops, etc.
313 /// If the control-flow is conditional, the condition expression will appear
314 /// within the set of statements in the block (usually the last statement).
316 /// Predecessors: the order in the set of predecessors is arbitrary.
318 /// Successors: the order in the set of successors is NOT arbitrary. We
319 /// currently have the following orderings based on the terminator:
321 /// Terminator Successor Ordering
322 /// -----------------------------------------------------
323 /// if Then Block; Else Block
324 /// ? operator LHS expression; RHS expression
325 /// &&, || expression that uses result of && or ||, RHS
327 /// But note that any of that may be NULL in case of optimized-out edges.
331 typedef BumpVector<CFGElement> ImplTy;
334 ElementList(BumpVectorContext &C) : Impl(C, 4) {}
336 typedef std::reverse_iterator<ImplTy::iterator> iterator;
337 typedef std::reverse_iterator<ImplTy::const_iterator> const_iterator;
338 typedef ImplTy::iterator reverse_iterator;
339 typedef ImplTy::const_iterator const_reverse_iterator;
340 typedef ImplTy::const_reference const_reference;
342 void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
343 reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
344 BumpVectorContext &C) {
345 return Impl.insert(I, Cnt, E, C);
348 const_reference front() const { return Impl.back(); }
349 const_reference back() const { return Impl.front(); }
351 iterator begin() { return Impl.rbegin(); }
352 iterator end() { return Impl.rend(); }
353 const_iterator begin() const { return Impl.rbegin(); }
354 const_iterator end() const { return Impl.rend(); }
355 reverse_iterator rbegin() { return Impl.begin(); }
356 reverse_iterator rend() { return Impl.end(); }
357 const_reverse_iterator rbegin() const { return Impl.begin(); }
358 const_reverse_iterator rend() const { return Impl.end(); }
360 CFGElement operator[](size_t i) const {
361 assert(i < Impl.size());
362 return Impl[Impl.size() - 1 - i];
365 size_t size() const { return Impl.size(); }
366 bool empty() const { return Impl.empty(); }
369 /// Stmts - The set of statements in the basic block.
370 ElementList Elements;
372 /// Label - An (optional) label that prefixes the executable
373 /// statements in the block. When this variable is non-NULL, it is
374 /// either an instance of LabelStmt, SwitchCase or CXXCatchStmt.
377 /// Terminator - The terminator for a basic block that
378 /// indicates the type of control-flow that occurs between a block
379 /// and its successors.
380 CFGTerminator Terminator;
382 /// LoopTarget - Some blocks are used to represent the "loop edge" to
383 /// the start of a loop from within the loop body. This Stmt* will be
384 /// refer to the loop statement for such blocks (and be null otherwise).
385 const Stmt *LoopTarget;
387 /// BlockID - A numerical ID assigned to a CFGBlock during construction
391 /// Predecessors/Successors - Keep track of the predecessor / successor
393 typedef BumpVector<CFGBlock*> AdjacentBlocks;
394 AdjacentBlocks Preds;
395 AdjacentBlocks Succs;
397 /// NoReturn - This bit is set when the basic block contains a function call
398 /// or implicit destructor that is attributed as 'noreturn'. In that case,
399 /// control cannot technically ever proceed past this block. All such blocks
400 /// will have a single immediate successor: the exit block. This allows them
401 /// to be easily reached from the exit block and using this bit quickly
402 /// recognized without scanning the contents of the block.
404 /// Optimization Note: This bit could be profitably folded with Terminator's
405 /// storage if the memory usage of CFGBlock becomes an issue.
406 unsigned HasNoReturnElement : 1;
408 /// Parent - The parent CFG that owns this CFGBlock.
412 explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
413 : Elements(C), Label(NULL), Terminator(NULL), LoopTarget(NULL),
414 BlockID(blockid), Preds(C, 1), Succs(C, 1), HasNoReturnElement(false),
418 // Statement iterators
419 typedef ElementList::iterator iterator;
420 typedef ElementList::const_iterator const_iterator;
421 typedef ElementList::reverse_iterator reverse_iterator;
422 typedef ElementList::const_reverse_iterator const_reverse_iterator;
424 CFGElement front() const { return Elements.front(); }
425 CFGElement back() const { return Elements.back(); }
427 iterator begin() { return Elements.begin(); }
428 iterator end() { return Elements.end(); }
429 const_iterator begin() const { return Elements.begin(); }
430 const_iterator end() const { return Elements.end(); }
432 reverse_iterator rbegin() { return Elements.rbegin(); }
433 reverse_iterator rend() { return Elements.rend(); }
434 const_reverse_iterator rbegin() const { return Elements.rbegin(); }
435 const_reverse_iterator rend() const { return Elements.rend(); }
437 unsigned size() const { return Elements.size(); }
438 bool empty() const { return Elements.empty(); }
440 CFGElement operator[](size_t i) const { return Elements[i]; }
443 typedef AdjacentBlocks::iterator pred_iterator;
444 typedef AdjacentBlocks::const_iterator const_pred_iterator;
445 typedef AdjacentBlocks::reverse_iterator pred_reverse_iterator;
446 typedef AdjacentBlocks::const_reverse_iterator const_pred_reverse_iterator;
448 typedef AdjacentBlocks::iterator succ_iterator;
449 typedef AdjacentBlocks::const_iterator const_succ_iterator;
450 typedef AdjacentBlocks::reverse_iterator succ_reverse_iterator;
451 typedef AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator;
453 pred_iterator pred_begin() { return Preds.begin(); }
454 pred_iterator pred_end() { return Preds.end(); }
455 const_pred_iterator pred_begin() const { return Preds.begin(); }
456 const_pred_iterator pred_end() const { return Preds.end(); }
458 pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); }
459 pred_reverse_iterator pred_rend() { return Preds.rend(); }
460 const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); }
461 const_pred_reverse_iterator pred_rend() const { return Preds.rend(); }
463 succ_iterator succ_begin() { return Succs.begin(); }
464 succ_iterator succ_end() { return Succs.end(); }
465 const_succ_iterator succ_begin() const { return Succs.begin(); }
466 const_succ_iterator succ_end() const { return Succs.end(); }
468 succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); }
469 succ_reverse_iterator succ_rend() { return Succs.rend(); }
470 const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); }
471 const_succ_reverse_iterator succ_rend() const { return Succs.rend(); }
473 unsigned succ_size() const { return Succs.size(); }
474 bool succ_empty() const { return Succs.empty(); }
476 unsigned pred_size() const { return Preds.size(); }
477 bool pred_empty() const { return Preds.empty(); }
480 class FilterOptions {
483 IgnoreDefaultsWithCoveredEnums = 0;
486 unsigned IgnoreDefaultsWithCoveredEnums : 1;
489 static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
490 const CFGBlock *Dst);
492 template <typename IMPL, bool IsPred>
493 class FilteredCFGBlockIterator {
496 const FilterOptions F;
497 const CFGBlock *From;
499 explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
500 const CFGBlock *from,
501 const FilterOptions &f)
502 : I(i), E(e), F(f), From(from) {}
504 bool hasMore() const { return I != E; }
506 FilteredCFGBlockIterator &operator++() {
507 do { ++I; } while (hasMore() && Filter(*I));
511 const CFGBlock *operator*() const { return *I; }
513 bool Filter(const CFGBlock *To) {
514 return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
518 typedef FilteredCFGBlockIterator<const_pred_iterator, true>
519 filtered_pred_iterator;
521 typedef FilteredCFGBlockIterator<const_succ_iterator, false>
522 filtered_succ_iterator;
524 filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
525 return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
528 filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
529 return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
532 // Manipulation of block contents
534 void setTerminator(Stmt *Statement) { Terminator = Statement; }
535 void setLabel(Stmt *Statement) { Label = Statement; }
536 void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
537 void setHasNoReturnElement() { HasNoReturnElement = true; }
539 CFGTerminator getTerminator() { return Terminator; }
540 const CFGTerminator getTerminator() const { return Terminator; }
542 Stmt *getTerminatorCondition();
544 const Stmt *getTerminatorCondition() const {
545 return const_cast<CFGBlock*>(this)->getTerminatorCondition();
548 const Stmt *getLoopTarget() const { return LoopTarget; }
550 Stmt *getLabel() { return Label; }
551 const Stmt *getLabel() const { return Label; }
553 bool hasNoReturnElement() const { return HasNoReturnElement; }
555 unsigned getBlockID() const { return BlockID; }
557 CFG *getParent() const { return Parent; }
559 void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
560 void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
561 bool ShowColors) const;
562 void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
564 void addSuccessor(CFGBlock *Block, BumpVectorContext &C) {
566 Block->Preds.push_back(this, C);
567 Succs.push_back(Block, C);
570 void appendStmt(Stmt *statement, BumpVectorContext &C) {
571 Elements.push_back(CFGStmt(statement), C);
574 void appendInitializer(CXXCtorInitializer *initializer,
575 BumpVectorContext &C) {
576 Elements.push_back(CFGInitializer(initializer), C);
579 void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
580 Elements.push_back(CFGBaseDtor(BS), C);
583 void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
584 Elements.push_back(CFGMemberDtor(FD), C);
587 void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) {
588 Elements.push_back(CFGTemporaryDtor(E), C);
591 void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
592 Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
595 void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) {
596 Elements.push_back(CFGDeleteDtor(RD, DE), C);
599 // Destructors must be inserted in reversed order. So insertion is in two
600 // steps. First we prepare space for some number of elements, then we insert
601 // the elements beginning at the last position in prepared space.
602 iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt,
603 BumpVectorContext &C) {
604 return iterator(Elements.insert(I.base(), Cnt, CFGAutomaticObjDtor(0, 0), C));
606 iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) {
607 *I = CFGAutomaticObjDtor(VD, S);
612 /// CFG - Represents a source-level, intra-procedural CFG that represents the
613 /// control-flow of a Stmt. The Stmt can represent an entire function body,
614 /// or a single expression. A CFG will always contain one empty block that
615 /// represents the Exit point of the CFG. A CFG will also contain a designated
616 /// Entry block. The CFG solely represents control-flow; it consists of
617 /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
618 /// was constructed from.
621 //===--------------------------------------------------------------------===//
622 // CFG Construction & Manipulation.
623 //===--------------------------------------------------------------------===//
626 std::bitset<Stmt::lastStmtConstant> alwaysAddMask;
628 typedef llvm::DenseMap<const Stmt *, const CFGBlock*> ForcedBlkExprs;
629 ForcedBlkExprs **forcedBlkExprs;
631 bool PruneTriviallyFalseEdges;
633 bool AddInitializers;
634 bool AddImplicitDtors;
635 bool AddTemporaryDtors;
636 bool AddStaticInitBranches;
638 bool alwaysAdd(const Stmt *stmt) const {
639 return alwaysAddMask[stmt->getStmtClass()];
642 BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
643 alwaysAddMask[stmtClass] = val;
647 BuildOptions &setAllAlwaysAdd() {
653 : forcedBlkExprs(0), PruneTriviallyFalseEdges(true)
655 ,AddInitializers(false)
656 ,AddImplicitDtors(false)
657 ,AddTemporaryDtors(false)
658 ,AddStaticInitBranches(false) {}
661 /// \brief Provides a custom implementation of the iterator class to have the
662 /// same interface as Function::iterator - iterator returns CFGBlock
663 /// (not a pointer to CFGBlock).
664 class graph_iterator {
666 typedef const CFGBlock value_type;
667 typedef value_type& reference;
668 typedef value_type* pointer;
669 typedef BumpVector<CFGBlock*>::iterator ImplTy;
671 graph_iterator(const ImplTy &i) : I(i) {}
673 bool operator==(const graph_iterator &X) const { return I == X.I; }
674 bool operator!=(const graph_iterator &X) const { return I != X.I; }
676 reference operator*() const { return **I; }
677 pointer operator->() const { return *I; }
678 operator CFGBlock* () { return *I; }
680 graph_iterator &operator++() { ++I; return *this; }
681 graph_iterator &operator--() { --I; return *this; }
687 class const_graph_iterator {
689 typedef const CFGBlock value_type;
690 typedef value_type& reference;
691 typedef value_type* pointer;
692 typedef BumpVector<CFGBlock*>::const_iterator ImplTy;
694 const_graph_iterator(const ImplTy &i) : I(i) {}
696 bool operator==(const const_graph_iterator &X) const { return I == X.I; }
697 bool operator!=(const const_graph_iterator &X) const { return I != X.I; }
699 reference operator*() const { return **I; }
700 pointer operator->() const { return *I; }
701 operator CFGBlock* () const { return *I; }
703 const_graph_iterator &operator++() { ++I; return *this; }
704 const_graph_iterator &operator--() { --I; return *this; }
710 /// buildCFG - Builds a CFG from an AST. The responsibility to free the
711 /// constructed CFG belongs to the caller.
712 static CFG* buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
713 const BuildOptions &BO);
715 /// createBlock - Create a new block in the CFG. The CFG owns the block;
716 /// the caller should not directly free it.
717 CFGBlock *createBlock();
719 /// setEntry - Set the entry block of the CFG. This is typically used
720 /// only during CFG construction. Most CFG clients expect that the
721 /// entry block has no predecessors and contains no statements.
722 void setEntry(CFGBlock *B) { Entry = B; }
724 /// setIndirectGotoBlock - Set the block used for indirect goto jumps.
725 /// This is typically used only during CFG construction.
726 void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
728 //===--------------------------------------------------------------------===//
730 //===--------------------------------------------------------------------===//
732 typedef BumpVector<CFGBlock*> CFGBlockListTy;
733 typedef CFGBlockListTy::iterator iterator;
734 typedef CFGBlockListTy::const_iterator const_iterator;
735 typedef std::reverse_iterator<iterator> reverse_iterator;
736 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
738 CFGBlock & front() { return *Blocks.front(); }
739 CFGBlock & back() { return *Blocks.back(); }
741 iterator begin() { return Blocks.begin(); }
742 iterator end() { return Blocks.end(); }
743 const_iterator begin() const { return Blocks.begin(); }
744 const_iterator end() const { return Blocks.end(); }
746 graph_iterator nodes_begin() { return graph_iterator(Blocks.begin()); }
747 graph_iterator nodes_end() { return graph_iterator(Blocks.end()); }
748 const_graph_iterator nodes_begin() const {
749 return const_graph_iterator(Blocks.begin());
751 const_graph_iterator nodes_end() const {
752 return const_graph_iterator(Blocks.end());
755 reverse_iterator rbegin() { return Blocks.rbegin(); }
756 reverse_iterator rend() { return Blocks.rend(); }
757 const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
758 const_reverse_iterator rend() const { return Blocks.rend(); }
760 CFGBlock & getEntry() { return *Entry; }
761 const CFGBlock & getEntry() const { return *Entry; }
762 CFGBlock & getExit() { return *Exit; }
763 const CFGBlock & getExit() const { return *Exit; }
765 CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; }
766 const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
768 typedef std::vector<const CFGBlock*>::const_iterator try_block_iterator;
769 try_block_iterator try_blocks_begin() const {
770 return TryDispatchBlocks.begin();
772 try_block_iterator try_blocks_end() const {
773 return TryDispatchBlocks.end();
776 void addTryDispatchBlock(const CFGBlock *block) {
777 TryDispatchBlocks.push_back(block);
780 /// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
782 /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
784 void addSyntheticDeclStmt(const DeclStmt *Synthetic,
785 const DeclStmt *Source) {
786 assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
787 assert(Synthetic != Source && "Don't include original DeclStmts in map");
788 assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
789 SyntheticDeclStmts[Synthetic] = Source;
792 typedef llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator
793 synthetic_stmt_iterator;
795 /// Iterates over synthetic DeclStmts in the CFG.
797 /// Each element is a (synthetic statement, source statement) pair.
799 /// \sa addSyntheticDeclStmt
800 synthetic_stmt_iterator synthetic_stmt_begin() const {
801 return SyntheticDeclStmts.begin();
804 /// \sa synthetic_stmt_begin
805 synthetic_stmt_iterator synthetic_stmt_end() const {
806 return SyntheticDeclStmts.end();
809 //===--------------------------------------------------------------------===//
810 // Member templates useful for various batch operations over CFGs.
811 //===--------------------------------------------------------------------===//
813 template <typename CALLBACK>
814 void VisitBlockStmts(CALLBACK& O) const {
815 for (const_iterator I=begin(), E=end(); I != E; ++I)
816 for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
818 if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
819 O(const_cast<Stmt*>(stmt->getStmt()));
823 //===--------------------------------------------------------------------===//
824 // CFG Introspection.
825 //===--------------------------------------------------------------------===//
827 /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which
829 unsigned getNumBlockIDs() const { return NumBlockIDs; }
831 /// size - Return the total number of CFGBlocks within the CFG
832 /// This is simply a renaming of the getNumBlockIDs(). This is necessary
833 /// because the dominator implementation needs such an interface.
834 unsigned size() const { return NumBlockIDs; }
836 //===--------------------------------------------------------------------===//
837 // CFG Debugging: Pretty-Printing and Visualization.
838 //===--------------------------------------------------------------------===//
840 void viewCFG(const LangOptions &LO) const;
841 void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
842 void dump(const LangOptions &LO, bool ShowColors) const;
844 //===--------------------------------------------------------------------===//
845 // Internal: constructors and data.
846 //===--------------------------------------------------------------------===//
848 CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0),
849 Blocks(BlkBVC, 10) {}
851 llvm::BumpPtrAllocator& getAllocator() {
852 return BlkBVC.getAllocator();
855 BumpVectorContext &getBumpVectorContext() {
862 CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch
863 // for indirect gotos
864 unsigned NumBlockIDs;
866 BumpVectorContext BlkBVC;
868 CFGBlockListTy Blocks;
870 /// C++ 'try' statements are modeled with an indirect dispatch block.
871 /// This is the collection of such blocks present in the CFG.
872 std::vector<const CFGBlock *> TryDispatchBlocks;
874 /// Collects DeclStmts synthesized for this CFG and maps each one back to its
876 llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
878 } // end namespace clang
880 //===----------------------------------------------------------------------===//
881 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
882 //===----------------------------------------------------------------------===//
886 /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
887 /// CFGTerminator to a specific Stmt class.
888 template <> struct simplify_type< ::clang::CFGTerminator> {
889 typedef ::clang::Stmt *SimpleType;
890 static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) {
891 return Val.getStmt();
895 // Traits for: CFGBlock
897 template <> struct GraphTraits< ::clang::CFGBlock *> {
898 typedef ::clang::CFGBlock NodeType;
899 typedef ::clang::CFGBlock::succ_iterator ChildIteratorType;
901 static NodeType* getEntryNode(::clang::CFGBlock *BB)
904 static inline ChildIteratorType child_begin(NodeType* N)
905 { return N->succ_begin(); }
907 static inline ChildIteratorType child_end(NodeType* N)
908 { return N->succ_end(); }
911 template <> struct GraphTraits< const ::clang::CFGBlock *> {
912 typedef const ::clang::CFGBlock NodeType;
913 typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType;
915 static NodeType* getEntryNode(const clang::CFGBlock *BB)
918 static inline ChildIteratorType child_begin(NodeType* N)
919 { return N->succ_begin(); }
921 static inline ChildIteratorType child_end(NodeType* N)
922 { return N->succ_end(); }
925 template <> struct GraphTraits<Inverse< ::clang::CFGBlock*> > {
926 typedef ::clang::CFGBlock NodeType;
927 typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
929 static NodeType *getEntryNode(Inverse< ::clang::CFGBlock*> G)
932 static inline ChildIteratorType child_begin(NodeType* N)
933 { return N->pred_begin(); }
935 static inline ChildIteratorType child_end(NodeType* N)
936 { return N->pred_end(); }
939 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
940 typedef const ::clang::CFGBlock NodeType;
941 typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
943 static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G)
946 static inline ChildIteratorType child_begin(NodeType* N)
947 { return N->pred_begin(); }
949 static inline ChildIteratorType child_end(NodeType* N)
950 { return N->pred_end(); }
955 template <> struct GraphTraits< ::clang::CFG* >
956 : public GraphTraits< ::clang::CFGBlock *> {
958 typedef ::clang::CFG::graph_iterator nodes_iterator;
960 static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
961 static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
962 static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); }
963 static unsigned size(::clang::CFG* F) { return F->size(); }
966 template <> struct GraphTraits<const ::clang::CFG* >
967 : public GraphTraits<const ::clang::CFGBlock *> {
969 typedef ::clang::CFG::const_graph_iterator nodes_iterator;
971 static NodeType *getEntryNode( const ::clang::CFG* F) {
972 return &F->getEntry();
974 static nodes_iterator nodes_begin( const ::clang::CFG* F) {
975 return F->nodes_begin();
977 static nodes_iterator nodes_end( const ::clang::CFG* F) {
978 return F->nodes_end();
980 static unsigned size(const ::clang::CFG* F) {
985 template <> struct GraphTraits<Inverse< ::clang::CFG*> >
986 : public GraphTraits<Inverse< ::clang::CFGBlock*> > {
988 typedef ::clang::CFG::graph_iterator nodes_iterator;
990 static NodeType *getEntryNode( ::clang::CFG* F) { return &F->getExit(); }
991 static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
992 static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
995 template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
996 : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
998 typedef ::clang::CFG::const_graph_iterator nodes_iterator;
1000 static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
1001 static nodes_iterator nodes_begin(const ::clang::CFG* F) {
1002 return F->nodes_begin();
1004 static nodes_iterator nodes_end(const ::clang::CFG* F) {
1005 return F->nodes_end();
1008 } // end llvm namespace