LLVM: llvm::bfi_detail::IrreducibleGraph Struct Reference

LLVM 20.0.0git

Graph of irreducible control flow. More...

#include "llvm/Analysis/BlockFrequencyInfoImpl.h"

Classes
struct	IrrNode

Public Types
using	BFIBase = BlockFrequencyInfoImplBase

using	BlockNode = BFIBase::BlockNode

Public Member Functions
template<class BlockEdgesAdder >
	IrreducibleGraph (BFIBase &BFI, const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)
	Construct an explicit graph containing irreducible control flow.

template<class BlockEdgesAdder >
void	initialize (const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)

void	addNodesInLoop (const BFIBase::LoopData &OuterLoop)

void	addNodesInFunction ()

void	addNode (const BlockNode &Node)

void	indexNodes ()

template<class BlockEdgesAdder >
void	addEdges (const BlockNode &Node, const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)

void	addEdge (IrrNode &Irr, const BlockNode &Succ, const BFIBase::LoopData *OuterLoop)

Public Attributes
BFIBase &	BFI

BlockNode	Start

const IrrNode *	StartIrr = nullptr

std::vector< IrrNode >	Nodes

SmallDenseMap< uint32_t, IrrNode *, 4 >	Lookup

Detailed Description

Graph of irreducible control flow.

This graph is used for determining the SCCs in a loop (or top-level function) that has irreducible control flow.

During the block frequency algorithm, the local graphs are defined in a light-weight way, deferring to the BasicBlock or MachineBasicBlock graphs for most edges, but getting others from LoopData::ExitMap. The latter only has successor information.

IrreducibleGraph makes this graph explicit. It's in a form that can use GraphTraits (so that analyzeIrreducible() can use scc_iterator), and it explicitly lists predecessors and successors. The initialization that relies on MachineBasicBlock is defined in the header.

Definition at line 599 of file BlockFrequencyInfoImpl.h.

Member Typedef Documentation

◆ BFIBase

using llvm::bfi_detail::IrreducibleGraph::BFIBase = BlockFrequencyInfoImplBase

Definition at line 600 of file BlockFrequencyInfoImpl.h.

◆ BlockNode

using llvm::bfi_detail::IrreducibleGraph::BlockNode = BFIBase::BlockNode

Definition at line 604 of file BlockFrequencyInfoImpl.h.

Constructor & Destructor Documentation

◆ IrreducibleGraph()

template<class BlockEdgesAdder >

llvm::bfi_detail::IrreducibleGraph::IrreducibleGraph	(	BFIBase &	BFI,
		const BFIBase::LoopData *	OuterLoop,
		BlockEdgesAdder	addBlockEdges
	)

inline

Construct an explicit graph containing irreducible control flow.

Construct an explicit graph of the control flow in OuterLoop (or the top-level function, if OuterLoop is nullptr). Uses addBlockEdges to add block successors that have not been packaged into loops.

BlockFrequencyInfoImpl::computeIrreducibleMass() is the only expected user of this.

Definition at line 634 of file BlockFrequencyInfoImpl.h.

References initialize().

Member Function Documentation

◆ addEdge()

void IrreducibleGraph::addEdge	(	IrrNode &	Irr,
		const BlockNode &	Succ,
		const BFIBase::LoopData *	OuterLoop
	)

Definition at line 658 of file BlockFrequencyInfoImpl.cpp.

References llvm::bfi_detail::IrreducibleGraph::IrrNode::Edges, llvm::BlockFrequencyInfoImplBase::BlockNode::Index, llvm::BlockFrequencyInfoImplBase::LoopData::isHeader(), Lookup, and llvm::bfi_detail::IrreducibleGraph::IrrNode::NumIn.

Referenced by addEdges().

◆ addEdges()

template<class BlockEdgesAdder >

void llvm::bfi_detail::IrreducibleGraph::addEdges	(	const BlockNode &	Node,
		const BFIBase::LoopData *	OuterLoop,
		BlockEdgesAdder	addBlockEdges
	)

