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