CFG.h revision 63f5887f316fb52d243fcbb3631c039de6c4b993 
1//===--- CFG.h - Classes for representing and building CFGs------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Ted Kremenek and is distributed under
6// the University of Illinois Open Source 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/GraphTraits.h"
19#include <list>
20#include <vector>
21#include <iosfwd>
22
23namespace clang {
24
25  class Stmt;
26  class Expr;
27  class CFG;
28  class PrinterHelper;
29
30/// CFGBlock - Represents a single basic block in a source-level CFG.
31///  It consists of:
32///
33///  (1) A set of statements/expressions (which may contain subexpressions).
34///  (2) A "terminator" statement (not in the set of statements).
35///  (3) A list of successors and predecessors.
36///
37/// Terminator: The terminator represents the type of control-flow that occurs
38/// at the end of the basic block.  The terminator is a Stmt* referring to an
39/// AST node that has control-flow: if-statements, breaks, loops, etc.
40/// If the control-flow is conditional, the condition expression will appear
41/// within the set of statements in the block (usually the last statement).
42///
43/// Predecessors: the order in the set of predecessors is arbitrary.
44///
45/// Successors: the order in the set of successors is NOT arbitrary.  We
46///  currently have the following orderings based on the terminator:
47///
48///     Terminator       Successor Ordering
49///  -----------------------------------------------------
50///       if            Then Block;  Else Block
51///     ? operator      LHS expression;  RHS expression
52///     &&, ||          expression that uses result of && or ||, RHS
53///
54class CFGBlock {
55  typedef std::vector<Stmt*> StatementListTy;
56  /// Stmts - The set of statements in the basic block.
57  StatementListTy Stmts;
58
59  /// Label - An (optional) label that prefixes the executable
60  ///  statements in the block.  When this variable is non-NULL, it is
61  ///  either an instance of LabelStmt or SwitchCase.
62  Stmt* Label;
63
64  /// Terminator - The terminator for a basic block that
65  ///  indicates the type of control-flow that occurs between a block
66  ///  and its successors.
67  Stmt* Terminator;
68
69  /// BlockID - A numerical ID assigned to a CFGBlock during construction
70  ///   of the CFG.
71  unsigned BlockID;
72
73  /// Predecessors/Successors - Keep track of the predecessor / successor
74  /// CFG blocks.
75  typedef std::vector<CFGBlock*> AdjacentBlocks;
76  AdjacentBlocks Preds;
77  AdjacentBlocks Succs;
78
79public:
80  explicit CFGBlock(unsigned blockid) : Label(NULL), Terminator(NULL),
81                                        BlockID(blockid) {}
82  ~CFGBlock() {};
83
84  // Statement iterators
85  typedef StatementListTy::iterator                                  iterator;
86  typedef StatementListTy::const_iterator                      const_iterator;
87  typedef std::reverse_iterator<const_iterator>        const_reverse_iterator;
88  typedef std::reverse_iterator<iterator>                    reverse_iterator;
89
90  Stmt*                        front()             { return Stmts.front();   }
91  Stmt*                        back()              { return Stmts.back();    }
92
93  iterator                     begin()             { return Stmts.begin();   }
94  iterator                     end()               { return Stmts.end();     }
95  const_iterator               begin()       const { return Stmts.begin();   }
96  const_iterator               end()         const { return Stmts.end();     }
97
98  reverse_iterator             rbegin()            { return Stmts.rbegin();  }
99  reverse_iterator             rend()              { return Stmts.rend();    }
100  const_reverse_iterator       rbegin()      const { return Stmts.rbegin();  }
101  const_reverse_iterator       rend()        const { return Stmts.rend();    }
102
103  unsigned                     size()        const { return Stmts.size();    }
104  bool                         empty()       const { return Stmts.empty();   }
105
106  // CFG iterators
107  typedef AdjacentBlocks::iterator                              pred_iterator;
108  typedef AdjacentBlocks::const_iterator                  const_pred_iterator;
109  typedef AdjacentBlocks::reverse_iterator              pred_reverse_iterator;
110  typedef AdjacentBlocks::const_reverse_iterator  const_pred_reverse_iterator;
111
112  typedef AdjacentBlocks::iterator                              succ_iterator;
113  typedef AdjacentBlocks::const_iterator                  const_succ_iterator;
114  typedef AdjacentBlocks::reverse_iterator              succ_reverse_iterator;
115  typedef AdjacentBlocks::const_reverse_iterator  const_succ_reverse_iterator;
116
117  pred_iterator                pred_begin()        { return Preds.begin();   }
118  pred_iterator                pred_end()          { return Preds.end();     }
119  const_pred_iterator          pred_begin()  const { return Preds.begin();   }
120  const_pred_iterator          pred_end()    const { return Preds.end();     }
121
122  pred_reverse_iterator        pred_rbegin()       { return Preds.rbegin();  }
123  pred_reverse_iterator        pred_rend()         { return Preds.rend();    }
124  const_pred_reverse_iterator  pred_rbegin() const { return Preds.rbegin();  }
125  const_pred_reverse_iterator  pred_rend()   const { return Preds.rend();    }
126
127  succ_iterator                succ_begin()        { return Succs.begin();   }
128  succ_iterator                succ_end()          { return Succs.end();     }
129  const_succ_iterator          succ_begin()  const { return Succs.begin();   }
130  const_succ_iterator          succ_end()    const { return Succs.end();     }
131
132  succ_reverse_iterator        succ_rbegin()       { return Succs.rbegin();  }
133  succ_reverse_iterator        succ_rend()         { return Succs.rend();    }
134  const_succ_reverse_iterator  succ_rbegin() const { return Succs.rbegin();  }
135  const_succ_reverse_iterator  succ_rend()   const { return Succs.rend();    }
136
137  unsigned                     succ_size()   const { return Succs.size();    }
138  bool                         succ_empty()  const { return Succs.empty();   }
139
140  unsigned                     pred_size()   const { return Preds.size();    }
141  bool                         pred_empty()  const { return Preds.empty();   }
142
143  // Manipulation of block contents
144
145  void appendStmt(Stmt* Statement) { Stmts.push_back(Statement); }
146  void setTerminator(Stmt* Statement) { Terminator = Statement; }
147  void setLabel(Stmt* Statement) { Label = Statement; }
148
149  Stmt* getTerminator() { return Terminator; }
150  const Stmt* getTerminator() const { return Terminator; }
151
152  Stmt* getLabel() { return Label; }
153  const Stmt* getLabel() const { return Label; }
154
155  void reverseStmts();
156
157  void addSuccessor(CFGBlock* Block) {
158    Block->Preds.push_back(this);
159    Succs.push_back(Block);
160  }
161
162  unsigned getBlockID() const { return BlockID; }
163
164  void dump(const CFG* cfg) const;
165  void print(std::ostream& OS, const CFG* cfg) const;
166};
167
168
169/// CFG - Represents a source-level, intra-procedural CFG that represents the
170///  control-flow of a Stmt.  The Stmt can represent an entire function body,
171///  or a single expression.  A CFG will always contain one empty block that
172///  represents the Exit point of the CFG.  A CFG will also contain a designated
173///  Entry block.  The CFG solely represents control-flow; it consists of
174///  CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
175///  was constructed from.
176class CFG {
177public:
178  //===--------------------------------------------------------------------===//
179  // CFG Construction & Manipulation.
180  //===--------------------------------------------------------------------===//
181
182  /// buildCFG - Builds a CFG from an AST.  The responsibility to free the
183  ///   constructed CFG belongs to the caller.
184  static CFG* buildCFG(Stmt* AST);
185
186  /// createBlock - Create a new block in the CFG.  The CFG owns the block;
187  ///  the caller should not directly free it.
188  CFGBlock* createBlock();
189
190  /// setEntry - Set the entry block of the CFG.  This is typically used
191  ///  only during CFG construction.  Most CFG clients expect that the
192  ///  entry block has no predecessors and contains no statements.
193  void setEntry(CFGBlock *B) { Entry = B; }
194
195  /// setExit - Set the exit block of the CFG.  This is typically used
196  ///  only during CFG construction.  Most CFG clients expect that the
197  ///  exit block has no successors and contains no statements.
198  void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; }
199
200  //===--------------------------------------------------------------------===//
201  // Block Iterators
202  //===--------------------------------------------------------------------===//
203
204  typedef std::list<CFGBlock>                      CFGBlockListTy;
205
206  typedef CFGBlockListTy::iterator                 iterator;
207  typedef CFGBlockListTy::const_iterator           const_iterator;
208  typedef std::reverse_iterator<iterator>          reverse_iterator;
209  typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
210
211  CFGBlock&                 front()                { return Blocks.front(); }
212  CFGBlock&                 back()                 { return Blocks.back(); }
213
214  iterator                  begin()                { return Blocks.begin(); }
215  iterator                  end()                  { return Blocks.end(); }
216  const_iterator            begin()       const    { return Blocks.begin(); }
217  const_iterator            end()         const    { return Blocks.end(); }
218
219  reverse_iterator          rbegin()               { return Blocks.rbegin(); }
220  reverse_iterator          rend()                 { return Blocks.rend(); }
221  const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
222  const_reverse_iterator    rend()        const    { return Blocks.rend(); }
223
224  CFGBlock&                 getEntry()             { return *Entry; }
225  const CFGBlock&           getEntry()    const    { return *Entry; }
226  CFGBlock&                 getExit()              { return *Exit; }
227  const CFGBlock&           getExit()     const    { return *Exit; }
228
229  CFGBlock*        getIndirectGotoBlock() { return IndirectGotoBlock; }
230  const CFGBlock*  getIndirectGotoBlock() const { return IndirectGotoBlock; }
231
232  //===--------------------------------------------------------------------===//
233  // CFG Edges (Source Block, Destination Block)
234  //===--------------------------------------------------------------------===//
235
236  class Edge {
237    const CFGBlock* S;
238    const CFGBlock* D;
239  public:
240    Edge(const CFGBlock* src, const CFGBlock* dst) : S(src), D(dst) {}
241    Edge(const Edge& RHS) : S(RHS.S), D(RHS.D) {}
242
243    Edge& operator=(const Edge& RHS) { S = RHS.S; D = RHS.D; return *this; }
244
245    const CFGBlock* getSrc() const { return S; }
246    const CFGBlock* getDst() const { return D; }
247
248    bool operator==(const Edge& RHS) const { return S == RHS.S && D == RHS.D; }
249    bool operator!=(const Edge& RHS) const { return !(*this == RHS); }
250  };
251
252  //===--------------------------------------------------------------------===//
253  // Member templates useful for various batch operations over CFGs.
254  //===--------------------------------------------------------------------===//
255
256  template <typename CALLBACK>
257  void VisitBlockStmts(CALLBACK& O) const {
258    for (const_iterator I=begin(), E=end(); I != E; ++I)
259      for (CFGBlock::const_iterator BI=I->begin(), BE=I->end(); BI != BE; ++BI)
260        O(*BI);
261  }
262
263  //===--------------------------------------------------------------------===//
264  // CFG Introspection.
265  //===--------------------------------------------------------------------===//
266
267  struct   BlkExprNumTy {
268    const signed Idx;
269    explicit BlkExprNumTy(signed idx) : Idx(idx) {}
270    explicit BlkExprNumTy() : Idx(-1) {}
271    operator bool() const { return Idx >= 0; }
272    operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; }
273  };
274
275  bool          isBlkExpr(const Stmt* S);
276  bool          isBlkExpr(const Expr* E) { return getBlkExprNum(E); }
277  BlkExprNumTy  getBlkExprNum(const Expr* E);
278  unsigned      getNumBlkExprs();
279
280  unsigned getNumBlockIDs() const { return NumBlockIDs; }
281
282  //===--------------------------------------------------------------------===//
283  // CFG Debugging: Pretty-Printing and Visualization.
284  //===--------------------------------------------------------------------===//
285
286  void viewCFG() const;
287  void print(std::ostream& OS) const;
288  void dump() const;
289
290  //===--------------------------------------------------------------------===//
291  // Internal: constructors and data.
292  //===--------------------------------------------------------------------===//
293
294  CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0),
295          BlkExprMap(NULL) {};
296
297  ~CFG();
298
299private:
300  CFGBlock* Entry;
301  CFGBlock* Exit;
302  CFGBlock* IndirectGotoBlock;  // Special block to contain collective dispatch
303  // for indirect gotos
304  CFGBlockListTy Blocks;
305  unsigned  NumBlockIDs;
306  // opaque pointer to prevent inclusion of DenseMap.h.  Map from expressions
307  // to integers to record block-level expressions.
308  void*     BlkExprMap;
309};
310} // end namespace clang
311
312//===----------------------------------------------------------------------===//
313// GraphTraits specializations for CFG basic block graphs (source-level CFGs)
314//===----------------------------------------------------------------------===//
315
316namespace llvm {
317
318// Traits for: CFGBlock
319
320template <> struct GraphTraits<clang::CFGBlock* > {
321  typedef clang::CFGBlock NodeType;
322  typedef clang::CFGBlock::succ_iterator ChildIteratorType;
323
324  static NodeType* getEntryNode(clang::CFGBlock* BB)
325  { return BB; }
326
327  static inline ChildIteratorType child_begin(NodeType* N)
328  { return N->succ_begin(); }
329
330  static inline ChildIteratorType child_end(NodeType* N)
331  { return N->succ_end(); }
332};
333
334template <> struct GraphTraits<const clang::CFGBlock* > {
335  typedef const clang::CFGBlock NodeType;
336  typedef clang::CFGBlock::const_succ_iterator ChildIteratorType;
337
338  static NodeType* getEntryNode(const clang::CFGBlock* BB)
339  { return BB; }
340
341  static inline ChildIteratorType child_begin(NodeType* N)
342  { return N->succ_begin(); }
343
344  static inline ChildIteratorType child_end(NodeType* N)
345  { return N->succ_end(); }
346};
347
348template <> struct GraphTraits<Inverse<const clang::CFGBlock*> > {
349  typedef const clang::CFGBlock NodeType;
350  typedef clang::CFGBlock::const_pred_iterator ChildIteratorType;
351
352  static NodeType *getEntryNode(Inverse<const clang::CFGBlock*> G)
353  { return G.Graph; }
354
355  static inline ChildIteratorType child_begin(NodeType* N)
356  { return N->pred_begin(); }
357
358  static inline ChildIteratorType child_end(NodeType* N)
359  { return N->pred_end(); }
360};
361
362// Traits for: CFG
363
364template <> struct GraphTraits<clang::CFG* >
365            : public GraphTraits<clang::CFGBlock* >  {
366
367  typedef clang::CFG::iterator nodes_iterator;
368
369  static NodeType *getEntryNode(clang::CFG* F) { return &F->getEntry(); }
370  static nodes_iterator nodes_begin(clang::CFG* F) { return F->begin(); }
371  static nodes_iterator nodes_end(clang::CFG* F) { return F->end(); }
372};
373
374template <> struct GraphTraits< const clang::CFG* >
375            : public GraphTraits< const clang::CFGBlock* >  {
376
377  typedef clang::CFG::const_iterator nodes_iterator;
378
379  static NodeType *getEntryNode( const clang::CFG* F) { return &F->getEntry(); }
380  static nodes_iterator nodes_begin( const clang::CFG* F) { return F->begin(); }
381  static nodes_iterator nodes_end( const clang::CFG* F) { return F->end(); }
382};
383
384template <> struct GraphTraits<Inverse<const clang::CFG*> >
385            : public GraphTraits<Inverse<const clang::CFGBlock*> > {
386
387  typedef clang::CFG::const_iterator nodes_iterator;
388
389  static NodeType *getEntryNode(const clang::CFG* F) { return &F->getExit(); }
390  static nodes_iterator nodes_begin(const clang::CFG* F) { return F->begin();}
391  static nodes_iterator nodes_end(const clang::CFG* F) { return F->end(); }
392};
393
394} // end llvm namespace
395
396#endif
397