CFG.h revision ba6f816d633e3b88c38c6896c2d78d19489650f2 
1//===--- CFG.h - Classes for representing and building CFGs------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines the CFG and CFGBuilder classes for representing and
11//  building Control-Flow Graphs (CFGs) from ASTs.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_CFG_H
16#define LLVM_CLANG_CFG_H
17
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"
24#include <cassert>
25
26namespace llvm {
27  class raw_ostream;
28}
29namespace clang {
30  class Decl;
31  class Stmt;
32  class Expr;
33  class CFG;
34  class PrinterHelper;
35  class LangOptions;
36  class ASTContext;
37
38/// CFGElement - Represents a top-level expression in a basic block.
39class CFGElement {
40  llvm::PointerIntPair<Stmt *, 2> Data;
41public:
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; }
53};
54
55/// CFGBlock - Represents a single basic block in a source-level CFG.
56///  It consists of:
57///
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.
61///
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).
67///
68/// Predecessors: the order in the set of predecessors is arbitrary.
69///
70/// Successors: the order in the set of successors is NOT arbitrary.  We
71///  currently have the following orderings based on the terminator:
72///
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
78///
79class CFGBlock {
80  class StatementList {
81    typedef BumpVector<CFGElement> ImplTy;
82    ImplTy Impl;
83  public:
84    StatementList(BumpVectorContext &C) : Impl(C, 4) {}
85
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;
90
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(); }
94
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(); }
103
104   CFGElement operator[](size_t i) const  {
105     assert(i < Impl.size());
106     return Impl[Impl.size() - 1 - i];
107   }
108
109    size_t size() const { return Impl.size(); }
110    bool empty() const { return Impl.empty(); }
111  };
112
113  /// Stmts - The set of statements in the basic block.
114  StatementList Stmts;
115
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.
119  Stmt *Label;
120
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.
124  Stmt *Terminator;
125
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;
130
131  /// BlockID - A numerical ID assigned to a CFGBlock during construction
132  ///   of the CFG.
133  unsigned BlockID;
134
135  /// Predecessors/Successors - Keep track of the predecessor / successor
136  /// CFG blocks.
137  typedef BumpVector<CFGBlock*> AdjacentBlocks;
138  AdjacentBlocks Preds;
139  AdjacentBlocks Succs;
140
141public:
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) {}
145  ~CFGBlock() {}
146
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;
152
153  CFGElement                   front()       const { return Stmts.front();   }
154  CFGElement                   back()        const { return Stmts.back();    }
155
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();     }
160
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();    }
165
166  unsigned                     size()        const { return Stmts.size();    }
167  bool                         empty()       const { return Stmts.empty();   }
168
169  CFGElement operator[](size_t i) const  { return Stmts[i]; }
170
171  // CFG iterators
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;
176
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;
181
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();     }
186
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();    }
191
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();     }
196
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();    }
201
202  unsigned                     succ_size()   const { return Succs.size();    }
203  bool                         succ_empty()  const { return Succs.empty();   }
204
205  unsigned                     pred_size()   const { return Preds.size();    }
206  bool                         pred_empty()  const { return Preds.empty();   }
207
208  // Manipulation of block contents
209
210  void setTerminator(Stmt* Statement) { Terminator = Statement; }
211  void setLabel(Stmt* Statement) { Label = Statement; }
212  void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
213
214  Stmt* getTerminator() { return Terminator; }
215  const Stmt* getTerminator() const { return Terminator; }
216
217  Stmt* getTerminatorCondition();
218
219  const Stmt* getTerminatorCondition() const {
220    return const_cast<CFGBlock*>(this)->getTerminatorCondition();
221  }
222
223  const Stmt *getLoopTarget() const { return LoopTarget; }
224
225  bool hasBinaryBranchTerminator() const;
226
227  Stmt* getLabel() { return Label; }
228  const Stmt* getLabel() const { return Label; }
229
230  unsigned getBlockID() const { return BlockID; }
231
232  void dump(const CFG *cfg, const LangOptions &LO) const;
233  void print(llvm::raw_ostream &OS, const CFG* cfg, const LangOptions &LO) const;
234  void printTerminator(llvm::raw_ostream &OS, const LangOptions &LO) const;
235
236  void addSuccessor(CFGBlock* Block, BumpVectorContext &C) {
237    if (Block)
238      Block->Preds.push_back(this, C);
239    Succs.push_back(Block, C);
240  }
241
242  void appendStmt(Stmt* Statement, BumpVectorContext &C, bool asLValue) {
243      Stmts.push_back(CFGElement(Statement, asLValue), C);
244  }
245  void StartScope(Stmt* S, BumpVectorContext &C) {
246    Stmts.push_back(CFGElement(S, CFGElement::StartScope), C);
247  }
248  void EndScope(Stmt* S, BumpVectorContext &C) {
249    Stmts.push_back(CFGElement(S, CFGElement::EndScope), C);
250  }
251};
252
253
254/// CFG - Represents a source-level, intra-procedural CFG that represents the
255///  control-flow of a Stmt.  The Stmt can represent an entire function body,
256///  or a single expression.  A CFG will always contain one empty block that
257///  represents the Exit point of the CFG.  A CFG will also contain a designated
258///  Entry block.  The CFG solely represents control-flow; it consists of
259///  CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
260///  was constructed from.
261class CFG {
262public:
263  //===--------------------------------------------------------------------===//
264  // CFG Construction & Manipulation.
265  //===--------------------------------------------------------------------===//
266
267  /// buildCFG - Builds a CFG from an AST.  The responsibility to free the
268  ///   constructed CFG belongs to the caller.
269  static CFG* buildCFG(const Decl *D, Stmt* AST, ASTContext *C,
270                       bool pruneTriviallyFalseEdges = true,
271                       bool AddEHEdges = false,
272                       bool AddScopes = false /* NOT FULLY IMPLEMENTED.
273                                                 NOT READY FOR GENERAL USE. */);
274
275  /// createBlock - Create a new block in the CFG.  The CFG owns the block;
276  ///  the caller should not directly free it.
277  CFGBlock* createBlock();
278
279  /// setEntry - Set the entry block of the CFG.  This is typically used
280  ///  only during CFG construction.  Most CFG clients expect that the
281  ///  entry block has no predecessors and contains no statements.
282  void setEntry(CFGBlock *B) { Entry = B; }
283
284  /// setIndirectGotoBlock - Set the block used for indirect goto jumps.
285  ///  This is typically used only during CFG construction.
286  void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; }
287
288  //===--------------------------------------------------------------------===//
289  // Block Iterators
290  //===--------------------------------------------------------------------===//
291
292  typedef BumpVector<CFGBlock*>                    CFGBlockListTy;
293  typedef CFGBlockListTy::iterator                 iterator;
294  typedef CFGBlockListTy::const_iterator           const_iterator;
295  typedef std::reverse_iterator<iterator>          reverse_iterator;
296  typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
297
298  CFGBlock&                 front()                { return *Blocks.front(); }
299  CFGBlock&                 back()                 { return *Blocks.back(); }
300
301  iterator                  begin()                { return Blocks.begin(); }
302  iterator                  end()                  { return Blocks.end(); }
303  const_iterator            begin()       const    { return Blocks.begin(); }
304  const_iterator            end()         const    { return Blocks.end(); }
305
306  reverse_iterator          rbegin()               { return Blocks.rbegin(); }
307  reverse_iterator          rend()                 { return Blocks.rend(); }
308  const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
309  const_reverse_iterator    rend()        const    { return Blocks.rend(); }
310
311  CFGBlock&                 getEntry()             { return *Entry; }
312  const CFGBlock&           getEntry()    const    { return *Entry; }
313  CFGBlock&                 getExit()              { return *Exit; }
314  const CFGBlock&           getExit()     const    { return *Exit; }
315
316  CFGBlock*        getIndirectGotoBlock() { return IndirectGotoBlock; }
317  const CFGBlock*  getIndirectGotoBlock() const { return IndirectGotoBlock; }
318
319  //===--------------------------------------------------------------------===//
320  // Member templates useful for various batch operations over CFGs.
321  //===--------------------------------------------------------------------===//
322
323  template <typename CALLBACK>
324  void VisitBlockStmts(CALLBACK& O) const {
325    for (const_iterator I=begin(), E=end(); I != E; ++I)
326      for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
327           BI != BE; ++BI)
328        O(*BI);
329  }
330
331  //===--------------------------------------------------------------------===//
332  // CFG Introspection.
333  //===--------------------------------------------------------------------===//
334
335  struct   BlkExprNumTy {
336    const signed Idx;
337    explicit BlkExprNumTy(signed idx) : Idx(idx) {}
338    explicit BlkExprNumTy() : Idx(-1) {}
339    operator bool() const { return Idx >= 0; }
340    operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; }
341  };
342
343  bool          isBlkExpr(const Stmt* S) { return getBlkExprNum(S); }
344  BlkExprNumTy  getBlkExprNum(const Stmt* S);
345  unsigned      getNumBlkExprs();
346
347  /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which
348  /// start at 0).
349  unsigned getNumBlockIDs() const { return NumBlockIDs; }
350
351  //===--------------------------------------------------------------------===//
352  // CFG Debugging: Pretty-Printing and Visualization.
353  //===--------------------------------------------------------------------===//
354
355  void viewCFG(const LangOptions &LO) const;
356  void print(llvm::raw_ostream& OS, const LangOptions &LO) const;
357  void dump(const LangOptions &LO) const;
358
359  //===--------------------------------------------------------------------===//
360  // Internal: constructors and data.
361  //===--------------------------------------------------------------------===//
362
363  CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0),
364          BlkExprMap(NULL), Blocks(BlkBVC, 10) {}
365
366  ~CFG();
367
368  llvm::BumpPtrAllocator& getAllocator() {
369    return BlkBVC.getAllocator();
370  }
371
372  BumpVectorContext &getBumpVectorContext() {
373    return BlkBVC;
374  }
375
376private:
377  CFGBlock* Entry;
378  CFGBlock* Exit;
379  CFGBlock* IndirectGotoBlock;  // Special block to contain collective dispatch
380                                // for indirect gotos
381  unsigned  NumBlockIDs;
382
383  // BlkExprMap - An opaque pointer to prevent inclusion of DenseMap.h.
384  //  It represents a map from Expr* to integers to record the set of
385  //  block-level expressions and their "statement number" in the CFG.
386  void*     BlkExprMap;
387
388  BumpVectorContext BlkBVC;
389
390  CFGBlockListTy Blocks;
391
392};
393} // end namespace clang
394
395//===----------------------------------------------------------------------===//
396// GraphTraits specializations for CFG basic block graphs (source-level CFGs)
397//===----------------------------------------------------------------------===//
398
399namespace llvm {
400
401/// Implement simplify_type for CFGElement, so that we can dyn_cast from
402/// CFGElement to a specific Stmt class.
403template <> struct simplify_type<const ::clang::CFGElement> {
404  typedef ::clang::Stmt* SimpleType;
405  static SimpleType getSimplifiedValue(const ::clang::CFGElement &Val) {
406    return Val.getStmt();
407  }
408};
409
410template <> struct simplify_type< ::clang::CFGElement>
411  : public simplify_type<const ::clang::CFGElement> {};
412
413// Traits for: CFGBlock
414
415template <> struct GraphTraits< ::clang::CFGBlock* > {
416  typedef ::clang::CFGBlock NodeType;
417  typedef ::clang::CFGBlock::succ_iterator ChildIteratorType;
418
419  static NodeType* getEntryNode(::clang::CFGBlock* BB)
420  { return BB; }
421
422  static inline ChildIteratorType child_begin(NodeType* N)
423  { return N->succ_begin(); }
424
425  static inline ChildIteratorType child_end(NodeType* N)
426  { return N->succ_end(); }
427};
428
429template <> struct GraphTraits< const ::clang::CFGBlock* > {
430  typedef const ::clang::CFGBlock NodeType;
431  typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType;
432
433  static NodeType* getEntryNode(const clang::CFGBlock* BB)
434  { return BB; }
435
436  static inline ChildIteratorType child_begin(NodeType* N)
437  { return N->succ_begin(); }
438
439  static inline ChildIteratorType child_end(NodeType* N)
440  { return N->succ_end(); }
441};
442
443template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
444  typedef const ::clang::CFGBlock NodeType;
445  typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
446
447  static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G)
448  { return G.Graph; }
449
450  static inline ChildIteratorType child_begin(NodeType* N)
451  { return N->pred_begin(); }
452
453  static inline ChildIteratorType child_end(NodeType* N)
454  { return N->pred_end(); }
455};
456
457// Traits for: CFG
458
459template <> struct GraphTraits< ::clang::CFG* >
460    : public GraphTraits< ::clang::CFGBlock* >  {
461
462  typedef ::clang::CFG::iterator nodes_iterator;
463
464  static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
465  static nodes_iterator nodes_begin(::clang::CFG* F) { return F->begin(); }
466  static nodes_iterator nodes_end(::clang::CFG* F) { return F->end(); }
467};
468
469template <> struct GraphTraits<const ::clang::CFG* >
470    : public GraphTraits<const ::clang::CFGBlock* >  {
471
472  typedef ::clang::CFG::const_iterator nodes_iterator;
473
474  static NodeType *getEntryNode( const ::clang::CFG* F) {
475    return &F->getEntry();
476  }
477  static nodes_iterator nodes_begin( const ::clang::CFG* F) {
478    return F->begin();
479  }
480  static nodes_iterator nodes_end( const ::clang::CFG* F) {
481    return F->end();
482  }
483};
484
485template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
486  : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
487
488  typedef ::clang::CFG::const_iterator nodes_iterator;
489
490  static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
491  static nodes_iterator nodes_begin(const ::clang::CFG* F) { return F->begin();}
492  static nodes_iterator nodes_end(const ::clang::CFG* F) { return F->end(); }
493};
494} // end llvm namespace
495#endif
496