diff options
Diffstat (limited to 'llvm/lib/Target/X86/ImmutableGraph.h')
| -rw-r--r-- | llvm/lib/Target/X86/ImmutableGraph.h | 432 |
1 files changed, 432 insertions, 0 deletions
diff --git a/llvm/lib/Target/X86/ImmutableGraph.h b/llvm/lib/Target/X86/ImmutableGraph.h new file mode 100644 index 00000000000..80c9cf489de --- /dev/null +++ b/llvm/lib/Target/X86/ImmutableGraph.h @@ -0,0 +1,432 @@ +//==========-- ImmutableGraph.h - A fast DAG implementation ---------=========// +// +// 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 +// +//===----------------------------------------------------------------------===// +/// +/// Description: ImmutableGraph is a fast DAG implementation that cannot be +/// modified, except by creating a new ImmutableGraph. ImmutableGraph is +/// implemented as two arrays: one containing nodes, and one containing edges. +/// The advantages to this implementation are two-fold: +/// 1. Iteration and traversal operations should experience terrific caching +/// performance. +/// 2. Set representations and operations on nodes and edges become +/// extraordinarily efficient. For instance, a set of edges is implemented as +/// a bit vector, wherein each bit corresponds to one edge in the edge +/// array. This implies a lower bound of 64x spacial improvement over, e.g., +/// an llvm::DenseSet or llvm::SmallSet. It also means that +/// insert/erase/contains operations complete in negligible constant time: +/// insert and erase require one load and one store, and contains requires +/// just one load. +/// +//===----------------------------------------------------------------------===// + +#ifndef IMMUTABLEGRAPH_H +#define IMMUTABLEGRAPH_H + +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <iterator> +#include <utility> +#include <vector> + +namespace llvm { + +template <typename _NodeValueT, typename _EdgeValueT, typename _SizeT = int> +class ImmutableGraph { + using Traits = GraphTraits<ImmutableGraph<_NodeValueT, _EdgeValueT> *>; + template <typename> friend class ImmutableGraphBuilder; + +public: + using NodeValueT = _NodeValueT; + using EdgeValueT = _EdgeValueT; + using size_type = _SizeT; + class Node; + class Edge { + friend class ImmutableGraph; + template <typename> friend class ImmutableGraphBuilder; + friend Traits; + + Node *__dest; + EdgeValueT __value; + + public: + EdgeValueT &value() { return __value; } + }; + class Node { + friend class ImmutableGraph; + template <typename> friend class ImmutableGraphBuilder; + friend Traits; + + Edge *__edges; + NodeValueT __value; + + public: + NodeValueT &value() { return __value; } + }; + +protected: + ImmutableGraph(Node *Nodes, size_type NodesSize, Edge *Edges, + size_type EdgesSize) + : __nodes{Nodes}, __nodes_size{NodesSize}, __edges{Edges}, + __edges_size{EdgesSize} {} + ImmutableGraph(const ImmutableGraph &) = delete; + ImmutableGraph(ImmutableGraph &&) = delete; + ImmutableGraph &operator=(const ImmutableGraph &) = delete; + ImmutableGraph &operator=(ImmutableGraph &&) = delete; + +public: + ~ImmutableGraph() { + delete[] __edges; + delete[] __nodes; + } + + Node *nodes_begin() const { return __nodes; } + Node *nodes_end() const { return __nodes + __nodes_size; } + Edge *edges_begin() const { return __edges; } + Edge *edges_end() const { return __edges + __edges_size; } + size_type nodes_size() const { return __nodes_size; } + size_type edges_size() const { return __edges_size; } + bool empty() const { return __nodes_size == 0; } + + class NodeSet { + friend class iterator; + + const ImmutableGraph &__g; + BitVector __v; + + public: + NodeSet(const ImmutableGraph &G, bool ContainsAll = false) + : __g{G}, __v{static_cast<unsigned>(__g.nodes_size()), ContainsAll} {} + bool insert(Node *N) { + size_type Idx = std::distance(__g.nodes_begin(), N); + bool AlreadyExists = __v.test(Idx); + __v.set(Idx); + return !AlreadyExists; + } + void erase(Node *N) { + size_type Idx = std::distance(__g.nodes_begin(), N); + __v.reset(Idx); + } + bool contains(Node *N) const { + size_type Idx = std::distance(__g.nodes_begin(), N); + return __v.test(Idx); + } + void clear() { __v.reset(); } + size_type empty() const { return __v.none(); } + /// Return the number of elements in the set + size_type count() const { return __v.count(); } + /// Return the size of the set's domain + size_type size() const { return __v.size(); } + /// Set union + NodeSet &operator|=(const NodeSet &RHS) { + assert(&this->__g == &RHS.__g); + __v |= RHS.__v; + return *this; + } + /// Set intersection + NodeSet &operator&=(const NodeSet &RHS) { + assert(&this->__g == &RHS.__g); + __v &= RHS.__v; + return *this; + } + /// Set disjoint union + NodeSet &operator^=(const NodeSet &RHS) { + assert(&this->__g == &RHS.__g); + __v ^= RHS.__v; + return *this; + } + + using index_iterator = typename BitVector::const_set_bits_iterator; + index_iterator index_begin() const { return __v.set_bits_begin(); } + index_iterator index_end() const { return __v.set_bits_end(); } + void set(size_type Idx) { __v.set(Idx); } + void reset(size_type Idx) { __v.reset(Idx); } + + class iterator { + const NodeSet &__set; + size_type __current; + + void advance() { + assert(__current != -1); + __current = __set.__v.find_next(__current); + } + + public: + iterator(const NodeSet &Set, size_type Begin) + : __set{Set}, __current{Begin} {} + iterator operator++(int) { + iterator Tmp = *this; + advance(); + return Tmp; + } + iterator &operator++() { + advance(); + return *this; + } + Node *operator*() const { + assert(__current != -1); + return __set.__g.nodes_begin() + __current; + } + bool operator==(const iterator &other) const { + assert(&this->__set == &other.__set); + return this->__current == other.__current; + } + bool operator!=(const iterator &other) const { return !(*this == other); } + }; + + iterator begin() const { return iterator{*this, __v.find_first()}; } + iterator end() const { return iterator{*this, -1}; } + }; + + class EdgeSet { + const ImmutableGraph &__g; + BitVector __v; + + public: + EdgeSet(const ImmutableGraph &G, bool ContainsAll = false) + : __g{G}, __v{static_cast<unsigned>(__g.edges_size()), ContainsAll} {} + bool insert(Edge *E) { + size_type Idx = std::distance(__g.edges_begin(), E); + bool AlreadyExists = __v.test(Idx); + __v.set(Idx); + return !AlreadyExists; + } + void erase(Edge *E) { + size_type Idx = std::distance(__g.edges_begin(), E); + __v.reset(Idx); + } + bool contains(Edge *E) const { + size_type Idx = std::distance(__g.edges_begin(), E); + return __v.test(Idx); + } + void clear() { __v.reset(); } + bool empty() const { return __v.none(); } + /// Return the number of elements in the set + size_type count() const { return __v.count(); } + /// Return the size of the set's domain + size_type size() const { return __v.size(); } + /// Set union + EdgeSet &operator|=(const EdgeSet &RHS) { + assert(&this->__g == &RHS.__g); + __v |= RHS.__v; + return *this; + } + /// Set intersection + EdgeSet &operator&=(const EdgeSet &RHS) { + assert(&this->__g == &RHS.__g); + __v &= RHS.__v; + return *this; + } + /// Set disjoint union + EdgeSet &operator^=(const EdgeSet &RHS) { + assert(&this->__g == &RHS.__g); + __v ^= RHS.__v; + return *this; + } + + using index_iterator = typename BitVector::const_set_bits_iterator; + index_iterator index_begin() const { return __v.set_bits_begin(); } + index_iterator index_end() const { return __v.set_bits_end(); } + void set(size_type Idx) { __v.set(Idx); } + void reset(size_type Idx) { __v.reset(Idx); } + + class iterator { + const EdgeSet &__set; + size_type __current; + + void advance() { + assert(__current != -1); + __current = __set.__v.find_next(__current); + } + + public: + iterator(const EdgeSet &Set, size_type Begin) + : __set{Set}, __current{Begin} {} + iterator operator++(int) { + iterator Tmp = *this; + advance(); + return Tmp; + } + iterator &operator++() { + advance(); + return *this; + } + Edge *operator*() const { + assert(__current != -1); + return __set.__g.edges_begin() + __current; + } + bool operator==(const iterator &other) const { + assert(&this->__set == &other.__set); + return this->__current == other.__current; + } + bool operator!=(const iterator &other) const { return !(*this == other); } + }; + + iterator begin() const { return iterator{*this, __v.find_first()}; } + iterator end() const { return iterator{*this, -1}; } + }; + +private: + Node *__nodes; + size_type __nodes_size; + Edge *__edges; + size_type __edges_size; +}; + +template <typename GraphT> class ImmutableGraphBuilder { + using NodeValueT = typename GraphT::NodeValueT; + using EdgeValueT = typename GraphT::EdgeValueT; + static_assert( + std::is_base_of<ImmutableGraph<NodeValueT, EdgeValueT>, GraphT>::value, + "Template argument to ImmutableGraphBuilder must derive from " + "ImmutableGraph<>"); + using size_type = typename GraphT::size_type; + using NodeSet = typename GraphT::NodeSet; + using Node = typename GraphT::Node; + using EdgeSet = typename GraphT::EdgeSet; + using Edge = typename GraphT::Edge; + using BuilderEdge = std::pair<EdgeValueT, size_type>; + using EdgeList = std::vector<BuilderEdge>; + using BuilderVertex = std::pair<NodeValueT, EdgeList>; + using VertexVec = std::vector<BuilderVertex>; + +public: + using NodeRef = size_type; + + NodeRef addVertex(const NodeValueT &V) { + auto I = __adj_list.emplace(__adj_list.end(), V, EdgeList{}); + return std::distance(__adj_list.begin(), I); + } + + void addEdge(const EdgeValueT &E, NodeRef From, NodeRef To) { + __adj_list[From].second.emplace_back(E, To); + } + + bool empty() const { return __adj_list.empty(); } + + template <typename... ArgT> GraphT *get(ArgT &&... Args) { + size_type VertexSize = __adj_list.size(), EdgeSize = 0; + for (const auto &V : __adj_list) { + EdgeSize += V.second.size(); + } + auto *VertexArray = new Node[VertexSize + 1 /* terminator node */]; + auto *EdgeArray = new Edge[EdgeSize]; + size_type VI = 0, EI = 0; + for (; VI < static_cast<size_type>(__adj_list.size()); ++VI) { + VertexArray[VI].__value = std::move(__adj_list[VI].first); + VertexArray[VI].__edges = &EdgeArray[EI]; + auto NumEdges = static_cast<size_type>(__adj_list[VI].second.size()); + if (NumEdges > 0) { + for (size_type VEI = 0; VEI < NumEdges; ++VEI, ++EI) { + auto &E = __adj_list[VI].second[VEI]; + EdgeArray[EI].__value = std::move(E.first); + EdgeArray[EI].__dest = VertexArray + E.second; + } + } + } + assert(VI == VertexSize && EI == EdgeSize && "Gadget graph malformed"); + VertexArray[VI].__edges = EdgeArray + EdgeSize; // terminator node + return new GraphT{VertexArray, VertexSize, EdgeArray, EdgeSize, + std::forward<ArgT>(Args)...}; + } + + template <typename... ArgT> + static GraphT *trim(const GraphT &G, const NodeSet &TrimNodes, + const EdgeSet &TrimEdges, ArgT &&... Args) { + size_type NewVertexSize = TrimNodes.size() - TrimNodes.count(); + size_type NewEdgeSize = TrimEdges.size() - TrimEdges.count(); + auto *NewVertexArray = new Node[NewVertexSize + 1 /* terminator node */]; + auto *NewEdgeArray = new Edge[NewEdgeSize]; + size_type TrimmedNodesSoFar = 0, + *TrimmedNodes = new size_type[TrimNodes.size()]; + for (size_type I = 0; I < TrimNodes.size(); ++I) { + TrimmedNodes[I] = TrimmedNodesSoFar; + if (TrimNodes.contains(G.nodes_begin() + I)) + ++TrimmedNodesSoFar; + } + size_type VertexI = 0, EdgeI = 0; + for (Node *NI = G.nodes_begin(), *NE = G.nodes_end(); NI != NE; ++NI) { + if (TrimNodes.contains(NI)) + continue; + size_type NewNumEdges = + static_cast<int>((NI + 1)->__edges - NI->__edges) > 0 + ? std::count_if( + NI->__edges, (NI + 1)->__edges, + [&TrimEdges](Edge &E) { return !TrimEdges.contains(&E); }) + : 0; + NewVertexArray[VertexI].__value = NI->__value; + NewVertexArray[VertexI].__edges = &NewEdgeArray[EdgeI]; + if (NewNumEdges > 0) { + for (Edge *EI = NI->__edges, *EE = (NI + 1)->__edges; EI != EE; ++EI) { + if (TrimEdges.contains(EI)) + continue; + NewEdgeArray[EdgeI].__value = EI->__value; + size_type DestIdx = std::distance(G.nodes_begin(), EI->__dest); + size_type NewIdx = DestIdx - TrimmedNodes[DestIdx]; + assert(NewIdx < NewVertexSize); + NewEdgeArray[EdgeI].__dest = NewVertexArray + NewIdx; + ++EdgeI; + } + } + ++VertexI; + } + delete[] TrimmedNodes; + assert(VertexI == NewVertexSize && EdgeI == NewEdgeSize && + "Gadget graph malformed"); + NewVertexArray[VertexI].__edges = NewEdgeArray + NewEdgeSize; + return new GraphT{NewVertexArray, NewVertexSize, NewEdgeArray, NewEdgeSize, + std::forward<ArgT>(Args)...}; + } + +private: + VertexVec __adj_list; +}; + +template <typename NodeValueT, typename EdgeValueT> +struct GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *> { + using GraphT = ImmutableGraph<NodeValueT, EdgeValueT>; + using NodeRef = typename GraphT::Node *; + using EdgeRef = typename GraphT::Edge &; + + static NodeRef edge_dest(EdgeRef E) { return E.__dest; } + using ChildIteratorType = + mapped_iterator<typename GraphT::Edge *, decltype(&edge_dest)>; + + static NodeRef getEntryNode(GraphT *G) { return G->nodes_begin(); } + static ChildIteratorType child_begin(NodeRef N) { + return {N->__edges, &edge_dest}; + } + static ChildIteratorType child_end(NodeRef N) { + return {(N + 1)->__edges, &edge_dest}; + } + + static NodeRef getNode(typename GraphT::Node &N) { return NodeRef{&N}; } + using nodes_iterator = + mapped_iterator<typename GraphT::Node *, decltype(&getNode)>; + static nodes_iterator nodes_begin(GraphT *G) { + return {G->nodes_begin(), &getNode}; + } + static nodes_iterator nodes_end(GraphT *G) { + return {G->nodes_end(), &getNode}; + } + + using ChildEdgeIteratorType = typename GraphT::Edge *; + + static ChildEdgeIteratorType child_edge_begin(NodeRef N) { + return N->__edges; + } + static ChildEdgeIteratorType child_edge_end(NodeRef N) { + return (N + 1)->__edges; + } + static typename GraphT::size_type size(GraphT *G) { return G->nodes_size(); } +}; + +} // end namespace llvm + +#endif // IMMUTABLEGRAPH_H |
