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