summaryrefslogtreecommitdiff
path: root/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
diff options
context:
space:
mode:
Diffstat (limited to 'clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h')
-rw-r--r--clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h504
1 files changed, 504 insertions, 0 deletions
diff --git a/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
new file mode 100644
index 00000000..727d04cb
--- /dev/null
+++ b/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -0,0 +1,504 @@
+//===- 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/Optional.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 <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;
+
+public:
+ explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
+ bool IsSink)
+ : Location(loc), State(std::move(state)), Succs(IsSink) {
+ 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(); }
+
+ 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>
+ Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
+ 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 const_succ_iterator = const ExplodedNode * const *;
+ using pred_iterator = ExplodedNode * const *;
+ using const_pred_iterator = const ExplodedNode * const *;
+
+ pred_iterator pred_begin() { return Preds.begin(); }
+ pred_iterator pred_end() { return 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();
+ }
+
+ succ_iterator succ_begin() { return Succs.begin(); }
+ succ_iterator succ_end() { return 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();
+ }
+
+ int64_t getID(ExplodedGraph *G) const;
+
+ /// 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;
+
+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.
+ unsigned 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,
+ bool IsSink = false);
+
+ std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
+ return llvm::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
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-20 04:21:19 +0000