CFG.h revision ce1eb34bbea1e0408f1952776d7d52ccde1bd275
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" 19ce1eb34bbea1e0408f1952776d7d52ccde1bd275Ted Kremenek#include "llvm/Support/Allocator.h" 20fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek#include <list> 21fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek#include <vector> 22fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek#include <iosfwd> 23c1581a0d64b0ee4f822ed2fca4442a111d03569aHartmut Kaiser#include <cassert> 24fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 25fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremeneknamespace clang { 2642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek class Stmt; 2763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek class Expr; 2842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek class CFG; 2942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek class PrinterHelper; 3083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek class BlockEdge; 31fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 32fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFGBlock - Represents a single basic block in a source-level CFG. 33fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// It consists of: 34fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 35fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// (1) A set of statements/expressions (which may contain subexpressions). 36fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// (2) A "terminator" statement (not in the set of statements). 37fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// (3) A list of successors and predecessors. 38fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 39fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Terminator: The terminator represents the type of control-flow that occurs 40fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// at the end of the basic block. The terminator is a Stmt* referring to an 41fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// AST node that has control-flow: if-statements, breaks, loops, etc. 42fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// If the control-flow is conditional, the condition expression will appear 43fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// within the set of statements in the block (usually the last statement). 44fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 45fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Predecessors: the order in the set of predecessors is arbitrary. 46fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 47fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Successors: the order in the set of successors is NOT arbitrary. We 48fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// currently have the following orderings based on the terminator: 49fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 50fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Terminator Successor Ordering 51fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// ----------------------------------------------------- 52fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// if Then Block; Else Block 539cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek/// ? operator LHS expression; RHS expression 549cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek/// &&, || expression that uses result of && or ||, RHS 55fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 56fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekclass CFGBlock { 57fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::vector<Stmt*> StatementListTy; 58fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// Stmts - The set of statements in the basic block. 59fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek StatementListTy Stmts; 609cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 619cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// Label - An (optional) label that prefixes the executable 629cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// statements in the block. When this variable is non-NULL, it is 639cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// either an instance of LabelStmt or SwitchCase. 649cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek Stmt* Label; 659cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 669cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek /// Terminator - The terminator for a basic block that 67fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// indicates the type of control-flow that occurs between a block 68fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// and its successors. 699cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek Stmt* Terminator; 709cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek 71fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// BlockID - A numerical ID assigned to a CFGBlock during construction 72fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// of the CFG. 73fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned BlockID; 74fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 75fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// Predecessors/Successors - Keep track of the predecessor / successor 76fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek /// CFG blocks. 77fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::vector<CFGBlock*> AdjacentBlocks; 78fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek AdjacentBlocks Preds; 79fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek AdjacentBlocks Succs; 80fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 81fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekpublic: 829cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek explicit CFGBlock(unsigned blockid) : Label(NULL), Terminator(NULL), 83fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek BlockID(blockid) {} 84fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek ~CFGBlock() {}; 85fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 86fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Statement iterators 87fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef StatementListTy::iterator iterator; 88fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef StatementListTy::const_iterator const_iterator; 89fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 90fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 91fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 925156ad8b2e64850a13d4e9d9ddeb3f9c6b9d3ebbTed Kremenek Stmt* front() const { return Stmts.front(); } 935156ad8b2e64850a13d4e9d9ddeb3f9c6b9d3ebbTed Kremenek Stmt* back() const { return Stmts.back(); } 94fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 95fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek iterator begin() { return Stmts.begin(); } 96fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek iterator end() { return Stmts.end(); } 97fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_iterator begin() const { return Stmts.begin(); } 98fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_iterator end() const { return Stmts.end(); } 99fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 100fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek reverse_iterator rbegin() { return Stmts.rbegin(); } 101fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek reverse_iterator rend() { return Stmts.rend(); } 102fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_reverse_iterator rbegin() const { return Stmts.rbegin(); } 103fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek const_reverse_iterator rend() const { return Stmts.rend(); } 104fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 105fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned size() const { return Stmts.size(); } 106fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek bool empty() const { return Stmts.empty(); } 107be7a7d6f2e5b86807afd08a568863df973baaa38Ted Kremenek 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 156411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek Expr* getTerminatorCondition(); 157411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 158411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek const Expr* getTerminatorCondition() const { 159411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return const_cast<CFGBlock*>(this)->getTerminatorCondition(); 160411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 161411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 1629c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek bool hasBinaryBranchTerminator() const; 1639c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek 1649cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek Stmt* getLabel() { return Label; } 1659cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek const Stmt* getLabel() const { return Label; } 1660cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek 167fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek void reverseStmts(); 168fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 169fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek void addSuccessor(CFGBlock* Block) { 170fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek Block->Preds.push_back(this); 171fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek Succs.push_back(Block); 172fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 173fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 174fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned getBlockID() const { return BlockID; } 175fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 1767dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void dump(const CFG* cfg) const; 17742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void print(std::ostream& OS, const CFG* cfg) const; 178a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek void printTerminator(std::ostream& OS) const; 179fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek}; 180fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 181fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 182fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFG - Represents a source-level, intra-procedural CFG that represents the 183fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// control-flow of a Stmt. The Stmt can represent an entire function body, 184fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// or a single expression. A CFG will always contain one empty block that 185fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// represents the Exit point of the CFG. A CFG will also contain a designated 186fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Entry block. The CFG solely represents control-flow; it consists of 187fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG 188fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// was constructed from. 189fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekclass CFG { 190fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekpublic: 191a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 192a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // CFG Construction & Manipulation. 193a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 194a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 195a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// buildCFG - Builds a CFG from an AST. The responsibility to free the 196a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// constructed CFG belongs to the caller. 197a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek static CFG* buildCFG(Stmt* AST); 198a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 199a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// createBlock - Create a new block in the CFG. The CFG owns the block; 200a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// the caller should not directly free it. 201a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* createBlock(); 202fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 203a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// setEntry - Set the entry block of the CFG. This is typically used 204a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// only during CFG construction. Most CFG clients expect that the 205a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// entry block has no predecessors and contains no statements. 206a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek void setEntry(CFGBlock *B) { Entry = B; } 207a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 208a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// setExit - Set the exit block of the CFG. This is typically used 209a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// only during CFG construction. Most CFG clients expect that the 210a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek /// exit block has no successors and contains no statements. 211a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; } 212a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 213a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 214a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // Block Iterators 215a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 216a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 217a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef std::list<CFGBlock> CFGBlockListTy; 218a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 219a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef CFGBlockListTy::iterator iterator; 220a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef CFGBlockListTy::const_iterator const_iterator; 221a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef std::reverse_iterator<iterator> reverse_iterator; 222a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 223fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 22419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& front() { return Blocks.front(); } 22519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& back() { return Blocks.back(); } 226fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 22719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek iterator begin() { return Blocks.begin(); } 22819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek iterator end() { return Blocks.end(); } 22919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_iterator begin() const { return Blocks.begin(); } 23019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_iterator end() const { return Blocks.end(); } 231fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 23219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek reverse_iterator rbegin() { return Blocks.rbegin(); } 23319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek reverse_iterator rend() { return Blocks.rend(); } 23419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_reverse_iterator rbegin() const { return Blocks.rbegin(); } 23519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek const_reverse_iterator rend() const { return Blocks.rend(); } 236fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 23719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& getEntry() { return *Entry; } 2387dba8607e59096014b7139ff20ef00870041d518Ted Kremenek const CFGBlock& getEntry() const { return *Entry; } 23919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock& getExit() { return *Exit; } 2407dba8607e59096014b7139ff20ef00870041d518Ted Kremenek const CFGBlock& getExit() const { return *Exit; } 2417dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 2427dba8607e59096014b7139ff20ef00870041d518Ted Kremenek CFGBlock* getIndirectGotoBlock() { return IndirectGotoBlock; } 2437dba8607e59096014b7139ff20ef00870041d518Ted Kremenek const CFGBlock* getIndirectGotoBlock() const { return IndirectGotoBlock; } 244fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 245a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 246a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek // Member templates useful for various batch operations over CFGs. 247a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek //===--------------------------------------------------------------------===// 248a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek 249a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek template <typename CALLBACK> 250a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek void VisitBlockStmts(CALLBACK& O) const { 251a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek for (const_iterator I=begin(), E=end(); I != E; ++I) 252a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek for (CFGBlock::const_iterator BI=I->begin(), BE=I->end(); BI != BE; ++BI) 253a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek O(*BI); 254a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek } 255a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek 256a90b0d1e585d993621a342d0b2874e61941372d5Ted Kremenek //===--------------------------------------------------------------------===// 257a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // CFG Introspection. 258a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 259a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 26063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek struct BlkExprNumTy { 26163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek const signed Idx; 26263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek explicit BlkExprNumTy(signed idx) : Idx(idx) {} 26363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek explicit BlkExprNumTy() : Idx(-1) {} 26463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek operator bool() const { return Idx >= 0; } 26563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; } 26663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek }; 26763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 26886946745225096243f6969dc745267b78fc211a6Ted Kremenek bool isBlkExpr(const Stmt* S) { return getBlkExprNum(S); } 26986946745225096243f6969dc745267b78fc211a6Ted Kremenek BlkExprNumTy getBlkExprNum(const Stmt* S); 27063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek unsigned getNumBlkExprs(); 27163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 2729438252ad2ecae5338df565ca33c6969e4fbfa41Ted Kremenek unsigned getNumBlockIDs() const { return NumBlockIDs; } 273a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 274a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 275a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // CFG Debugging: Pretty-Printing and Visualization. 276a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 277a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 2787dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void viewCFG() const; 2797dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void print(std::ostream& OS) const; 2807dba8607e59096014b7139ff20ef00870041d518Ted Kremenek void dump() const; 281a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 282a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 283a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // Internal: constructors and data. 284a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek //===--------------------------------------------------------------------===// 285a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 28663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0), 287ce1eb34bbea1e0408f1952776d7d52ccde1bd275Ted Kremenek BlkExprMap(NULL), BlkEdgeSet(NULL) {}; 28863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 28963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek ~CFG(); 290ce1eb34bbea1e0408f1952776d7d52ccde1bd275Ted Kremenek 291ce1eb34bbea1e0408f1952776d7d52ccde1bd275Ted Kremenek llvm::BumpPtrAllocator& getAllocator() { 292ce1eb34bbea1e0408f1952776d7d52ccde1bd275Ted Kremenek return Alloc; 293ce1eb34bbea1e0408f1952776d7d52ccde1bd275Ted Kremenek } 294a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek 295a36c6540346266f570b2fc7457950dea45d89988Ted Kremenekprivate: 296a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* Entry; 297a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* Exit; 298a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch 299a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek // for indirect gotos 300a36c6540346266f570b2fc7457950dea45d89988Ted Kremenek CFGBlockListTy Blocks; 30163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek unsigned NumBlockIDs; 30286d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek 30386d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek // BlkExprMap - An opaque pointer to prevent inclusion of DenseMap.h. 30486d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek // It represents a map from Expr* to integers to record the set of 30586d1777a6b7723865c1e67a7aafc797ec0a574ffTed Kremenek // block-level expressions and their "statement number" in the CFG. 30663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek void* BlkExprMap; 30783c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 308274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek /// BlkEdgeSet - An opaque pointer to prevent inclusion of FoldingSet.h. 30995b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// The set contains std::pair<CFGBlock*,CFGBlock*> objects that have 31095b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// stable references for use by the 'BlockEdge' class. This set is intended 31195b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// to be sparse, as it only contains edges whether both the source 31295b1a9055ea7a27c231f6e082e5bcee4947ea0ceTed Kremenek /// and destination block have multiple successors/predecessors. 31383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek void* BlkEdgeSet; 31483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 315274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek /// Alloc - An internal allocator used for BlkEdgeSet. 316ce1eb34bbea1e0408f1952776d7d52ccde1bd275Ted Kremenek llvm::BumpPtrAllocator Alloc; 317274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek 31883c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek friend class BlockEdge; 31983c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 32083c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// getBlockEdgeImpl - Utility method used by the class BlockEdge. The CFG 32183c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// stores a set of interned std::pair<CFGBlock*,CFGBlock*> that can 32283c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// be used by BlockEdge to refer to edges that cannot be represented 32383c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek /// by a single pointer. 32483c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek const std::pair<CFGBlock*,CFGBlock*>* getBlockEdgeImpl(const CFGBlock* B1, 32583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek const CFGBlock* B2); 32683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 327fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek}; 328fa2be43dbd6fdc4414e261db69aaf35dfb21a416Ted Kremenek} // end namespace clang 3297dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3307dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 3317dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// GraphTraits specializations for CFG basic block graphs (source-level CFGs) 3327dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 3337dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3347dba8607e59096014b7139ff20ef00870041d518Ted Kremeneknamespace llvm { 3357dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3367dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// Traits for: CFGBlock 3377dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3387dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<clang::CFGBlock* > { 3397dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock NodeType; 3407dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock::succ_iterator ChildIteratorType; 3417dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3427dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType* getEntryNode(clang::CFGBlock* BB) 3437dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return BB; } 3447dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3457dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) 3467dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_begin(); } 3477dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3487dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) 3497dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_end(); } 3507dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3517dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3527dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<const clang::CFGBlock* > { 3537dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef const clang::CFGBlock NodeType; 3547dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock::const_succ_iterator ChildIteratorType; 3557dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3567dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType* getEntryNode(const clang::CFGBlock* BB) 3577dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return BB; } 3587dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3597dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) 3607dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_begin(); } 3617dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3627dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) 3637dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->succ_end(); } 3647dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3657dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3667dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<Inverse<const clang::CFGBlock*> > { 3677dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef const clang::CFGBlock NodeType; 3687dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFGBlock::const_pred_iterator ChildIteratorType; 3697dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3707dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode(Inverse<const clang::CFGBlock*> G) 3717dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return G.Graph; } 3727dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3737dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_begin(NodeType* N) 3747dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->pred_begin(); } 3757dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3767dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static inline ChildIteratorType child_end(NodeType* N) 3777dba8607e59096014b7139ff20ef00870041d518Ted Kremenek { return N->pred_end(); } 3787dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3797dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3807dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// Traits for: CFG 3817dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3827dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<clang::CFG* > 3837dba8607e59096014b7139ff20ef00870041d518Ted Kremenek : public GraphTraits<clang::CFGBlock* > { 3847dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3857dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFG::iterator nodes_iterator; 3867dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3877dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode(clang::CFG* F) { return &F->getEntry(); } 3887dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_begin(clang::CFG* F) { return F->begin(); } 3897dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_end(clang::CFG* F) { return F->end(); } 3907dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 3917dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3927dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits< const clang::CFG* > 3937dba8607e59096014b7139ff20ef00870041d518Ted Kremenek : public GraphTraits< const clang::CFGBlock* > { 3947dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3957dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFG::const_iterator nodes_iterator; 3967dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 3977dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode( const clang::CFG* F) { return &F->getEntry(); } 3987dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_begin( const clang::CFG* F) { return F->begin(); } 3997dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_end( const clang::CFG* F) { return F->end(); } 4007dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 4017dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 4027dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate <> struct GraphTraits<Inverse<const clang::CFG*> > 4037dba8607e59096014b7139ff20ef00870041d518Ted Kremenek : public GraphTraits<Inverse<const clang::CFGBlock*> > { 4047dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 4057dba8607e59096014b7139ff20ef00870041d518Ted Kremenek typedef clang::CFG::const_iterator nodes_iterator; 4067dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 4077dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static NodeType *getEntryNode(const clang::CFG* F) { return &F->getExit(); } 4087dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_begin(const clang::CFG* F) { return F->begin();} 4097dba8607e59096014b7139ff20ef00870041d518Ted Kremenek static nodes_iterator nodes_end(const clang::CFG* F) { return F->end(); } 4107dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 4117dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 4127dba8607e59096014b7139ff20ef00870041d518Ted Kremenek} // end llvm namespace 413cd881d534517f09a2fae10445f9b865f49ccc6c8Ted Kremenek 414cd881d534517f09a2fae10445f9b865f49ccc6c8Ted Kremenek#endif 415