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