llvm::IDFCalculatorBase< NodeTy, IsPostDom > Class Template Reference

Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks. More...

#include "llvm/Support/GenericIteratedDominanceFrontier.h"

Inheritance diagram for llvm::IDFCalculatorBase< NodeTy, IsPostDom >:

Public Types
using	OrderedNodeTy = std::conditional_t< IsPostDom, Inverse< NodeTy * >, NodeTy * >
using	ChildrenGetterTy = IDFCalculatorDetail::ChildrenGetterTy< NodeTy, IsPostDom >

Public Member Functions
	IDFCalculatorBase (DominatorTreeBase< NodeTy, IsPostDom > &DT)
	IDFCalculatorBase (DominatorTreeBase< NodeTy, IsPostDom > &DT, const ChildrenGetterTy &C)
void	setDefiningBlocks (const SmallPtrSetImpl< NodeTy * > &Blocks)
	Give the IDF calculator the set of blocks in which the value is defined.
void	setLiveInBlocks (const SmallPtrSetImpl< NodeTy * > &Blocks)
	Give the IDF calculator the set of blocks in which the value is live on entry to the block.
void	resetLiveInBlocks ()
	Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.
void	calculate (SmallVectorImpl< NodeTy * > &IDFBlocks)
	Calculate iterated dominance frontiers.

Detailed Description

template<class NodeTy, bool IsPostDom>
class llvm::IDFCalculatorBase< NodeTy, IsPostDom >

Determine the iterated dominance frontier, given a set of defining blocks, and optionally, a set of live-in blocks.

In turn, the results can be used to place phi nodes.

This algorithm is a linear time computation of Iterated Dominance Frontiers, pruned using the live-in set. By default, liveness is not used to prune the IDF computation. The template parameters should be of a CFG block type.

Definition at line 58 of file GenericIteratedDominanceFrontier.h.

Member Typedef Documentation

ChildrenGetterTy

template<class NodeTy , bool IsPostDom>

using llvm::IDFCalculatorBase< NodeTy, IsPostDom >::ChildrenGetterTy = IDFCalculatorDetail::ChildrenGetterTy<NodeTy, IsPostDom>

Definition at line 62 of file GenericIteratedDominanceFrontier.h.

OrderedNodeTy

template<class NodeTy , bool IsPostDom>

using llvm::IDFCalculatorBase< NodeTy, IsPostDom >::OrderedNodeTy = std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>

Definition at line 60 of file GenericIteratedDominanceFrontier.h.

Constructor & Destructor Documentation

IDFCalculatorBase() [1/2]

template<class NodeTy , bool IsPostDom>

llvm::IDFCalculatorBase< NodeTy, IsPostDom >::IDFCalculatorBase ( DominatorTreeBase< NodeTy, IsPostDom > &  DT )

inline

Definition at line 65 of file GenericIteratedDominanceFrontier.h.

IDFCalculatorBase() [2/2]

template<class NodeTy , bool IsPostDom>

llvm::IDFCalculatorBase< NodeTy, IsPostDom >::IDFCalculatorBase ( DominatorTreeBase< NodeTy, IsPostDom > &  DT, const ChildrenGetterTy &  C  )

inline

Definition at line 67 of file GenericIteratedDominanceFrontier.h.

Member Function Documentation

calculate()

template<class NodeTy , bool IsPostDom>

void llvm::IDFCalculatorBase< NodeTy, IsPostDom >::calculate

(

SmallVectorImpl< NodeTy * > &

IDFBlocks

)

Calculate iterated dominance frontiers.

This uses the linear-time phi algorithm based on DJ-graphs mentioned in the file-level comment. It performs DF->IDF pruning using the live-in set, to avoid computing the IDF for blocks where an inserted PHI node would be dead.

Definition at line 131 of file GenericIteratedDominanceFrontier.h.

References assert(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeNodeBase< NodeT >::getDFSNumIn(), llvm::DomTreeNodeBase< NodeT >::getLevel(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallPtrSetImplBase::reserve().

Referenced by llvm::MemorySSAUpdater::insertDef(), and llvm::SSAUpdaterBulk::RewriteAllUses().

resetLiveInBlocks()

template<class NodeTy , bool IsPostDom>

void llvm::IDFCalculatorBase< NodeTy, IsPostDom >::resetLiveInBlocks ( )

inline

Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.

Definition at line 92 of file GenericIteratedDominanceFrontier.h.

Referenced by llvm::SSAUpdaterBulk::RewriteAllUses().

setDefiningBlocks()

template<class NodeTy , bool IsPostDom>

void llvm::IDFCalculatorBase< NodeTy, IsPostDom >::setDefiningBlocks ( const SmallPtrSetImpl< NodeTy * > &  Blocks )

inline

Give the IDF calculator the set of blocks in which the value is defined.

This is equivalent to the set of starting blocks it should be calculating the IDF for (though later gets pruned based on liveness).

Note: This set must live for the entire lifetime of the IDF calculator.

Definition at line 76 of file GenericIteratedDominanceFrontier.h.

References Blocks.

Referenced by llvm::MemorySSAUpdater::insertDef(), and llvm::SSAUpdaterBulk::RewriteAllUses().

setLiveInBlocks()

template<class NodeTy , bool IsPostDom>

void llvm::IDFCalculatorBase< NodeTy, IsPostDom >::setLiveInBlocks ( const SmallPtrSetImpl< NodeTy * > &  Blocks )

inline

Give the IDF calculator the set of blocks in which the value is live on entry to the block.

This is used to prune the IDF calculation to not include blocks where any phi insertion would be dead.

Note: This set must live for the entire lifetime of the IDF calculator.

Definition at line 85 of file GenericIteratedDominanceFrontier.h.

References Blocks.

Referenced by llvm::SSAUpdaterBulk::RewriteAllUses().

---

The documentation for this class was generated from the following file:

• include/llvm/Support/GenericIteratedDominanceFrontier.h