LLVM 17.0.0git
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>
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.

## 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.