#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"

Public Member Functions
	SSAUpdaterImpl (UpdaterT U, AvailableValsTy A, SmallVectorImpl< PhiT * > *Ins)

ValT	GetValue (BlkT *BB)
	GetValue - Check to see if AvailableVals has an entry for the specified BB and if so, return it.

BBInfo *	BuildBlockList (BlkT BB, BlockListTy BlockList)
	BuildBlockList - Starting from the specified basic block, traverse back through its predecessors until reaching blocks with known values.

BBInfo *	IntersectDominators (BBInfo Blk1, BBInfo Blk2)
	IntersectDominators - This is the dataflow lattice "meet" operation for finding dominators.

void	FindDominators (BlockListTy BlockList, BBInfo PseudoEntry)
	FindDominators - Calculate the dominator tree for the subset of the CFG corresponding to the basic blocks on the BlockList.

bool	IsDefInDomFrontier (const BBInfo Pred, const BBInfo IDom)
	IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for any blocks containing definitions of the value.

void	FindPHIPlacement (BlockListTy *BlockList)
	FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of the known definitions.

bool	FindSingularVal (BBInfo *Info)
	Check all predecessors and if all of them have the same AvailableVal use it as value for block represented by Info.

void	FindAvailableVals (BlockListTy *BlockList)
	FindAvailableVal - If this block requires a PHI, first check if an existing PHI matches the PHI placement and reaching definitions computed earlier, and if not, create a new PHI.

void	FindExistingPHI (BlkT BB, BlockListTy BlockList)
	FindExistingPHI - Look through the PHI nodes in a block to see if any of them match what is needed.

bool	CheckIfPHIMatches (PhiT PHI, SmallVectorImpl< BBInfo > &TaggedBlocks)
	CheckIfPHIMatches - Check if a PHI node matches the placement and values in the BBMap.

void	RecordMatchingPHIs (BlockListTy *BlockList)
	RecordMatchingPHIs - For each PHI node that matches, record it in both the BBMap and the AvailableVals mapping.

Detailed Description

template<typename UpdaterT>
class llvm::SSAUpdaterImpl< UpdaterT >

Definition at line 31 of file SSAUpdaterImpl.h.

Constructor & Destructor Documentation

◆ SSAUpdaterImpl()

template<typename UpdaterT >

llvm::SSAUpdaterImpl< UpdaterT >::SSAUpdaterImpl	(	UpdaterT *	U,
		AvailableValsTy *	A,
		SmallVectorImpl< PhiT * > *	Ins
	)

inlineexplicit

Definition at line 86 of file SSAUpdaterImpl.h.

Member Function Documentation

◆ BuildBlockList()

template<typename UpdaterT >

BBInfo * llvm::SSAUpdaterImpl< UpdaterT >::BuildBlockList	(	BlkT *	BB,
		BlockListTy *	BlockList
	)

inline

BuildBlockList - Starting from the specified basic block, traverse back through its predecessors until reaching blocks with known values.

Create BBInfo structures for the blocks and append them to the block list.

Definition at line 116 of file SSAUpdaterImpl.h.

References Allocator, llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorImpl< T >::clear(), E, llvm::SmallVectorBase< Size_T >::empty(), Info, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::GetValue().

◆ CheckIfPHIMatches()

template<typename UpdaterT >

bool llvm::SSAUpdaterImpl< UpdaterT >::CheckIfPHIMatches	(	PhiT *	PHI,
		SmallVectorImpl< BBInfo * > &	TaggedBlocks
	)

inline

CheckIfPHIMatches - Check if a PHI node matches the placement and values in the BBMap.

Definition at line 427 of file SSAUpdaterImpl.h.

References Cleanup, E, I, llvm::make_scope_exit(), PHI, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::FindExistingPHI().

◆ FindAvailableVals()

template<typename UpdaterT >

void llvm::SSAUpdaterImpl< UpdaterT >::FindAvailableVals ( BlockListTy * BlockList )

inline

FindAvailableVal - If this block requires a PHI, first check if an existing PHI matches the PHI placement and reaching definitions computed earlier, and if not, create a new PHI.

Visit all the block's predecessors to calculate the available value for each one and fill in the incoming values for a new PHI.

Definition at line 353 of file SSAUpdaterImpl.h.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dbgs(), E, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SSAUpdaterImpl< UpdaterT >::FindExistingPHI(), llvm::SSAUpdaterImpl< UpdaterT >::FindSingularVal(), I, Info, LLVM_DEBUG, PHI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateCommon< T, typename >::rbegin(), and llvm::SmallVectorTemplateCommon< T, typename >::rend().

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::GetValue().

◆ FindDominators()

template<typename UpdaterT >

void llvm::SSAUpdaterImpl< UpdaterT >::FindDominators	(	BlockListTy *	BlockList,
		BBInfo *	PseudoEntry
	)

inline

FindDominators - Calculate the dominator tree for the subset of the CFG corresponding to the basic blocks on the BlockList.

