Merge "Update prebuilt Clang to r353983." into p9.0HEADp9.0-backupp9.0

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