LLVM  14.0.0git
Classes | Namespaces
ImmutableGraph.h File Reference
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
Include dependency graph for ImmutableGraph.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  llvm::ImmutableGraph< NodeValueT, EdgeValueT >
 
class  llvm::ImmutableGraph< NodeValueT, EdgeValueT >::Edge
 
class  llvm::ImmutableGraph< NodeValueT, EdgeValueT >::Node
 
class  llvm::ImmutableGraph< NodeValueT, EdgeValueT >::NodeSet
 
class  llvm::ImmutableGraph< NodeValueT, EdgeValueT >::NodeSet::iterator
 
class  llvm::ImmutableGraph< NodeValueT, EdgeValueT >::EdgeSet
 
class  llvm::ImmutableGraph< NodeValueT, EdgeValueT >::EdgeSet::iterator
 
class  llvm::ImmutableGraphBuilder< GraphT >
 
struct  llvm::GraphTraits< ImmutableGraph< NodeValueT, EdgeValueT > * >
 

Namespaces

 llvm
 ---------------------— PointerInfo ------------------------------------—
 

Detailed Description

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.

Definition in file ImmutableGraph.h.