This uses the algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey and Kennedy, published in Software–Practice and Experience, 2001, 4:1-10. Because the CFG subset does not include any edges leading into blocks that define the value, the results are not the usual dominator tree. The CFG subset has a single pseudo-entry node with edges to a set of root nodes for blocks that define the value. The dominators for this subset CFG are not the standard dominators but they are adequate for placing PHIs within the subset CFG.

Definition at line 240 of file SSAUpdaterImpl.h.

References E, I, Info, llvm::SSAUpdaterImpl< UpdaterT >::IntersectDominators(), llvm::SmallVectorTemplateCommon< T, typename >::rbegin(), and llvm::SmallVectorTemplateCommon< T, typename >::rend().

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::GetValue().

◆ FindExistingPHI()

template<typename UpdaterT >

void llvm::SSAUpdaterImpl< UpdaterT >::FindExistingPHI	(	BlkT *	BB,
		BlockListTy *	BlockList
	)

inline

FindExistingPHI - Look through the PHI nodes in a block to see if any of them match what is needed.

Definition at line 415 of file SSAUpdaterImpl.h.

References llvm::SSAUpdaterImpl< UpdaterT >::CheckIfPHIMatches(), and llvm::SSAUpdaterImpl< UpdaterT >::RecordMatchingPHIs().

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::FindAvailableVals().

◆ FindPHIPlacement()

template<typename UpdaterT >

void llvm::SSAUpdaterImpl< UpdaterT >::FindPHIPlacement ( BlockListTy * BlockList )

inline

FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of the known definitions.

Iteratively add PHIs in the dom frontiers until nothing changes. Along the way, keep track of the nearest dominating definitions for non-PHI blocks.

Definition at line 294 of file SSAUpdaterImpl.h.

References E, I, Info, llvm::SSAUpdaterImpl< UpdaterT >::IsDefInDomFrontier(), llvm::SmallVectorTemplateCommon< T, typename >::rbegin(), and llvm::SmallVectorTemplateCommon< T, typename >::rend().

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::GetValue().

◆ FindSingularVal()

template<typename UpdaterT >

bool llvm::SSAUpdaterImpl< UpdaterT >::FindSingularVal ( BBInfo * Info )

inline

Check all predecessors and if all of them have the same AvailableVal use it as value for block represented by Info.

Return true if singluar value is found.

Definition at line 329 of file SSAUpdaterImpl.h.

References assert(), Idx, and Info.

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::FindAvailableVals().

◆ GetValue()

template<typename UpdaterT >

ValT llvm::SSAUpdaterImpl< UpdaterT >::GetValue ( BlkT * BB )

inline

GetValue - Check to see if AvailableVals has an entry for the specified BB and if so, return it.

If not, construct SSA form by first calculating the required placement of PHIs and then inserting new PHIs where needed.

Definition at line 94 of file SSAUpdaterImpl.h.

References llvm::SSAUpdaterImpl< UpdaterT >::BuildBlockList(), llvm::SSAUpdaterImpl< UpdaterT >::FindAvailableVals(), llvm::SSAUpdaterImpl< UpdaterT >::FindDominators(), llvm::SSAUpdaterImpl< UpdaterT >::FindPHIPlacement(), and llvm::SmallVectorBase< Size_T >::size().

◆ IntersectDominators()

template<typename UpdaterT >

BBInfo * llvm::SSAUpdaterImpl< UpdaterT >::IntersectDominators	(	BBInfo *	Blk1,
		BBInfo *	Blk2
	)

inline

IntersectDominators - This is the dataflow lattice "meet" operation for finding dominators.

Given two basic blocks, it walks up the dominator tree until it finds a common dominator of both. It uses the postorder number of the blocks to determine how to do that.

Definition at line 214 of file SSAUpdaterImpl.h.

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::FindDominators().

◆ IsDefInDomFrontier()

template<typename UpdaterT >

bool llvm::SSAUpdaterImpl< UpdaterT >::IsDefInDomFrontier	(	const BBInfo *	Pred,
		const BBInfo *	IDom
	)

inline

IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for any blocks containing definitions of the value.

If one is found, then the successor of Pred is in the dominance frontier for the definition, and this function returns true.

Definition at line 282 of file SSAUpdaterImpl.h.

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::FindPHIPlacement().

◆ RecordMatchingPHIs()

template<typename UpdaterT >

void llvm::SSAUpdaterImpl< UpdaterT >::RecordMatchingPHIs ( BlockListTy * BlockList )

inline

RecordMatchingPHIs - For each PHI node that matches, record it in both the BBMap and the AvailableVals mapping.

Definition at line 487 of file SSAUpdaterImpl.h.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), E, llvm::SmallVectorTemplateCommon< T, typename >::end(), I, and PHI.

Referenced by llvm::SSAUpdaterImpl< UpdaterT >::FindExistingPHI().

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

include/llvm/Transforms/Utils/SSAUpdaterImpl.h

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ SSAUpdaterImpl()

Member Function Documentation

◆ BuildBlockList()

◆ CheckIfPHIMatches()

◆ FindAvailableVals()

◆ FindDominators()

◆ FindExistingPHI()

◆ FindPHIPlacement()

◆ FindSingularVal()

◆ GetValue()

◆ IntersectDominators()

◆ IsDefInDomFrontier()

◆ RecordMatchingPHIs()