LLVM 19.0.0git
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
llvm::bfi_detail::IrreducibleGraph Struct Reference

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

BFIBaseBFI
 
BlockNode Start
 
const IrrNodeStartIrr = nullptr
 
std::vector< IrrNodeNodes
 
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

Definition at line 600 of file BlockFrequencyInfoImpl.h.

◆ 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 
)

◆ 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

◆ addNodesInFunction()

void IrreducibleGraph::addNodesInFunction ( )

◆ addNodesInLoop()

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

◆ 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 
)

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: