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