CFG.h revision be7a7d6f2e5b86807afd08a568863df973baaa38
1fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===--- CFG.h - Classes for representing and building CFGs------*- C++ -*-===// 2fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 3fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// The LLVM Compiler Infrastructure 4fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 50bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// This file is distributed under the University of Illinois Open Source 60bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// License. See LICENSE.TXT for details. 7fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 8fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===----------------------------------------------------------------------===// 9fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 10fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// This file defines the CFG and CFGBuilder classes for representing and 11fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// building Control-Flow Graphs (CFGs) from ASTs. 12fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 13fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===----------------------------------------------------------------------===// 14fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 15cd881d534517f09a2fae10445f9b865f49ccc6c8Ted Kremenek#ifndef LLVM_CLANG_CFG_H 16cd881d534517f09a2fae10445f9b865f49ccc6c8Ted Kremenek#define LLVM_CLANG_CFG_H 17cd881d534517f09a2fae10445f9b865f49ccc6c8Ted Kremenek 187dba8607e59096014b7139ff20ef00870041d518Ted Kremenek#include "llvm/ADT/GraphTraits.h" 19fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek#include <list> 20fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek#include <vector> 21fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek#include <iosfwd> 22c1581a0d64b0ee4f822ed2fca4442a111d03569aHartmut Kaiser#include <cassert> 23fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 24fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremeneknamespace clang { 2542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek class Stmt; 2663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek class Expr; 2742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek class CFG; 2842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek class PrinterHelper; 2983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek class BlockEdge; 30fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 31fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFGBlock - Represents a single basic block in a source-level CFG. 32fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// It consists of: 33fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 34fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// (1) A set of statements/expressions (which may contain subexpressions). 35fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// (2) A "terminator" statement (not in the set of statements). 36fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// (3) A list of successors and predecessors. 37fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 38fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Terminator: The terminator represents the type of control-flow that occurs 39fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// at the end of the basic block. The terminator is a Stmt* referring to an 40fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// AST node that has control-flow: if-statements, breaks, loops, etc. 41fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// If the control-flow is conditional, the condition expression will appear 42fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// within the set of statements in the block (usually the last statement). 43fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 44fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Predecessors: the order in the set of predecessors is arbitrary. 45fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 46fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Successors: the order in the set of successors is NOT arbitrary. We 47fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// currently have the following orderings based on the terminator: 48fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 49fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Terminator Successor Ordering 50fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// ----------------------------------------------------- 51fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// if Then Block; Else Block 529cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek/// ? operator LHS expression; RHS expression 539cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek/// &&, || expression that uses result of && or ||, RHS 54fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 55fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekclass CFGBlock { 56fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::vector<Stmt*> StatementListTy; 57fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// Stmts - The set of statements in the basic block. 58fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek StatementListTy Stmts; 599cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 609cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// Label - An (optional) label that prefixes the executable 619cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// statements in the block. When this variable is non-NULL, it is 629cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// either an instance of LabelStmt or SwitchCase. 639cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek Stmt* Label; 649cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 659cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// Terminator - The terminator for a basic block that 66fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// indicates the type of control-flow that occurs between a block 67fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// and its successors. 689cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek Stmt* Terminator; 699cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 70fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// BlockID - A numerical ID assigned to a CFGBlock during construction 71fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// of the CFG. 72fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned BlockID; 73fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 74fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// Predecessors/Successors - Keep track of the predecessor / successor 75fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// CFG blocks. 76fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::vector<CFGBlock*> AdjacentBlocks; 77fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek AdjacentBlocks Preds; 78fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek AdjacentBlocks Succs; 79fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 80fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekpublic: 819cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek explicit CFGBlock(unsigned blockid) : Label(NULL), Terminator(NULL), 82fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek BlockID(blockid) {} 83fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek ~CFGBlock() {}; 84fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 85fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Statement iterators 86fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef StatementListTy::iterator iterator; 87fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef StatementListTy::const_iterator const_iterator; 88fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 89fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 90fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 915156ad8b2e64850a13d4e9d9ddeb3f9c6b9d3ebbTed Kremenek Stmt* front() const { return Stmts.front(); } 925156ad8b2e64850a13d4e9d9ddeb3f9c6b9d3ebbTed Kremenek Stmt* back() const { return Stmts.back(); } 93fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 94fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek iterator begin() { return Stmts.begin(); } 95fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek iterator end() { return Stmts.end(); } 96fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_iterator begin() const { return Stmts.begin(); } 97fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_iterator end() const { return Stmts.end(); } 98fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 99fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek reverse_iterator rbegin() { return Stmts.rbegin(); } 100fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek reverse_iterator rend() { return Stmts.rend(); } 101fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_reverse_iterator rbegin() const { return Stmts.rbegin(); } 102fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_reverse_iterator rend() const { return Stmts.rend(); } 103fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 104fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned size() const { return Stmts.size(); } 105fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek bool empty() const { return Stmts.empty(); } 106be7a7d6f2e5b86807afd08a568863df973baaa38Ted Kremenek 107be7a7d6f2e5b86807afd08a568863df973baaa38Ted Kremenek Stmt*& operator[](size_t i) { assert (i < size()); return Stmts[i]; } 108be7a7d6f2e5b86807afd08a568863df973baaa38Ted Kremenek Stmt* operator[](size_t i) const { assert (i < size()); return Stmts[i]; } 109be7a7d6f2e5b86807afd08a568863df973baaa38Ted Kremenek 110fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // CFG iterators 111fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::iterator pred_iterator; 112fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::const_iterator const_pred_iterator; 113fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::reverse_iterator pred_reverse_iterator; 114fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::const_reverse_iterator const_pred_reverse_iterator; 115fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 116fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::iterator succ_iterator; 117fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::const_iterator const_succ_iterator; 118fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::reverse_iterator succ_reverse_iterator; 119fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator; 120fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 121fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek pred_iterator pred_begin() { return Preds.begin(); } 122fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek pred_iterator pred_end() { return Preds.end(); } 123fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_pred_iterator pred_begin() const { return Preds.begin(); } 124fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_pred_iterator pred_end() const { return Preds.end(); } 125fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 126fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); } 127fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek pred_reverse_iterator pred_rend() { return Preds.rend(); } 128fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); } 129fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_pred_reverse_iterator pred_rend() const { return Preds.rend(); } 130fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 131fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek succ_iterator succ_begin() { return Succs.begin(); } 132fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek succ_iterator succ_end() { return Succs.end(); } 133fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_succ_iterator succ_begin() const { return Succs.begin(); } 134fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_succ_iterator succ_end() const { return Succs.end(); } 135fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 136fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); } 137fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek succ_reverse_iterator succ_rend() { return Succs.rend(); } 138fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); } 139fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_succ_reverse_iterator succ_rend() const { return Succs.rend(); } 140fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 141fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned succ_size() const { return Succs.size(); } 142fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek bool succ_empty() const { return Succs.empty(); } 143fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 144fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned pred_size() const { return Preds.size(); } 145fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek bool pred_empty() const { return Preds.empty(); } 146fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 147fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Manipulation of block contents 148fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 149fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek void appendStmt(Stmt* Statement) { Stmts.push_back(Statement); } 1509cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek void setTerminator(Stmt* Statement) { Terminator = Statement; } 1519cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek void setLabel(Stmt* Statement) { Label = Statement; } 1529cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 1539cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek Stmt* getTerminator() { return Terminator; } 1549cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek const Stmt* getTerminator() const { return Terminator; } 1559cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 1569cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek Stmt* getLabel() { return Label; } 1579cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek const Stmt* getLabel() const { return Label; } 1580cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek 159fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek void reverseStmts(); 160fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 161fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek void addSuccessor(CFGBlock* Block) { 162fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek Block->Preds.push_back(this); 163fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek Succs.push_back(Block); 164fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 165fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 166fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned getBlockID() const { return BlockID; } 167fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 1687dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void dump(const CFG* cfg) const; 16942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void print(std::ostream& OS, const CFG* cfg) const; 170fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek}; 171fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 172fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 173fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFG - Represents a source-level, intra-procedural CFG that represents the 174fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// control-flow of a Stmt. The Stmt can represent an entire function body, 175fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// or a single expression. A CFG will always contain one empty block that 176fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// represents the Exit point of the CFG. A CFG will also contain a designated 177fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Entry block. The CFG solely represents control-flow; it consists of 178fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG 179fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// was constructed from. 180fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekclass CFG { 181fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekpublic: 182a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 183a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // CFG Construction & Manipulation. 184a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 185a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 186a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// buildCFG - Builds a CFG from an AST. The responsibility to free the 187a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// constructed CFG belongs to the caller. 188a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek static CFG* buildCFG(Stmt* AST); 189a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 190a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// createBlock - Create a new block in the CFG. The CFG owns the block; 191a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// the caller should not directly free it. 192a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* createBlock(); 193fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 194a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// setEntry - Set the entry block of the CFG. This is typically used 195a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// only during CFG construction. Most CFG clients expect that the 196a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// entry block has no predecessors and contains no statements. 197a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek void setEntry(CFGBlock *B) { Entry = B; } 198a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 199a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// setExit - Set the exit block of the CFG. This is typically used 200a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// only during CFG construction. Most CFG clients expect that the 201a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// exit block has no successors and contains no statements. 202a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; } 203a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 204a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 205a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // Block Iterators 206a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 207a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 208a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef std::list<CFGBlock> CFGBlockListTy; 209a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 210a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef CFGBlockListTy::iterator iterator; 211a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef CFGBlockListTy::const_iterator const_iterator; 212a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 213a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 214fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 21519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& front() { return Blocks.front(); } 21619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& back() { return Blocks.back(); } 217fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 21819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek iterator begin() { return Blocks.begin(); } 21919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek iterator end() { return Blocks.end(); } 22019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_iterator begin() const { return Blocks.begin(); } 22119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_iterator end() const { return Blocks.end(); } 222fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 22319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek reverse_iterator rbegin() { return Blocks.rbegin(); } 22419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek reverse_iterator rend() { return Blocks.rend(); } 22519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_reverse_iterator rbegin() const { return Blocks.rbegin(); } 22619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_reverse_iterator rend() const { return Blocks.rend(); } 227fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 22819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& getEntry() { return *Entry; } 2297dba8607e59096014b7139ff20ef00870041d518Ted Kremenek const CFGBlock& getEntry() const { return *Entry; } 23019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& getExit() { return *Exit; } 2317dba8607e59096014b7139ff20ef00870041d518Ted Kremenek const CFGBlock& getExit() const { return *Exit; } 2327dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 2337dba8607e59096014b7139ff20ef00870041d518Ted Kremenek CFGBlock* getIndirectGotoBlock() { return IndirectGotoBlock; } 2347dba8607e59096014b7139ff20ef00870041d518Ted Kremenek const CFGBlock* getIndirectGotoBlock() const { return IndirectGotoBlock; } 235fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 236a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 237a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek // Member templates useful for various batch operations over CFGs. 238a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek //===--------------------------------------------------------------------===// 239a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek 240a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek template <typename CALLBACK> 241a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek void VisitBlockStmts(CALLBACK& O) const { 242a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek for (const_iterator I=begin(), E=end(); I != E; ++I) 243a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek for (CFGBlock::const_iterator BI=I->begin(), BE=I->end(); BI != BE; ++BI) 244a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek O(*BI); 245a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek } 246a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek 247a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek //===--------------------------------------------------------------------===// 248a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // CFG Introspection. 249a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 250a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 25163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek struct BlkExprNumTy { 25263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek const signed Idx; 25363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek explicit BlkExprNumTy(signed idx) : Idx(idx) {} 25463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek explicit BlkExprNumTy() : Idx(-1) {} 25563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek operator bool() const { return Idx >= 0; } 25663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; } 25763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek }; 25863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 25963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek bool isBlkExpr(const Stmt* S); 26063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek bool isBlkExpr(const Expr* E) { return getBlkExprNum(E); } 26163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprNumTy getBlkExprNum(const Expr* E); 26263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek unsigned getNumBlkExprs(); 26363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 2649438252ad2ecae5338df565ca33c6969e4fbfa41Ted Kremenek unsigned getNumBlockIDs() const { return NumBlockIDs; } 265a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 266a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 267a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // CFG Debugging: Pretty-Printing and Visualization. 268a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 269a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 2707dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void viewCFG() const; 2717dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void print(std::ostream& OS) const; 2727dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void dump() const; 273a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 274a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 275a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // Internal: constructors and data. 276a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 277a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 27863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0), 27983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek BlkExprMap(NULL), BlkEdgeSet(NULL) {}; 28063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 28163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek ~CFG(); 282a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 283a36c6540346266f570b2fc7457950dea45d89988Ted Kremenekprivate: 284a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* Entry; 285a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* Exit; 286a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch 287a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // for indirect gotos 288a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlockListTy Blocks; 28963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek unsigned NumBlockIDs; 29086d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek 29186d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek // BlkExprMap - An opaque pointer to prevent inclusion of DenseMap.h. 29286d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek // It represents a map from Expr* to integers to record the set of 29386d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek // block-level expressions and their "statement number" in the CFG. 29463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek void* BlkExprMap; 29583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 29695b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// BlkEdgeSet - An opaque pointer to prevent inclusion of <set>. 29795b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// The set contains std::pair<CFGBlock*,CFGBlock*> objects that have 29895b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// stable references for use by the 'BlockEdge' class. This set is intended 29995b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// to be sparse, as it only contains edges whether both the source 30095b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// and destination block have multiple successors/predecessors. 30183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek void* BlkEdgeSet; 30283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 30383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek friend class BlockEdge; 30483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 30583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// getBlockEdgeImpl - Utility method used by the class BlockEdge. The CFG 30683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// stores a set of interned std::pair<CFGBlock*,CFGBlock*> that can 30783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// be used by BlockEdge to refer to edges that cannot be represented 30883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// by a single pointer. 30983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek const std::pair<CFGBlock*,CFGBlock*>* getBlockEdgeImpl(const CFGBlock* B1, 31083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek const CFGBlock* B2); 31183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 312fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek}; 313fa2be43dbd6fdc4414e261db69aaf35dfb21a416Ted Kremenek} // end namespace clang 3147dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3157dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 3167dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// GraphTraits specializations for CFG basic block graphs (source-level CFGs) 3177dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 3187dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3197dba8607e59096014b7139ff20ef00870041d518Ted Kremeneknamespace llvm { 3207dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3217dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// Traits for: CFGBlock 3227dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3237dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<clang::CFGBlock* > { 3247dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock NodeType; 3257dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock::succ_iterator ChildIteratorType; 3267dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3277dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType* getEntryNode(clang::CFGBlock* BB) 3287dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return BB; } 3297dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3307dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) 3317dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_begin(); } 3327dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3337dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) 3347dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_end(); } 3357dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3367dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3377dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<const clang::CFGBlock* > { 3387dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef const clang::CFGBlock NodeType; 3397dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock::const_succ_iterator ChildIteratorType; 3407dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3417dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType* getEntryNode(const clang::CFGBlock* BB) 3427dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return BB; } 3437dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3447dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) 3457dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_begin(); } 3467dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3477dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) 3487dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_end(); } 3497dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3507dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3517dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<Inverse<const clang::CFGBlock*> > { 3527dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef const clang::CFGBlock NodeType; 3537dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock::const_pred_iterator ChildIteratorType; 3547dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3557dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode(Inverse<const clang::CFGBlock*> G) 3567dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return G.Graph; } 3577dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3587dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) 3597dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->pred_begin(); } 3607dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3617dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) 3627dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->pred_end(); } 3637dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3647dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3657dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// Traits for: CFG 3667dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3677dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<clang::CFG* > 3687dba8607e59096014b7139ff20ef00870041d518Ted Kremenek : public GraphTraits<clang::CFGBlock* > { 3697dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3707dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFG::iterator nodes_iterator; 3717dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3727dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode(clang::CFG* F) { return &F->getEntry(); } 3737dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_begin(clang::CFG* F) { return F->begin(); } 3747dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_end(clang::CFG* F) { return F->end(); } 3757dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3767dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3777dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits< const clang::CFG* > 3787dba8607e59096014b7139ff20ef00870041d518Ted Kremenek : public GraphTraits< const clang::CFGBlock* > { 3797dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3807dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFG::const_iterator nodes_iterator; 3817dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3827dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode( const clang::CFG* F) { return &F->getEntry(); } 3837dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_begin( const clang::CFG* F) { return F->begin(); } 3847dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_end( const clang::CFG* F) { return F->end(); } 3857dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3867dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3877dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<Inverse<const clang::CFG*> > 3887dba8607e59096014b7139ff20ef00870041d518Ted Kremenek : public GraphTraits<Inverse<const clang::CFGBlock*> > { 3897dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3907dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFG::const_iterator nodes_iterator; 3917dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3927dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode(const clang::CFG* F) { return &F->getExit(); } 3937dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_begin(const clang::CFG* F) { return F->begin();} 3947dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_end(const clang::CFG* F) { return F->end(); } 3957dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3967dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3977dba8607e59096014b7139ff20ef00870041d518Ted Kremenek} // end llvm namespace 398cd881d534517f09a2fae10445f9b865f49ccc6c8Ted Kremenek 399cd881d534517f09a2fae10445f9b865f49ccc6c8Ted Kremenek#endif 400