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 "llvm/ADT/PointerIntPair.h"
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/Support/Allocator.h"
21 #include "llvm/Support/Casting.h"
22 #include "clang/Analysis/Support/BumpVector.h"
23 #include "clang/Basic/SourceLocation.h"
38 /// CFGElement - Represents a top-level expression in a basic block.
40 llvm::PointerIntPair<Stmt *, 2> Data;
42 enum Type { StartScope, EndScope };
43 explicit CFGElement() {}
44 CFGElement(Stmt *S, bool lvalue) : Data(S, lvalue ? 1 : 0) {}
45 CFGElement(Stmt *S, Type t) : Data(S, t == StartScope ? 2 : 3) {}
46 Stmt *getStmt() const { return Data.getPointer(); }
47 bool asLValue() const { return Data.getInt() == 1; }
48 bool asStartScope() const { return Data.getInt() == 2; }
49 bool asEndScope() const { return Data.getInt() == 3; }
50 bool asDtor() const { return Data.getInt() == 4; }
51 operator Stmt*() const { return getStmt(); }
52 operator bool() const { return getStmt() != 0; }
55 /// CFGBlock - Represents a single basic block in a source-level CFG.
58 /// (1) A set of statements/expressions (which may contain subexpressions).
59 /// (2) A "terminator" statement (not in the set of statements).
60 /// (3) A list of successors and predecessors.
62 /// Terminator: The terminator represents the type of control-flow that occurs
63 /// at the end of the basic block. The terminator is a Stmt* referring to an
64 /// AST node that has control-flow: if-statements, breaks, loops, etc.
65 /// If the control-flow is conditional, the condition expression will appear
66 /// within the set of statements in the block (usually the last statement).
68 /// Predecessors: the order in the set of predecessors is arbitrary.
70 /// Successors: the order in the set of successors is NOT arbitrary. We
71 /// currently have the following orderings based on the terminator:
73 /// Terminator Successor Ordering
74 /// -----------------------------------------------------
75 /// if Then Block; Else Block
76 /// ? operator LHS expression; RHS expression
77 /// &&, || expression that uses result of && or ||, RHS
81 typedef BumpVector<CFGElement> ImplTy;
84 StatementList(BumpVectorContext &C) : Impl(C, 4) {}
86 typedef std::reverse_iterator<ImplTy::iterator> iterator;
87 typedef std::reverse_iterator<ImplTy::const_iterator> const_iterator;
88 typedef ImplTy::iterator reverse_iterator;
89 typedef ImplTy::const_iterator const_reverse_iterator;
91 void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
92 CFGElement front() const { return Impl.back(); }
93 CFGElement back() const { return Impl.front(); }
95 iterator begin() { return Impl.rbegin(); }
96 iterator end() { return Impl.rend(); }
97 const_iterator begin() const { return Impl.rbegin(); }
98 const_iterator end() const { return Impl.rend(); }
99 reverse_iterator rbegin() { return Impl.begin(); }
100 reverse_iterator rend() { return Impl.end(); }
101 const_reverse_iterator rbegin() const { return Impl.begin(); }
102 const_reverse_iterator rend() const { return Impl.end(); }
104 CFGElement operator[](size_t i) const {
105 assert(i < Impl.size());
106 return Impl[Impl.size() - 1 - i];
109 size_t size() const { return Impl.size(); }
110 bool empty() const { return Impl.empty(); }
113 /// Stmts - The set of statements in the basic block.
116 /// Label - An (optional) label that prefixes the executable
117 /// statements in the block. When this variable is non-NULL, it is
118 /// either an instance of LabelStmt, SwitchCase or CXXCatchStmt.
121 /// Terminator - The terminator for a basic block that
122 /// indicates the type of control-flow that occurs between a block
123 /// and its successors.
126 /// LoopTarget - Some blocks are used to represent the "loop edge" to
127 /// the start of a loop from within the loop body. This Stmt* will be
128 /// refer to the loop statement for such blocks (and be null otherwise).
129 const Stmt *LoopTarget;
131 /// BlockID - A numerical ID assigned to a CFGBlock during construction
135 /// Predecessors/Successors - Keep track of the predecessor / successor
137 typedef BumpVector<CFGBlock*> AdjacentBlocks;
138 AdjacentBlocks Preds;
139 AdjacentBlocks Succs;
142 explicit CFGBlock(unsigned blockid, BumpVectorContext &C)
143 : Stmts(C), Label(NULL), Terminator(NULL), LoopTarget(NULL),
144 BlockID(blockid), Preds(C, 1), Succs(C, 1) {}
147 // Statement iterators
148 typedef StatementList::iterator iterator;
149 typedef StatementList::const_iterator const_iterator;
150 typedef StatementList::reverse_iterator reverse_iterator;
151 typedef StatementList::const_reverse_iterator const_reverse_iterator;
153 CFGElement front() const { return Stmts.front(); }
154 CFGElement back() const { return Stmts.back(); }
156 iterator begin() { return Stmts.begin(); }
157 iterator end() { return Stmts.end(); }
158 const_iterator begin() const { return Stmts.begin(); }
159 const_iterator end() const { return Stmts.end(); }
161 reverse_iterator rbegin() { return Stmts.rbegin(); }
162 reverse_iterator rend() { return Stmts.rend(); }
163 const_reverse_iterator rbegin() const { return Stmts.rbegin(); }
164 const_reverse_iterator rend() const { return Stmts.rend(); }
166 unsigned size() const { return Stmts.size(); }
167 bool empty() const { return Stmts.empty(); }
169 CFGElement operator[](size_t i) const { return Stmts[i]; }
172 typedef AdjacentBlocks::iterator pred_iterator;
173 typedef AdjacentBlocks::const_iterator const_pred_iterator;
174 typedef AdjacentBlocks::reverse_iterator pred_reverse_iterator;
175 typedef AdjacentBlocks::const_reverse_iterator const_pred_reverse_iterator;
177 typedef AdjacentBlocks::iterator succ_iterator;
178 typedef AdjacentBlocks::const_iterator const_succ_iterator;
179 typedef AdjacentBlocks::reverse_iterator succ_reverse_iterator;
180 typedef AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator;
182 pred_iterator pred_begin() { return Preds.begin(); }
183 pred_iterator pred_end() { return Preds.end(); }
184 const_pred_iterator pred_begin() const { return Preds.begin(); }
185 const_pred_iterator pred_end() const { return Preds.end(); }
187 pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); }
188 pred_reverse_iterator pred_rend() { return Preds.rend(); }
189 const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); }
190 const_pred_reverse_iterator pred_rend() const { return Preds.rend(); }
192 succ_iterator succ_begin() { return Succs.begin(); }
193 succ_iterator succ_end() { return Succs.end(); }
194 const_succ_iterator succ_begin() const { return Succs.begin(); }
195 const_succ_iterator succ_end() const { return Succs.end(); }
197 succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); }
198 succ_reverse_iterator succ_rend() { return Succs.rend(); }
199 const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); }
200 const_succ_reverse_iterator succ_rend() const { return Succs.rend(); }
202 unsigned succ_size() const { return Succs.size(); }
203 bool succ_empty() const { return Succs.empty(); }
205 unsigned pred_size() const { return Preds.size(); }
206 bool pred_empty() const { return Preds.empty(); }
209 class FilterOptions {
212 IgnoreDefaultsWithCoveredEnums = 0;
215 unsigned IgnoreDefaultsWithCoveredEnums : 1;
218 static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
219 const CFGBlock *Dst);
221 template <typename IMPL, bool IsPred>
222 class FilteredCFGBlockIterator {
225 const FilterOptions F;
226 const CFGBlock *From;
228 explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
229 const CFGBlock *from,
230 const FilterOptions &f)
231 : I(i), E(e), F(f), From(from) {}
233 bool hasMore() const { return I != E; }
235 FilteredCFGBlockIterator &operator++() {
236 do { ++I; } while (hasMore() && Filter(*I));
240 const CFGBlock *operator*() const { return *I; }
242 bool Filter(const CFGBlock *To) {
243 return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
247 typedef FilteredCFGBlockIterator<const_pred_iterator, true>
248 filtered_pred_iterator;
250 typedef FilteredCFGBlockIterator<const_succ_iterator, false>
251 filtered_succ_iterator;
253 filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
254 return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
257 filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
258 return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
261 // Manipulation of block contents
263 void setTerminator(Stmt* Statement) { Terminator = Statement; }
264 void setLabel(Stmt* Statement) { Label = Statement; }
265 void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
267 Stmt* getTerminator() { return Terminator; }
268 const Stmt* getTerminator() const { return Terminator; }
270 Stmt* getTerminatorCondition();
272 const Stmt* getTerminatorCondition() const {
273 return const_cast<CFGBlock*>(this)->getTerminatorCondition();
276 const Stmt *getLoopTarget() const { return LoopTarget; }
278 bool hasBinaryBranchTerminator() const;
280 Stmt* getLabel() { return Label; }
281 const Stmt* getLabel() const { return Label; }
283 unsigned getBlockID() const { return BlockID; }
285 void dump(const CFG *cfg, const LangOptions &LO) const;
286 void print(llvm::raw_ostream &OS, const CFG* cfg, const LangOptions &LO) const;
287 void printTerminator(llvm::raw_ostream &OS, const LangOptions &LO) const;
289 void addSuccessor(CFGBlock* Block, BumpVectorContext &C) {
291 Block->Preds.push_back(this, C);
292 Succs.push_back(Block, C);
295 void appendStmt(Stmt* Statement, BumpVectorContext &C, bool asLValue) {
296 Stmts.push_back(CFGElement(Statement, asLValue), C);
298 void StartScope(Stmt* S, BumpVectorContext &C) {
299 Stmts.push_back(CFGElement(S, CFGElement::StartScope), C);
301 void EndScope(Stmt* S, BumpVectorContext &C) {
302 Stmts.push_back(CFGElement(S, CFGElement::EndScope), C);
307 /// CFG - Represents a source-level, intra-procedural CFG that represents the
308 /// control-flow of a Stmt. The Stmt can represent an entire function body,
309 /// or a single expression. A CFG will always contain one empty block that
310 /// represents the Exit point of the CFG. A CFG will also contain a designated
311 /// Entry block. The CFG solely represents control-flow; it consists of
312 /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
313 /// was constructed from.
316 //===--------------------------------------------------------------------===//
317 // CFG Construction & Manipulation.
318 //===--------------------------------------------------------------------===//
320 /// buildCFG - Builds a CFG from an AST. The responsibility to free the
321 /// constructed CFG belongs to the caller.
322 static CFG* buildCFG(const Decl *D, Stmt* AST, ASTContext *C,
323 bool pruneTriviallyFalseEdges = true,
324 bool AddEHEdges = false,
325 bool AddScopes = false /* NOT FULLY IMPLEMENTED.
326 NOT READY FOR GENERAL USE. */);
328 /// createBlock - Create a new block in the CFG. The CFG owns the block;
329 /// the caller should not directly free it.
330 CFGBlock* createBlock();
332 /// setEntry - Set the entry block of the CFG. This is typically used
333 /// only during CFG construction. Most CFG clients expect that the
334 /// entry block has no predecessors and contains no statements.
335 void setEntry(CFGBlock *B) { Entry = B; }
337 /// setIndirectGotoBlock - Set the block used for indirect goto jumps.
338 /// This is typically used only during CFG construction.
339 void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; }
341 //===--------------------------------------------------------------------===//
343 //===--------------------------------------------------------------------===//
345 typedef BumpVector<CFGBlock*> CFGBlockListTy;
346 typedef CFGBlockListTy::iterator iterator;
347 typedef CFGBlockListTy::const_iterator const_iterator;
348 typedef std::reverse_iterator<iterator> reverse_iterator;
349 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
351 CFGBlock& front() { return *Blocks.front(); }
352 CFGBlock& back() { return *Blocks.back(); }
354 iterator begin() { return Blocks.begin(); }
355 iterator end() { return Blocks.end(); }
356 const_iterator begin() const { return Blocks.begin(); }
357 const_iterator end() const { return Blocks.end(); }
359 reverse_iterator rbegin() { return Blocks.rbegin(); }
360 reverse_iterator rend() { return Blocks.rend(); }
361 const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
362 const_reverse_iterator rend() const { return Blocks.rend(); }
364 CFGBlock& getEntry() { return *Entry; }
365 const CFGBlock& getEntry() const { return *Entry; }
366 CFGBlock& getExit() { return *Exit; }
367 const CFGBlock& getExit() const { return *Exit; }
369 CFGBlock* getIndirectGotoBlock() { return IndirectGotoBlock; }
370 const CFGBlock* getIndirectGotoBlock() const { return IndirectGotoBlock; }
372 //===--------------------------------------------------------------------===//
373 // Member templates useful for various batch operations over CFGs.
374 //===--------------------------------------------------------------------===//
376 template <typename CALLBACK>
377 void VisitBlockStmts(CALLBACK& O) const {
378 for (const_iterator I=begin(), E=end(); I != E; ++I)
379 for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
384 //===--------------------------------------------------------------------===//
385 // CFG Introspection.
386 //===--------------------------------------------------------------------===//
388 struct BlkExprNumTy {
390 explicit BlkExprNumTy(signed idx) : Idx(idx) {}
391 explicit BlkExprNumTy() : Idx(-1) {}
392 operator bool() const { return Idx >= 0; }
393 operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; }
396 bool isBlkExpr(const Stmt* S) { return getBlkExprNum(S); }
397 BlkExprNumTy getBlkExprNum(const Stmt* S);
398 unsigned getNumBlkExprs();
400 /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which
402 unsigned getNumBlockIDs() const { return NumBlockIDs; }
404 //===--------------------------------------------------------------------===//
405 // CFG Debugging: Pretty-Printing and Visualization.
406 //===--------------------------------------------------------------------===//
408 void viewCFG(const LangOptions &LO) const;
409 void print(llvm::raw_ostream& OS, const LangOptions &LO) const;
410 void dump(const LangOptions &LO) const;
412 //===--------------------------------------------------------------------===//
413 // Internal: constructors and data.
414 //===--------------------------------------------------------------------===//
416 CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0),
417 BlkExprMap(NULL), Blocks(BlkBVC, 10) {}
421 llvm::BumpPtrAllocator& getAllocator() {
422 return BlkBVC.getAllocator();
425 BumpVectorContext &getBumpVectorContext() {
432 CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch
433 // for indirect gotos
434 unsigned NumBlockIDs;
436 // BlkExprMap - An opaque pointer to prevent inclusion of DenseMap.h.
437 // It represents a map from Expr* to integers to record the set of
438 // block-level expressions and their "statement number" in the CFG.
441 BumpVectorContext BlkBVC;
443 CFGBlockListTy Blocks;
446 } // end namespace clang
448 //===----------------------------------------------------------------------===//
449 // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
450 //===----------------------------------------------------------------------===//
454 /// Implement simplify_type for CFGElement, so that we can dyn_cast from
455 /// CFGElement to a specific Stmt class.
456 template <> struct simplify_type<const ::clang::CFGElement> {
457 typedef ::clang::Stmt* SimpleType;
458 static SimpleType getSimplifiedValue(const ::clang::CFGElement &Val) {
459 return Val.getStmt();
463 template <> struct simplify_type< ::clang::CFGElement>
464 : public simplify_type<const ::clang::CFGElement> {};
466 // Traits for: CFGBlock
468 template <> struct GraphTraits< ::clang::CFGBlock* > {
469 typedef ::clang::CFGBlock NodeType;
470 typedef ::clang::CFGBlock::succ_iterator ChildIteratorType;
472 static NodeType* getEntryNode(::clang::CFGBlock* BB)
475 static inline ChildIteratorType child_begin(NodeType* N)
476 { return N->succ_begin(); }
478 static inline ChildIteratorType child_end(NodeType* N)
479 { return N->succ_end(); }
482 template <> struct GraphTraits< const ::clang::CFGBlock* > {
483 typedef const ::clang::CFGBlock NodeType;
484 typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType;
486 static NodeType* getEntryNode(const clang::CFGBlock* BB)
489 static inline ChildIteratorType child_begin(NodeType* N)
490 { return N->succ_begin(); }
492 static inline ChildIteratorType child_end(NodeType* N)
493 { return N->succ_end(); }
496 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
497 typedef const ::clang::CFGBlock NodeType;
498 typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
500 static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G)
503 static inline ChildIteratorType child_begin(NodeType* N)
504 { return N->pred_begin(); }
506 static inline ChildIteratorType child_end(NodeType* N)
507 { return N->pred_end(); }
512 template <> struct GraphTraits< ::clang::CFG* >
513 : public GraphTraits< ::clang::CFGBlock* > {
515 typedef ::clang::CFG::iterator nodes_iterator;
517 static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
518 static nodes_iterator nodes_begin(::clang::CFG* F) { return F->begin(); }
519 static nodes_iterator nodes_end(::clang::CFG* F) { return F->end(); }
522 template <> struct GraphTraits<const ::clang::CFG* >
523 : public GraphTraits<const ::clang::CFGBlock* > {
525 typedef ::clang::CFG::const_iterator nodes_iterator;
527 static NodeType *getEntryNode( const ::clang::CFG* F) {
528 return &F->getEntry();
530 static nodes_iterator nodes_begin( const ::clang::CFG* F) {
533 static nodes_iterator nodes_end( const ::clang::CFG* F) {
538 template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
539 : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
541 typedef ::clang::CFG::const_iterator nodes_iterator;
543 static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
544 static nodes_iterator nodes_begin(const ::clang::CFG* F) { return F->begin();}
545 static nodes_iterator nodes_end(const ::clang::CFG* F) { return F->end(); }
547 } // end llvm namespace