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