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