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 <list>
  21 #include <vector>
  22 #include <cassert>
  23
  24 namespace llvm {
  25   class raw_ostream;
  26 }
  27 namespace 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 ///
  59 class 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
 119 public:
 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.
 232 class CFG {
 233 public:
 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
 339 private:
 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
 361 namespace llvm {
 362
 363 // Traits for: CFGBlock
 364
 365 template <> 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
 379 template <> 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
 393 template <> 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
 409 template <> 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
 419 template <> 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
 429 template <> 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