#include <dominator_tree.h>

Inheritance diagram for BuildDominatorTree:

Public Types
using	G = FlowGraph::Graph

using	ImmediateDominatorMap = ordered_map<const IR::MAU::Table , const IR::MAU::Table >
	map[x] = y, means that table y is the immediate dominator for table x.

using	IndexMap = boost::property_map<G, boost::vertex_index_t>::type

using	PredMap = boost::iterator_property_map<std::vector<Vertex>::iterator, IndexMap>

using	Vertex = boost::graph_traits<G>::vertex_descriptor

Public Types inherited from P4::Visitor
typedef Visitor_Context	Context

Public Member Functions
	BuildDominatorTree (ordered_map< gress_t, FlowGraph > &fg)

const std::vector< const IR::MAU::Table * >	getAllDominators (const IR::MAU::Table *t, gress_t gress) const

const ordered_map< gress_t, FlowGraph > &	getFlowGraph () const

std::optional< const IR::MAU::Table * >	getImmediateDominator (const IR::MAU::Table *t, gress_t gress) const

const IR::MAU::Table *	getNonGatewayGroupDominator (ordered_set< const IR::MAU::Table * > &tables) const

std::optional< const IR::MAU::Table * >	getNonGatewayImmediateDominator (const IR::MAU::Table *t, gress_t gress) const

cstring	hasImmediateDominator (gress_t g, cstring t) const
	GTest methods.

bool	isDominator (cstring t1, gress_t gress, cstring t2) const

void	setupDomTree ()

bool	strictlyDominates (const IR::BFN::Unit u1, const IR::BFN::Unit u2) const

bool	strictlyDominates (const IR::MAU::Table t1, const IR::MAU::Table t2) const

bool	strictlyDominates (cstring t1, cstring t2, gress_t gress) const

Public Member Functions inherited from P4::Inspector
const IR::Node *	apply_visitor (const IR::Node , const char name=0) override

profile_t	init_apply (const IR::Node *root) override

virtual void	loop_revisit (const IR::Node *)

virtual void	postorder (const IR::Node *)

virtual bool	preorder (const IR::Node *)

virtual void	revisit (const IR::Node *)

void	revisit_visited ()

bool	visit_in_progress (const IR::Node *n) const

void	visitAgain () const override

void	visitOnce () const override

Public Member Functions inherited from P4::Visitor
virtual bool	check_global (cstring)

virtual void	clear_globals ()

virtual Visitor *	clone () const

virtual ControlFlowVisitor *	controlFlowVisitor ()

virtual void	end_apply ()

virtual void	end_apply (const IR::Node *root)

virtual void	erase_global (cstring)

template<class T >
const T *	findContext () const

template<class T >
const T *	findContext (const Context *&c) const

template<class T >
const T *	findOrigCtxt () const

template<class T >
const T *	findOrigCtxt (const Context *&c) const

virtual Visitor &	flow_clone ()

virtual void	flow_merge (Visitor &)

virtual bool	flow_merge_closure (Visitor &)

virtual void	flow_merge_global_from (cstring)

virtual void	flow_merge_global_to (cstring)

const Context *	getChildContext () const

int	getChildrenVisited () const

const Context *	getContext () const

int	getContextDepth () const

const IR::Node *	getCurrentNode () const

template<class T >
const T *	getCurrentNode () const

const IR::Node *	getOriginal () const

template<class T >
const T *	getOriginal () const

template<class T >
const T *	getParent () const

virtual bool	has_flow_joins () const

profile_t	init_apply (const IR::Node root, const Context parent_context)

bool	isInContext (const IR::Node *n) const

virtual const char *	name () const

template<class T >
void	parallel_visit (const IR::Vector< T > &v, const char *name, int cidx)

template<class T >
void	parallel_visit (const IR::Vector< T > &v, const char *name=0)

template<class T >
void	parallel_visit (IR::Vector< T > &v, const char *name, int cidx)

template<class T >
void	parallel_visit (IR::Vector< T > &v, const char *name=0)

void	print_context () const

const Visitor &	setCalledBy (const Visitor *visitor)

void	setName (const char *name)

void	visit (const IR::Node &n, const char *name, int cidx)

void	visit (const IR::Node &n, const char *name=0)

void	visit (const IR::Node &n, const char name, int cidx)

void	visit (const IR::Node &n, const char name=0)

void	visit (const IR::Node const &n, const char name, int cidx)

void	visit (const IR::Node const &n, const char name=0)

void	visit (IR::Node &n, const char *name, int cidx)

void	visit (IR::Node &n, const char *name=0)

