//===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the template classes ExplodedNode and ExplodedGraph,
// which represent a path-sensitive, intra-procedural "exploded graph."
// See "Precise interprocedural dataflow analysis via graph reachability"
// by Reps, Horwitz, and Sagiv
// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an
// exploded graph.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
#include "clang/Analysis/AnalysisDeclContext.h"
#include "clang/Analysis/ProgramPoint.h"
#include "clang/Analysis/Support/BumpVector.h"
#include "clang/Basic/LLVM.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include <cassert>
#include <cstdint>
#include <memory>
#include <optional>
#include <utility>
#include <vector>
namespace clang {
class CFG;
class Decl;
class Expr;
class ParentMap;
class Stmt;
namespace ento {
class ExplodedGraph;
//===----------------------------------------------------------------------===//
// ExplodedGraph "implementation" classes. These classes are not typed to
// contain a specific kind of state. Typed-specialized versions are defined
// on top of these classes.
//===----------------------------------------------------------------------===//
// ExplodedNode is not constified all over the engine because we need to add
// successors to it at any time after creating it.
class ExplodedNode : public llvm::FoldingSetNode {
friend class BranchNodeBuilder;
friend class CoreEngine;
friend class EndOfFunctionNodeBuilder;
friend class ExplodedGraph;
friend class IndirectGotoNodeBuilder;
friend class NodeBuilder;
friend class SwitchNodeBuilder;
/// Efficiently stores a list of ExplodedNodes, or an optional flag.
///
/// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing
/// for the case when there is only one node in the group. This is a fairly
/// common case in an ExplodedGraph, where most nodes have only one
/// predecessor and many have only one successor. It can also be used to
/// store a flag rather than a node list, which ExplodedNode uses to mark
/// whether a node is a sink. If the flag is set, the group is implicitly
/// empty and no nodes may be added.
class NodeGroup {
// Conceptually a discriminated union. If the low bit is set, the node is
// a sink. If the low bit is not set, the pointer refers to the storage
// for the nodes in the group.
// This is not a PointerIntPair in order to keep the storage type opaque.
uintptr_t P;
public:
NodeGroup(bool Flag = false) : P(Flag) {
assert(getFlag() == Flag);
}
ExplodedNode * const *begin() const;
ExplodedNode * const *end() const;
unsigned size() const;
bool empty() const { return P == 0 || getFlag() != 0; }
/// Adds a node to the list.
///
/// The group must not have been created with its flag set.
void addNode(ExplodedNode *N, ExplodedGraph &G);
/// Replaces the single node in this group with a new node.
///
/// Note that this should only be used when you know the group was not
/// created with its flag set, and that the group is empty or contains
/// only a single node.
void replaceNode(ExplodedNode *node);
/// Returns whether this group was created with its flag set.
bool getFlag() const {
return (P & 1);
}
};
/// Location - The program location (within a function body) associated
/// with this node.
const ProgramPoint Location;
/// State - The state associated with this node.
ProgramStateRef State;
/// Preds - The predecessors of this node.
NodeGroup Preds;
/// Succs - The successors of this node.
NodeGroup Succs;
int64_t Id;
public:
explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
int64_t Id, bool IsSink)
: Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) {
assert(isSink() == IsSink);
}
/// getLocation - Returns the edge associated with the given node.
ProgramPoint getLocation() const { return Location; }
const LocationContext *getLocationContext() const {
return getLocation().getLocationContext();
}
const StackFrameContext *getStackFrame() const {
return getLocation().getStackFrame();
}
const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
CFG &getCFG() const { return *getLocationContext()->getCFG(); }
const CFGBlock *getCFGBlock() const;
const ParentMap &getParentMap() const {
return getLocationContext()->getParentMap();
}
template <typename T> T &getAnalysis() const {
return *getLocationContext()->getAnalysis<T>();
}
const ProgramStateRef &getState() const { return State; }
template <typename T> std::optional<T> getLocationAs() const & {
return Location.getAs<T>();
}
/// Get the value of an arbitrary expression at this node.
SVal getSVal(const Stmt *S) const {
return getState()->getSVal(S, getLocationContext());
}
static void Profile(llvm::FoldingSetNodeID &ID,
const ProgramPoint &Loc,
const ProgramStateRef &state,
bool IsSink) {
ID.Add(Loc);
ID.AddPointer(state.get());
ID.AddBoolean(IsSink);
}
void Profile(llvm::FoldingSetNodeID& ID) const {
// We avoid copy constructors by not using accessors.
Profile(ID, Location, State, isSink());
}
/// addPredeccessor - Adds a predecessor to the current node, and
/// in tandem add this node as a successor of the other node.
void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
unsigned succ_size() const { return Succs.size(); }
unsigned pred_size() const { return Preds.size(); }
bool succ_empty() const { return Succs.empty(); }
bool pred_empty() const { return Preds.empty(); }
bool isSink() const { return Succs.getFlag(); }
bool hasSinglePred() const {
return (pred_size() == 1);
}
ExplodedNode *getFirstPred() {
return pred_empty() ? nullptr : *(pred_begin());
}
const ExplodedNode *getFirstPred() const {
return const_cast<ExplodedNode*>(this)->getFirstPred();
}
ExplodedNode *getFirstSucc() {
return succ_empty() ? nullptr : *(succ_begin());
}
const ExplodedNode *getFirstSucc() const {
return const_cast<ExplodedNode*>(this)->getFirstSucc();
}
// Iterators over successor and predecessor vertices.
using succ_iterator = ExplodedNode * const *;
using succ_range = llvm::iterator_range<succ_iterator>;
using const_succ_iterator = const ExplodedNode * const *;
using const_succ_range = llvm::iterator_range<const_succ_iterator>;
using pred_iterator = ExplodedNode * const *;
using pred_range = llvm::iterator_range<pred_iterator>;
using const_pred_iterator = const ExplodedNode * const *;
using const_pred_range = llvm::iterator_range<const_pred_iterator>;
pred_iterator pred_begin() { return Preds.begin(); }
pred_iterator pred_end() { return Preds.end(); }
pred_range preds() { return {Preds.begin(), Preds.end()}; }
const_pred_iterator pred_begin() const {
return const_cast<ExplodedNode*>(this)->pred_begin();
}
const_pred_iterator pred_end() const {
return const_cast<ExplodedNode*>(this)->pred_end();
}
const_pred_range preds() const { return {Preds.begin(), Preds.end()}; }
succ_iterator succ_begin() { return Succs.begin(); }
succ_iterator succ_end() { return Succs.end(); }
succ_range succs() { return {Succs.begin(), Succs.end()}; }
const_succ_iterator succ_begin() const {
return const_cast<ExplodedNode*>(this)->succ_begin();
}
const_succ_iterator succ_end() const {
return const_cast<ExplodedNode*>(this)->succ_end();
}
const_succ_range succs() const { return {Succs.begin(), Succs.end()}; }
int64_t getID() const { return Id; }
/// The node is trivial if it has only one successor, only one predecessor,
/// it's predecessor has only one successor,
/// and its program state is the same as the program state of the previous
/// node.
/// Trivial nodes may be skipped while printing exploded graph.
bool isTrivial() const;
/// If the node's program point corresponds to a statement, retrieve that
/// statement. Useful for figuring out where to put a warning or a note.
/// If the statement belongs to a body-farmed definition,
/// retrieve the call site for that definition.
const Stmt *getStmtForDiagnostics() const;
/// Find the next statement that was executed on this node's execution path.
/// Useful for explaining control flow that follows the current node.
/// If the statement belongs to a body-farmed definition, retrieve the
/// call site for that definition.
const Stmt *getNextStmtForDiagnostics() const;
/// Find the statement that was executed immediately before this node.
/// Useful when the node corresponds to a CFG block entrance.
/// If the statement belongs to a body-farmed definition, retrieve the
/// call site for that definition.
const Stmt *getPreviousStmtForDiagnostics() const;
/// Find the statement that was executed at or immediately before this node.
/// Useful when any nearby statement will do.
/// If the statement belongs to a body-farmed definition, retrieve the
/// call site for that definition.
const Stmt *getCurrentOrPreviousStmtForDiagnostics() const;
private:
void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
};
using InterExplodedGraphMap =
llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
class ExplodedGraph {
protected:
friend class CoreEngine;
// Type definitions.
using NodeVector = std::vector<ExplodedNode *>;
/// The roots of the simulation graph. Usually there will be only
/// one, but clients are free to establish multiple subgraphs within a single
/// SimulGraph. Moreover, these subgraphs can often merge when paths from
/// different roots reach the same state at the same program location.
NodeVector Roots;
/// The nodes in the simulation graph which have been
/// specially marked as the endpoint of an abstract simulation path.
NodeVector EndNodes;
/// Nodes - The nodes in the graph.
llvm::FoldingSet<ExplodedNode> Nodes;
/// BVC - Allocator and context for allocating nodes and their predecessor
/// and successor groups.
BumpVectorContext BVC;
/// NumNodes - The number of nodes in the graph.
int64_t NumNodes = 0;
/// A list of recently allocated nodes that can potentially be recycled.
NodeVector ChangedNodes;
/// A list of nodes that can be reused.
NodeVector FreeNodes;
/// Determines how often nodes are reclaimed.
///
/// If this is 0, nodes will never be reclaimed.
unsigned ReclaimNodeInterval = 0;
/// Counter to determine when to reclaim nodes.
unsigned ReclaimCounter;
public:
ExplodedGraph();
~ExplodedGraph();
/// Retrieve the node associated with a (Location,State) pair,
/// where the 'Location' is a ProgramPoint in the CFG. If no node for
/// this pair exists, it is created. IsNew is set to true if
/// the node was freshly created.
ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
bool IsSink = false,
bool* IsNew = nullptr);
/// Create a node for a (Location, State) pair,
/// but don't store it for deduplication later. This
/// is useful when copying an already completed
/// ExplodedGraph for further processing.
ExplodedNode *createUncachedNode(const ProgramPoint &L,
ProgramStateRef State,
int64_t Id,
bool IsSink = false);
std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
return std::make_unique<ExplodedGraph>();
}
/// addRoot - Add an untyped node to the set of roots.
ExplodedNode *addRoot(ExplodedNode *V) {
Roots.push_back(V);
return V;
}
/// addEndOfPath - Add an untyped node to the set of EOP nodes.
ExplodedNode *addEndOfPath(ExplodedNode *V) {
EndNodes.push_back(V);
return V;
}
unsigned num_roots() const { return Roots.size(); }
unsigned num_eops() const { return EndNodes.size(); }
bool empty() const { return NumNodes == 0; }
unsigned size() const { return NumNodes; }
void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
// Iterators.
using NodeTy = ExplodedNode;
using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
using roots_iterator = NodeVector::iterator;
using const_roots_iterator = NodeVector::const_iterator;
using eop_iterator = NodeVector::iterator;
using const_eop_iterator = NodeVector::const_iterator;
using node_iterator = AllNodesTy::iterator;
using const_node_iterator = AllNodesTy::const_iterator;
node_iterator nodes_begin() { return Nodes.begin(); }
node_iterator nodes_end() { return Nodes.end(); }
const_node_iterator nodes_begin() const { return Nodes.begin(); }
const_node_iterator nodes_end() const { return Nodes.end(); }
roots_iterator roots_begin() { return Roots.begin(); }
roots_iterator roots_end() { return Roots.end(); }
const_roots_iterator roots_begin() const { return Roots.begin(); }
const_roots_iterator roots_end() const { return Roots.end(); }
eop_iterator eop_begin() { return EndNodes.begin(); }
eop_iterator eop_end() { return EndNodes.end(); }
const_eop_iterator eop_begin() const { return EndNodes.begin(); }
const_eop_iterator eop_end() const { return EndNodes.end(); }
llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
BumpVectorContext &getNodeAllocator() { return BVC; }
using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;
/// Creates a trimmed version of the graph that only contains paths leading
/// to the given nodes.
///
/// \param Nodes The nodes which must appear in the final graph. Presumably
/// these are end-of-path nodes (i.e. they have no successors).
/// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
/// the returned graph.
/// \param[out] InverseMap An optional map from nodes in the returned graph to
/// nodes in this graph.
/// \returns The trimmed graph
std::unique_ptr<ExplodedGraph>
trim(ArrayRef<const NodeTy *> Nodes,
InterExplodedGraphMap *ForwardMap = nullptr,
InterExplodedGraphMap *InverseMap = nullptr) const;
/// Enable tracking of recently allocated nodes for potential reclamation
/// when calling reclaimRecentlyAllocatedNodes().
void enableNodeReclamation(unsigned Interval) {
ReclaimCounter = ReclaimNodeInterval = Interval;
}
/// Reclaim "uninteresting" nodes created since the last time this method
/// was called.
void reclaimRecentlyAllocatedNodes();
/// Returns true if nodes for the given expression kind are always
/// kept around.
static bool isInterestingLValueExpr(const Expr *Ex);
private:
bool shouldCollect(const ExplodedNode *node);
void collectNode(ExplodedNode *node);
};
class ExplodedNodeSet {
using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
ImplTy Impl;
public:
ExplodedNodeSet(ExplodedNode *N) {
assert(N && !static_cast<ExplodedNode*>(N)->isSink());
Impl.insert(N);
}
ExplodedNodeSet() = default;
void Add(ExplodedNode *N) {
if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
}
using iterator = ImplTy::iterator;
using const_iterator = ImplTy::const_iterator;
unsigned size() const { return Impl.size(); }
bool empty() const { return Impl.empty(); }
bool erase(ExplodedNode *N) { return Impl.remove(N); }
void clear() { Impl.clear(); }
void insert(const ExplodedNodeSet &S) {
assert(&S != this);
if (empty())
Impl = S.Impl;
else
Impl.insert(S.begin(), S.end());
}
iterator begin() { return Impl.begin(); }
iterator end() { return Impl.end(); }
const_iterator begin() const { return Impl.begin(); }
const_iterator end() const { return Impl.end(); }
};
} // namespace ento
} // namespace clang
// GraphTraits
namespace llvm {
template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
using GraphTy = clang::ento::ExplodedGraph *;
using NodeRef = clang::ento::ExplodedNode *;
using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
using nodes_iterator = llvm::df_iterator<GraphTy>;
static NodeRef getEntryNode(const GraphTy G) {
return *G->roots_begin();
}
static bool predecessorOfTrivial(NodeRef N) {
return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
}
static ChildIteratorType child_begin(NodeRef N) {
if (predecessorOfTrivial(N))
return child_begin(*N->succ_begin());
return N->succ_begin();
}
static ChildIteratorType child_end(NodeRef N) {
if (predecessorOfTrivial(N))
return child_end(N->getFirstSucc());
return N->succ_end();
}
static nodes_iterator nodes_begin(const GraphTy G) {
return df_begin(G);
}
static nodes_iterator nodes_end(const GraphTy G) {
return df_end(G);
}
};
} // namespace llvm
#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H