Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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