granicus.if.org Git - clang/blob - include/clang/Analysis/CFG.h

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