ImmutableGraph.h File Reference

Description: ImmutableGraph is a fast DAG implementation that cannot be modified, except by creating a new ImmutableGraph. More...

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

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
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

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.