void	visit (IR::Node &, const char =0, int=0)

template<class T , typename = std::enable_if_t<Util::has_SourceInfo_v<T> && !std::is_pointer_v<T>>, class... Args>
void	warn (const int kind, const char *format, const T &node, Args &&...args)
	The const ref variant of the above.

template<class T , typename = std::enable_if_t<Util::has_SourceInfo_v<T>>, class... Args>
void	warn (const int kind, const char format, const T node, Args &&...args)

bool	warning_enabled (int warning_kind) const

Additional Inherited Members
Static Public Member Functions inherited from P4::Visitor
static cstring	demangle (const char *)

static bool	warning_enabled (const Visitor *visitor, int warning_kind)

Public Attributes inherited from P4::Visitor
const Visitor *	called_by = nullptr

cstring	internalName

SplitFlowVisit_base *&	split_link

SplitFlowVisit_base *	split_link_mem = nullptr

Protected Member Functions inherited from P4::Visitor
virtual void	init_join_flows (const IR::Node *)

virtual bool	join_flows (const IR::Node *)

virtual void	post_join_flows (const IR::Node , const IR::Node )

void	visit_children (const IR::Node *, std::function< void()> fn)

Protected Attributes inherited from P4::Visitor
bool	dontForwardChildrenBeforePreorder = false

bool	joinFlows = false

bool	visitDagOnce = true

Detailed Description

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

SPDX-License-Identifier: Apache-2.0 This class builds an immediate dominator tree using separate table flow graphs for ingress and egress. This class uses the Lengauer-Tarjan dominator tree algorithm offered by boost. This class maintains a map of table pointers, so must be rerun every time new table objects are created (e.g. through gateway merge) and the associated flow graphs must be re-computed accordingly.

Member Function Documentation

◆ getAllDominators()

const std::vector< const IR::MAU::Table * > BuildDominatorTree::getAllDominators	(	const IR::MAU::Table *	t,
		gress_t	gress ) const

Returns: a vector of tables that strictly dominate the give table t.

◆ getFlowGraph()

const ordered_map< gress_t, FlowGraph > & BuildDominatorTree::getFlowGraph ( ) const

inline

Returns: the flow graph associated with each gress in the program

◆ getImmediateDominator()

std::optional< const IR::MAU::Table * > BuildDominatorTree::getImmediateDominator	(	const IR::MAU::Table *	t,
		gress_t	gress ) const

Returns: the immediate dominator table for t with gress.; std::nullopt if there is no immediate dominator. If t is nullptr, then it indicates the deparser, in which case the gress needs to be specified.

◆ getNonGatewayGroupDominator()

const IR::MAU::Table * BuildDominatorTree::getNonGatewayGroupDominator ( ordered_set< const IR::MAU::Table * > & tables ) const

Returns: the lowest common ancestor (group dominator) for the group of tables in tables.

◆ getNonGatewayImmediateDominator()

std::optional< const IR::MAU::Table * > BuildDominatorTree::getNonGatewayImmediateDominator	(	const IR::MAU::Table *	t,
		gress_t	gress ) const

Returns: the non gateway immediate dominator for t belonging to gress.; std::nullopt if there is no non-gateway immediate dominator. If t is nullptr, then it indicates the deparser, in which case the gress needs to be specified.

◆ hasImmediateDominator()

cstring BuildDominatorTree::hasImmediateDominator	(	gress_t	g,
		cstring	t ) const

GTest methods.

Used exclusively for gtests. Returns the immediate dominator of the table with name t and gress g. Returns empty string if no dominator present.

◆ isDominator()

bool BuildDominatorTree::isDominator	(	cstring	t1,
		gress_t	gress,
		cstring	t2 ) const

Used exclusively for gtests. Return true if the table with name t2 and gress is a dominator of table with name t1.

◆ strictlyDominates() [1/3]

bool BuildDominatorTree::strictlyDominates	(	const IR::BFN::Unit *	u1,
		const IR::BFN::Unit *	u2 ) const

Returns: true if the unit u1 strictly dominates unit u2.

◆ strictlyDominates() [2/3]

bool BuildDominatorTree::strictlyDominates	(	const IR::MAU::Table *	t1,
		const IR::MAU::Table *	t2 ) const

Returns: true if the table t1 strictly dominates table t2.

◆ strictlyDominates() [3/3]

bool BuildDominatorTree::strictlyDominates	(	cstring	t1,
		cstring	t2,
		gress_t	gress ) const

Used exclusively for gtests. Returns true if the table with name t1 strictly dominates the table with name t2 for gress.

Public Types

Public Member Functions

Additional Inherited Members