llvm/llvm/lib/Target/X86/ImmutableGraph.h

//==========-- 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
//
//===----------------------------------------------------------------------===//
/// \file
/// 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 benefit from cache locality.
/// 2. Operations on sets of nodes/edges are efficient, and representations of
///    those sets in memory are compact. 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 spatial 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 LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H
#define LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H

#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

namespace llvm {

template <typename NodeValueT, typename EdgeValueT> class ImmutableGraph { … };

template <typename GraphT> class ImmutableGraphBuilder { … };

GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *>;

} // end namespace llvm

#endif // LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H