Definition at line 674 of file BlockFrequencyInfoImpl.h.

References addEdge(), BFI, I, Lookup, and llvm::BlockFrequencyInfoImplBase::Working.

Referenced by initialize().

◆ addNode()

void llvm::bfi_detail::IrreducibleGraph::addNode ( const BlockNode & Node )

inline

Definition at line 645 of file BlockFrequencyInfoImpl.h.

References BFI, llvm::bfi_detail::BlockMass::getEmpty(), Nodes, and llvm::BlockFrequencyInfoImplBase::Working.

Referenced by addNodesInFunction(), and addNodesInLoop().

◆ addNodesInFunction()

void IrreducibleGraph::addNodesInFunction ( )

Definition at line 645 of file BlockFrequencyInfoImpl.cpp.

References addNode(), BFI, indexNodes(), Start, and llvm::BlockFrequencyInfoImplBase::Working.

Referenced by initialize().

◆ addNodesInLoop()

void IrreducibleGraph::addNodesInLoop ( const BFIBase::LoopData & OuterLoop )

Definition at line 637 of file BlockFrequencyInfoImpl.cpp.

References addNode(), llvm::BlockFrequencyInfoImplBase::LoopData::getHeader(), indexNodes(), N, llvm::BlockFrequencyInfoImplBase::LoopData::Nodes, Nodes, llvm::SmallVectorBase< Size_T >::size(), and Start.

Referenced by initialize().

◆ indexNodes()

void IrreducibleGraph::indexNodes ( )

Definition at line 653 of file BlockFrequencyInfoImpl.cpp.

References I, Lookup, and Nodes.

Referenced by addNodesInFunction(), and addNodesInLoop().

◆ initialize()

template<class BlockEdgesAdder >

void llvm::bfi_detail::IrreducibleGraph::initialize	(	const BFIBase::LoopData *	OuterLoop,
		BlockEdgesAdder	addBlockEdges
	)

Definition at line 659 of file BlockFrequencyInfoImpl.h.

References addEdges(), addNodesInFunction(), addNodesInLoop(), BFI, llvm::BlockFrequencyInfoImplBase::BlockNode::Index, Lookup, N, llvm::BlockFrequencyInfoImplBase::LoopData::Nodes, Start, StartIrr, and llvm::BlockFrequencyInfoImplBase::Working.

Referenced by IrreducibleGraph().

Member Data Documentation

◆ BFI

BFIBase& llvm::bfi_detail::IrreducibleGraph::BFI

Definition at line 602 of file BlockFrequencyInfoImpl.h.

Referenced by addEdges(), addNode(), addNodesInFunction(), and initialize().

◆ Lookup

SmallDenseMap<uint32_t, IrrNode *, 4> llvm::bfi_detail::IrreducibleGraph::Lookup

Definition at line 622 of file BlockFrequencyInfoImpl.h.

Referenced by addEdge(), addEdges(), indexNodes(), and initialize().

◆ Nodes

std::vector<IrrNode> llvm::bfi_detail::IrreducibleGraph::Nodes

Definition at line 621 of file BlockFrequencyInfoImpl.h.

Referenced by addNode(), addNodesInLoop(), and indexNodes().

◆ Start

BlockNode llvm::bfi_detail::IrreducibleGraph::Start

Definition at line 619 of file BlockFrequencyInfoImpl.h.

Referenced by addNodesInFunction(), addNodesInLoop(), and initialize().

◆ StartIrr

const IrrNode* llvm::bfi_detail::IrreducibleGraph::StartIrr = nullptr

Definition at line 620 of file BlockFrequencyInfoImpl.h.

Referenced by initialize().

The documentation for this struct was generated from the following files:

include/llvm/Analysis/BlockFrequencyInfoImpl.h
lib/Analysis/BlockFrequencyInfoImpl.cpp