LLVM 19.0.0git
Classes | Namespaces | Typedefs | Functions
GenericDomTree.h File Reference

This file defines a set of templates that efficiently compute a dominator tree over a generic graph. More...

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/CFGDiff.h"
#include "llvm/Support/CFGUpdate.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <memory>
#include <type_traits>
#include <utility>

Go to the source code of this file.

Classes

class  llvm::DomTreeNodeBase< NodeT >
 Base class for the actual dominator tree node. More...
 
struct  llvm::DomTreeNodeTraits< NodeT >
 Default DomTreeNode traits for NodeT. More...
 
class  llvm::DominatorTreeBase< NodeT, IsPostDom >
 Core dominator tree base class. More...
 

Namespaces

namespace  llvm
 This is an optimization pass for GlobalISel generic memory operations.
 
namespace  llvm::DomTreeBuilder
 

Typedefs

template<typename T >
using llvm::DomTreeBase = DominatorTreeBase< T, false >
 
template<typename T >
using llvm::PostDomTreeBase = DominatorTreeBase< T, true >
 

Functions

template<class NodeT >
raw_ostream & llvm::operator<< (raw_ostream &O, const DomTreeNodeBase< NodeT > *Node)
 
template<class NodeT >
void llvm::PrintDomTree (const DomTreeNodeBase< NodeT > *N, raw_ostream &O, unsigned Lev)
 
template<typename DomTreeT >
void llvm::DomTreeBuilder::Calculate (DomTreeT &DT)
 
template<typename DomTreeT >
void llvm::DomTreeBuilder::CalculateWithUpdates (DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
 
template<typename DomTreeT >
void llvm::DomTreeBuilder::InsertEdge (DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
 
template<typename DomTreeT >
void llvm::DomTreeBuilder::DeleteEdge (DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
 
template<typename DomTreeT >
void llvm::DomTreeBuilder::ApplyUpdates (DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
 
template<typename DomTreeT >
bool llvm::DomTreeBuilder::Verify (const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)
 

Detailed Description

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

This is used typically in LLVM for fast dominance queries on the CFG, but is fully generic w.r.t. the underlying graph types.

Unlike ADT/* graph algorithms, generic dominator tree has more requirements on the graph's NodeRef. The NodeRef should be a pointer and, either NodeRef->getParent() must return the parent node that is also a pointer or DomTreeNodeTraits needs to be specialized.

FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.

Definition in file GenericDomTree.h.