ExplodedGraph.h revision f6f5ef4aaa66b60270e84d1fe1292886369d2f38
1cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson//=-- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -*- C++ -*-------==// 2dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// 3dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// The LLVM Compiler Infrastructure 4dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// 5dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// This file is distributed under the University of Illinois Open Source 6dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// License. See LICENSE.TXT for details. 7dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// 8dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson//===----------------------------------------------------------------------===// 9dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// 10dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// This file defines the template classes ExplodedNode and ExplodedGraph, 11dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// which represent a path-sensitive, intra-procedural "exploded graph." 12dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson// 13dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson//===----------------------------------------------------------------------===// 14dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson 15dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#ifndef LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH 16dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#define LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH 17dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson 18dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "clang/Analysis/ProgramPoint.h" 19dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "llvm/ADT/SmallVector.h" 20dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "llvm/ADT/FoldingSet.h" 21dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "llvm/ADT/SmallPtrSet.h" 22dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "llvm/Support/Allocator.h" 23dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "llvm/ADT/OwningPtr.h" 24dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "llvm/ADT/GraphTraits.h" 25dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson#include "llvm/ADT/DepthFirstIterator.h" 26dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson 27dc8058c3370588bfcad49fadace1691da47d58cdAdam Jacksonnamespace clang { 28dc8058c3370588bfcad49fadace1691da47d58cdAdam Jackson 29dc8058c3370588bfcad49fadace1691da47d58cdAdam Jacksonclass GRCoreEngineImpl; 30cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass ExplodedNodeImpl; 31cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass GRStmtNodeBuilderImpl; 32cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass GRBranchNodeBuilderImpl; 33cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass GRIndirectGotoNodeBuilderImpl; 34cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass GRSwitchNodeBuilderImpl; 35cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass CFG; 36cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass ASTContext; 37cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass FunctionDecl; 38cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 39e8c7d7598fb48237508f566204c71ba8f74d544fChia-I Wu 40ed4a65c3cfdf88afba48860be34ce26f7c371869Ian Romanickclass ExplodedNodeImpl : public llvm::FoldingSetNode { 41df04ffbf025994abd59e26c8439e77bb340ef20bGeorge Sapountzisprotected: 42df04ffbf025994abd59e26c8439e77bb340ef20bGeorge Sapountzis friend class ExplodedGraphImpl; 43ad503c41557606d15b0420c824369456f6d20a8fJeremy Huddleston friend class GRCoreEngineImpl; 44ad503c41557606d15b0420c824369456f6d20a8fJeremy Huddleston friend class GRStmtNodeBuilderImpl; 45ad503c41557606d15b0420c824369456f6d20a8fJeremy Huddleston friend class GRBranchNodeBuilderImpl; 46ad503c41557606d15b0420c824369456f6d20a8fJeremy Huddleston friend class GRIndirectGotoNodeBuilderImpl; 47cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson friend class GRSwitchNodeBuilderImpl; 482b9dac397bd97909876bbda8532e2cbce9d8a77fJon TURNEY 49df04ffbf025994abd59e26c8439e77bb340ef20bGeorge Sapountzis class NodeGroup { 502b9dac397bd97909876bbda8532e2cbce9d8a77fJon TURNEY enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; 51df04ffbf025994abd59e26c8439e77bb340ef20bGeorge Sapountzis uintptr_t P; 5280b280db883edc9550484dba03bd5c124b6a9bf9Jeremy Huddleston 532b4e009ed56b69b243f5cc88f490dcf8166cf729Ian Romanick unsigned getKind() const { 54df04ffbf025994abd59e26c8439e77bb340ef20bGeorge Sapountzis return P & Mask; 55cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 569c7aaa7afbda92587f28cc28c4c8315e7861d318RALOVICH, Kristóf 579c7aaa7afbda92587f28cc28c4c8315e7861d318RALOVICH, Kristóf void* getPtr() const { 589c7aaa7afbda92587f28cc28c4c8315e7861d318RALOVICH, Kristóf return reinterpret_cast<void*>(P & ~Mask); 599c7aaa7afbda92587f28cc28c4c8315e7861d318RALOVICH, Kristóf } 609c7aaa7afbda92587f28cc28c4c8315e7861d318RALOVICH, Kristóf 619c7aaa7afbda92587f28cc28c4c8315e7861d318RALOVICH, Kristóf ExplodedNodeImpl* getNode() const { 6226d2ce0a09f1aac628519cf3473fcabd3f149446Ian Romanick return reinterpret_cast<ExplodedNodeImpl*>(getPtr()); 63cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 644a22ae8d446855d839cc199df8eb1b057045cb88Kristian Høgsberg 6580b280db883edc9550484dba03bd5c124b6a9bf9Jeremy Huddleston public: 664a22ae8d446855d839cc199df8eb1b057045cb88Kristian Høgsberg NodeGroup() : P(0) {} 67cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 68cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson ~NodeGroup(); 690896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 70cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson ExplodedNodeImpl** begin() const; 71cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 724a22ae8d446855d839cc199df8eb1b057045cb88Kristian Høgsberg ExplodedNodeImpl** end() const; 73cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 74cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson unsigned size() const; 75cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 76e82dd8c6e1fa2fff5b960de26961080ba5e9651dKristian Høgsberg bool empty() const; 77eeaab2047cfce8a7445fd9f835e737682eb503acKristian Høgsberg 78cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson void addNode(ExplodedNodeImpl* N); 79c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg 800896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf void setFlag() { 81cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson P |= AuxFlag; 820896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 830896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 84e82dd8c6e1fa2fff5b960de26961080ba5e9651dKristian Høgsberg bool getFlag() const { 85eeaab2047cfce8a7445fd9f835e737682eb503acKristian Høgsberg return P & AuxFlag ? true : false; 86e3e8196c025bd344a59b4671e473c395a6ea426bKristian Høgsberg } 87cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson }; 880896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 89cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson /// Location - The program location (within a function body) associated 904a22ae8d446855d839cc199df8eb1b057045cb88Kristian Høgsberg /// with this node. 91cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson const ProgramPoint Location; 92cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 934df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// State - The state associated with this node. Normally this value 944df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// is immutable, but we anticipate there will be times when algorithms 954df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// that directly manipulate the analysis graph will need to change it. 964df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes void* State; 974df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 984df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// Preds - The predecessors of this node. 994df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes NodeGroup Preds; 1004df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 1014df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// Succs - The successors of this node. 1024df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes NodeGroup Succs; 1034df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 1044df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// Construct a ExplodedNodeImpl with the provided location and state. 1054df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state) 1064df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes : Location(loc), State(state) {} 1074df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 1084df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// addPredeccessor - Adds a predecessor to the current node, and 1094df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// in tandem add this node as a successor of the other node. 1104df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes void addPredecessor(ExplodedNodeImpl* V) { 1114df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes assert (!V->isSink()); 1124df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes Preds.addNode(V); 1134df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes V->Succs.addNode(this); 1144df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes } 1154df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 1164df137691ee29bb812347fa2c5f19095243ede22Jesse Barnespublic: 1174df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes // This method is only defined so that we can cast a 1184df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes // void* to FoldingSet<ExplodedNodeImpl> so that we can iterate 1194df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes // over the vertices of EdgeNodeSetMap in ExplodeGraphImpl. 1204df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes // The actual profiling of vertices will be done in the derived 1214df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes // class, ExplodedNode<>. Nodes will NEVER be INSERTED into the 1224df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes // FoldingSet using this Profile method (since it doesn't do anything). 1234df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes inline void Profile(llvm::FoldingSetNodeID& ID) const { 1244df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes assert (false && "Needs to be implemented in derived class."); 1254df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes } 1264df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 1274df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes /// getLocation - Returns the edge associated with the given node. 1284df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes const ProgramPoint& getLocation() const { return Location; } 1294df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 1304df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes unsigned succ_size() const { return Succs.size(); } 1314df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes unsigned pred_size() const { return Preds.size(); } 1324df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes bool succ_empty() const { return Succs.empty(); } 1334df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes bool pred_empty() const { return Preds.size(); } 1344df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes 1354df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes bool isSink() const { return Preds.getFlag(); } 1364df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes void markAsSink() { Preds.setFlag(); } 1374df137691ee29bb812347fa2c5f19095243ede22Jesse Barnes}; 138cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 139cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 140cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksontemplate <typename StateTy> 1410896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristófstruct GRTrait { 142cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson static inline void* toPtr(StateTy S) { 143cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return reinterpret_cast<void*>(S); 144cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 145cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson static inline StateTy toState(void* P) { 146cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return reinterpret_cast<StateTy>(P); 147cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 1480896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf}; 149cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 150cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 151cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksontemplate <typename StateTy> 152cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass ExplodedNode : public ExplodedNodeImpl { 153588042a8ec4ea91a952c07a0768516fd590758f4Ian Romanickpublic: 1540896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf /// Construct a ExplodedNodeImpl with the given node ID, program edge, 155cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson /// and state. 156c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg explicit ExplodedNode(const ProgramPoint& loc, StateTy state) 157cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson : ExplodedNodeImpl(loc, GRTrait<StateTy>::toPtr(state)) {} 1580896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 15966fc35cde9ed68a09920ad6a28de794dd1d3aa8cKristian Høgsberg /// getState - Returns the state associated with the node. 16066fc35cde9ed68a09920ad6a28de794dd1d3aa8cKristian Høgsberg inline StateTy getState() const { 161cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return GRTrait<StateTy>::toState(State); 162cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 163cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 164cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson // Profiling (for FoldingSet). 165c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg 16666fc35cde9ed68a09920ad6a28de794dd1d3aa8cKristian Høgsberg static inline void Profile(llvm::FoldingSetNodeID& ID, 167cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson const ProgramPoint& Loc, 1680896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf StateTy state) { 1690896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf ID.Add(Loc); 1700896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf GRTrait<StateTy>::Profile(ID, state); 171cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 1720896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 1730896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf inline void Profile(llvm::FoldingSetNodeID& ID) const { 1740896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf Profile(ID, getLocation(), getState()); 175cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 1760896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 1770896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf // Iterators over successor and predecessor vertices. 1780896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef ExplodedNode** succ_iterator; 1790896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef const ExplodedNode** const_succ_iterator; 180cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson typedef ExplodedNode** pred_iterator; 1810896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef const ExplodedNode** const_pred_iterator; 1820896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 1830896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } 1840896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } 185cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 1860896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf const_pred_iterator pred_begin() const { 18766fc35cde9ed68a09920ad6a28de794dd1d3aa8cKristian Høgsberg return const_cast<ExplodedNode*>(this)->pred_begin(); 1880896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 1890896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf const_pred_iterator pred_end() const { 1900896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf return const_cast<ExplodedNode*>(this)->pred_end(); 1910896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 1920896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 1930896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } 194cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } 195cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 196cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson const_succ_iterator succ_begin() const { 197cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return const_cast<ExplodedNode*>(this)->succ_begin(); 198cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 199cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson const_succ_iterator succ_end() const { 200cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return const_cast<ExplodedNode*>(this)->succ_end(); 201cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 202cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson}; 203cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 2046ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg 205cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonclass ExplodedGraphImpl { 206cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonprotected: 2076ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg friend class GRCoreEngineImpl; 2086ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg friend class GRStmtNodeBuilderImpl; 2090896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf friend class GRBranchNodeBuilderImpl; 210c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg friend class GRIndirectGotoNodeBuilderImpl; 2116ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg friend class GRSwitchNodeBuilderImpl; 2120896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 2136ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg // Type definitions. 2140896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; 2150896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; 2160896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 21766fc35cde9ed68a09920ad6a28de794dd1d3aa8cKristian Høgsberg /// Roots - The roots of the simulation graph. Usually there will be only 2186ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg /// one, but clients are free to establish multiple subgraphs within a single 2196ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg /// SimulGraph. Moreover, these subgraphs can often merge when paths from 2206ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg /// different roots reach the same state at the same program location. 2216ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg RootsTy Roots; 2226ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg 2230896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf /// EndNodes - The nodes in the simulation graph which have been 2240896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf /// specially marked as the endpoint of an abstract simulation path. 22577c7f90ed44748f0e54e894deff1cac63da54cd6Kristian Høgsberg EndNodesTy EndNodes; 2260896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 227cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson /// Allocator - BumpPtrAllocator to create nodes. 228cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson llvm::BumpPtrAllocator Allocator; 22931819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg 230c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg /// cfg - The CFG associated with this analysis graph. 23166fc35cde9ed68a09920ad6a28de794dd1d3aa8cKristian Høgsberg CFG& cfg; 23231819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg 23331819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg /// FD - The function declaration of the function being analyzed. 23431819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg FunctionDecl& FD; 23531819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg 23631819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg /// Ctx - The ASTContext used to "interpret" FD. 23731819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg ASTContext& Ctx; 23831819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg 2396ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg /// NumNodes - The number of nodes in the graph. 24031819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg unsigned NumNodes; 241c491e585e43d48a2aeec96ccc4008da6c443fb42Kristian Høgsberg 24231819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg /// getNodeImpl - Retrieve the node associated with a (Location,State) 24331819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg /// pair, where 'State' is represented as an opaque void*. This method 24431819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg /// is intended to be used only by GRCoreEngineImpl. 24531819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State, 246cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson bool* IsNew) = 0; 247cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 2483869be74afb184dbdf9d67fda3de3e3ac7e3db6cAdam Jackson /// addRoot - Add an untyped node to the set of roots. 2490896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { 250cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson Roots.push_back(V); 251cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return V; 252cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 253cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 2543869be74afb184dbdf9d67fda3de3e3ac7e3db6cAdam Jackson /// addEndOfPath - Add an untyped node to the set of EOP nodes. 2553869be74afb184dbdf9d67fda3de3e3ac7e3db6cAdam Jackson ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { 2567bcfb66000557a0ef32bdc6b31949a92f95a9ff6Ian Romanick EndNodes.push_back(V); 257cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return V; 258b5dc40710d0e5edffb9f673dfbf26df4d0043eefnobled } 259b5dc40710d0e5edffb9f673dfbf26df4d0043eefnobled 260c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg // ctor. 2610896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf ExplodedGraphImpl(CFG& c, FunctionDecl& f, ASTContext& ctx) 2620896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf : cfg(c), FD(f), Ctx(ctx), NumNodes(0) {} 263cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 264b5dc40710d0e5edffb9f673dfbf26df4d0043eefnobledpublic: 265b5dc40710d0e5edffb9f673dfbf26df4d0043eefnobled virtual ~ExplodedGraphImpl() {} 266b5dc40710d0e5edffb9f673dfbf26df4d0043eefnobled 267b5dc40710d0e5edffb9f673dfbf26df4d0043eefnobled unsigned num_roots() const { return Roots.size(); } 268d46d30f997c1718217545947ca4d80ec7d18e684Ian Romanick unsigned num_eops() const { return EndNodes.size(); } 2690896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 270cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson bool empty() const { return NumNodes == 0; } 2716ec39db726beead21d97bf64ddbe1f0b2d2d6ca1Kristian Høgsberg unsigned size() const { return NumNodes; } 2721885cf27c9c4642a049c60a8236cb84735cb9ebaJeremy Huddleston 2731885cf27c9c4642a049c60a8236cb84735cb9ebaJeremy Huddleston llvm::BumpPtrAllocator& getAllocator() { return Allocator; } 2741885cf27c9c4642a049c60a8236cb84735cb9ebaJeremy Huddleston CFG& getCFG() { return cfg; } 2756ec39db726beead21d97bf64ddbe1f0b2d2d6ca1Kristian Høgsberg ASTContext& getContext() { return Ctx; } 2766ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg FunctionDecl& getFunctionDecl() { return FD; } 27731819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsberg}; 2786ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg 2791885cf27c9c4642a049c60a8236cb84735cb9ebaJeremy Huddlestontemplate <typename CHECKER> 28031819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsbergclass ExplodedGraph : public ExplodedGraphImpl { 28131819830b66a49f1b62e09090cc65aefc657aeb8Kristian Høgsbergpublic: 282643b2af0203764cb9f0a5b9e082937ab3f243523Kristian Høgsberg typedef CHECKER CheckerTy; 283bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick typedef typename CHECKER::StateTy StateTy; 284bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick typedef ExplodedNode<StateTy> NodeTy; 285bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick typedef llvm::FoldingSet<NodeTy> AllNodesTy; 286bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 287bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanickprotected: 288bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick llvm::OwningPtr<CheckerTy> CheckerState; 289bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 290bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick /// Nodes - The nodes in the graph. 291bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick AllNodesTy Nodes; 292bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 293d46d30f997c1718217545947ca4d80ec7d18e684Ian Romanickprotected: 294c3db1d621e1f7c73006ed76855d31b1034bc3aefIan Romanick virtual ExplodedNodeImpl* 295bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick getNodeImpl(const ProgramPoint& L, void* State, bool* IsNew) { 296c491e585e43d48a2aeec96ccc4008da6c443fb42Kristian Høgsberg return getNode(L, GRTrait<StateTy>::toState(State), IsNew); 297bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick } 298bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 299cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jacksonpublic: 300bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick ExplodedGraph(CFG& c, FunctionDecl& fd, ASTContext& ctx) 301bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick : ExplodedGraphImpl(c, fd, ctx), CheckerState(new CheckerTy(*this)) {} 302bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 303bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick /// getCheckerState - Returns the internal checker state associated 304bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick /// with the exploded graph. Ownership remains with the ExplodedGraph 305bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick /// objecct. 306bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick CheckerTy* getCheckerState() const { return CheckerState.get(); } 307bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 308d46d30f997c1718217545947ca4d80ec7d18e684Ian Romanick /// getNode - Retrieve the node associated with a (Location,State) pair, 309c3db1d621e1f7c73006ed76855d31b1034bc3aefIan Romanick /// where the 'Location' is a ProgramPoint in the CFG. If no node for 310bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick /// this pair exists, it is created. IsNew is set to true if 311bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick /// the node was freshly created. 312c491e585e43d48a2aeec96ccc4008da6c443fb42Kristian Høgsberg NodeTy* getNode(const ProgramPoint& L, StateTy State, bool* IsNew = NULL) { 313bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 3140896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf // Profile 'State' to determine if we already have an existing node. 3158bffadbc83d19ecd8be8f0107d51463e36477666Ian Romanick llvm::FoldingSetNodeID profile; 316bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick void* InsertPos = 0; 317bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 318bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick NodeTy::Profile(profile, L, State); 319bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos); 320bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 321bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick if (!V) { 322bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick // Allocate a new node. 323bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick V = (NodeTy*) Allocator.Allocate<NodeTy>(); 324bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick new (V) NodeTy(L, State); 325bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 326bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick // Insert the node into the node set and return it. 327bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick Nodes.InsertNode(V, InsertPos); 328bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 329d46d30f997c1718217545947ca4d80ec7d18e684Ian Romanick ++NumNodes; 330c3db1d621e1f7c73006ed76855d31b1034bc3aefIan Romanick 331bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick if (IsNew) *IsNew = true; 332bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick } 333c491e585e43d48a2aeec96ccc4008da6c443fb42Kristian Høgsberg else 334bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick if (IsNew) *IsNew = false; 335bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 3368bffadbc83d19ecd8be8f0107d51463e36477666Ian Romanick return V; 337bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick } 338bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 339bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick // Iterators. 340bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick typedef NodeTy** roots_iterator; 341bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick typedef const NodeTy** const_roots_iterator; 3420896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef NodeTy** eop_iterator; 343cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson typedef const NodeTy** const_eop_iterator; 344bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 345bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick 346cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson roots_iterator roots_begin() { 347a832aa5ba097253f53983e3f1186b71626d164aeIan Romanick return reinterpret_cast<roots_iterator>(Roots.begin()); 348bc7b2f0dc33753f6d6b55bd4058e82ddf0997967Ian Romanick } 349521e4b9b7e3c79e7362f7cbd594a2e8cf74cdfe4Brian Paul 350521e4b9b7e3c79e7362f7cbd594a2e8cf74cdfe4Brian Paul roots_iterator roots_end() { 351c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg return reinterpret_cast<roots_iterator>(Roots.end()); 352cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 353cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 35438c51a76533a90cf2c9381c99247cfac45fe70ebKristian Høgsberg const_roots_iterator roots_begin() const { 3550896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf return const_cast<ExplodedGraph>(this)->roots_begin(); 3560896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 357cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 3586ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg const_roots_iterator roots_end() const { 35952cf8db428909156b062f17a9e6251a38178dec3Ian Romanick return const_cast<ExplodedGraph>(this)->roots_end(); 36052cf8db428909156b062f17a9e6251a38178dec3Ian Romanick } 361ad503c41557606d15b0420c824369456f6d20a8fJeremy Huddleston 36266fc35cde9ed68a09920ad6a28de794dd1d3aa8cKristian Høgsberg eop_iterator eop_begin() { 36352cf8db428909156b062f17a9e6251a38178dec3Ian Romanick return reinterpret_cast<eop_iterator>(EndNodes.begin()); 3646ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg } 3656ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg 36652cf8db428909156b062f17a9e6251a38178dec3Ian Romanick eop_iterator eop_end() { 36752cf8db428909156b062f17a9e6251a38178dec3Ian Romanick return reinterpret_cast<eop_iterator>(EndNodes.end()); 36852cf8db428909156b062f17a9e6251a38178dec3Ian Romanick } 36952cf8db428909156b062f17a9e6251a38178dec3Ian Romanick 37052cf8db428909156b062f17a9e6251a38178dec3Ian Romanick const_eop_iterator eop_begin() const { 37152cf8db428909156b062f17a9e6251a38178dec3Ian Romanick return const_cast<ExplodedGraph>(this)->eop_begin(); 37252cf8db428909156b062f17a9e6251a38178dec3Ian Romanick } 37352cf8db428909156b062f17a9e6251a38178dec3Ian Romanick 37452cf8db428909156b062f17a9e6251a38178dec3Ian Romanick const_eop_iterator eop_end() const { 37552cf8db428909156b062f17a9e6251a38178dec3Ian Romanick return const_cast<ExplodedGraph>(this)->eop_end(); 37652cf8db428909156b062f17a9e6251a38178dec3Ian Romanick } 37752cf8db428909156b062f17a9e6251a38178dec3Ian Romanick}; 3786ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsberg 37952cf8db428909156b062f17a9e6251a38178dec3Ian Romanick 38052cf8db428909156b062f17a9e6251a38178dec3Ian Romanicktemplate <typename NodeTy> 3816ddf66e9230ee862ac341c4767cf6b3b2dd2552bKristian Høgsbergclass ExplodedNodeSet { 38252cf8db428909156b062f17a9e6251a38178dec3Ian Romanick 383cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy; 384cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson ImplTy Impl; 3854dbd13cb3f5aeff6ddc85fd091b4677369c19778Ian Romanick 386c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsbergpublic: 387cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson ExplodedNodeSet(NodeTy* N) { 388c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()); 389c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg Impl.insert(N); 390c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg } 391c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg 392c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg ExplodedNodeSet() {} 393c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg 394c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg inline void Add(NodeTy* N) { 395c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N); 396c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg } 397c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg 398c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg typedef typename ImplTy::iterator iterator; 399c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg typedef typename ImplTy::const_iterator const_iterator; 400cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 401cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson inline unsigned size() const { return Impl.size(); } 402cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson inline bool empty() const { return Impl.empty(); } 4039e2bc5d4b0385e374e06c0b26db266067a723bf3Adam Jackson 4049e2bc5d4b0385e374e06c0b26db266067a723bf3Adam Jackson inline iterator begin() { return Impl.begin(); } 4059e2bc5d4b0385e374e06c0b26db266067a723bf3Adam Jackson inline iterator end() { return Impl.end(); } 406cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 407c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg inline const_iterator begin() const { return Impl.begin(); } 408c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg inline const_iterator end() const { return Impl.end(); } 4094dbd13cb3f5aeff6ddc85fd091b4677369c19778Ian Romanick}; 4100896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 411cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson} // end clang namespace 4120896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 4134dbd13cb3f5aeff6ddc85fd091b4677369c19778Ian Romanick// GraphTraits 4144dbd13cb3f5aeff6ddc85fd091b4677369c19778Ian Romanick 4154dbd13cb3f5aeff6ddc85fd091b4677369c19778Ian Romanicknamespace llvm { 4165e6a6a2719c695996490bde491dac267e52f78afBrian Paul template<typename StateTy> 4175e6a6a2719c695996490bde491dac267e52f78afBrian Paul struct GraphTraits<clang::ExplodedNode<StateTy>*> { 4185e6a6a2719c695996490bde491dac267e52f78afBrian Paul typedef clang::ExplodedNode<StateTy> NodeType; 4195e6a6a2719c695996490bde491dac267e52f78afBrian Paul typedef typename NodeType::succ_iterator ChildIteratorType; 4205e6a6a2719c695996490bde491dac267e52f78afBrian Paul typedef llvm::df_iterator<NodeType*> nodes_iterator; 4215e6a6a2719c695996490bde491dac267e52f78afBrian Paul 422c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg static inline NodeType* getEntryNode(NodeType* N) { 4234dbd13cb3f5aeff6ddc85fd091b4677369c19778Ian Romanick return N; 4244dbd13cb3f5aeff6ddc85fd091b4677369c19778Ian Romanick } 4255e6a6a2719c695996490bde491dac267e52f78afBrian Paul 426c796bb0cc3fde409545bff320540ddf5c029e513Kristian Høgsberg static inline ChildIteratorType child_begin(NodeType* N) { 427cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return N->succ_begin(); 428489ccef3982267b0d35c8548921f58d553c25a3aAdam Jackson } 429cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 430cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson static inline ChildIteratorType child_end(NodeType* N) { 431cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return N->succ_end(); 43238c51a76533a90cf2c9381c99247cfac45fe70ebKristian Høgsberg } 4330896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 434cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson static inline nodes_iterator nodes_begin(NodeType* N) { 435c356f5867f2c1fad7155df538b9affa8dbdcf869Kristian Høgsberg return df_begin(N); 436cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 4370896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 4380896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf static inline nodes_iterator nodes_end(NodeType* N) { 4390896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf return df_end(N); 4400896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 441cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson }; 4420896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 4430896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf template<typename StateTy> 4440896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf struct GraphTraits<const clang::ExplodedNode<StateTy>*> { 4450896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef const clang::ExplodedNode<StateTy> NodeType; 4460896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf typedef typename NodeType::succ_iterator ChildIteratorType; 447cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson typedef llvm::df_iterator<NodeType*> nodes_iterator; 448cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 449cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson static inline NodeType* getEntryNode(NodeType* N) { 450cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return N; 451cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 45238c51a76533a90cf2c9381c99247cfac45fe70ebKristian Høgsberg 4530896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf static inline ChildIteratorType child_begin(NodeType* N) { 4540896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf return N->succ_begin(); 4550896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 4560896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 4570896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf static inline ChildIteratorType child_end(NodeType* N) { 4580896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf return N->succ_end(); 4590896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 4600896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 4610896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf static inline nodes_iterator nodes_begin(NodeType* N) { 4620896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf return df_begin(N); 4630896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf } 4640896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf 4650896268b97674d009d609476acfa1eed5dfea350RALOVICH, Kristóf static inline nodes_iterator nodes_end(NodeType* N) { 466cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson return df_end(N); 467cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson } 468cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson }; 4697b7845a076c933e096ac511b4184141ba194449aKristian Høgsberg 4707b7845a076c933e096ac511b4184141ba194449aKristian Høgsberg} // end llvm namespace 471cb3610e37c4c0a40520441b8515d044dabcc8854Adam Jackson 47238c51a76533a90cf2c9381c99247cfac45fe70ebKristian Høgsberg#endif 4737b7845a076c933e096ac511b4184141ba194449aKristian Høgsberg