FlowGraph Struct Reference

#include <table_flow_graph.h>

Classes
class	BFSPathFinder
	Custom BFS visitor for finding a shortest path between two nodes. More...
struct	DumpTableDetails

Public Types
typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_table_t, const IR::MAU::Table * >, boost::property< boost::edge_annotation_t, cstring > >	Graph

Public Member Functions
	FlowGraph (const FlowGraph &other)
	FlowGraph (FlowGraph &&other)
std::pair< typename Graph::edge_descriptor, bool >	add_edge (const IR::MAU::Table *src, const IR::MAU::Table *dst, const cstring edge_label)
void	add_sink_vertex ()
Graph::vertex_descriptor	add_vertex (const IR::MAU::Table *table)
bool	can_reach (const IR::MAU::Table *t1, const IR::MAU::Table *t2) const
void	clear ()
	Clears the state in this FlowGraph.
void	dump_viz (std::ostream &out, const DumpTableDetails *details=nullptr)
std::vector< const IR::MAU::Table * >	find_path (const IR::MAU::Table *src, const IR::MAU::Table *dst)
const cstring	get_ctrl_dependency_info (typename Graph::edge_descriptor edge) const
const std::set< const IR::MAU::Table * >	get_dominators (const IR::MAU::Table *table) const
const std::set< const IR::MAU::Table * >	get_tables () const
Graph::vertex_descriptor	get_vertex (const IR::MAU::Table *tbl) const
const IR::MAU::Table *	get_vertex (typename Graph::vertex_descriptor v) const
bool	is_always_reached (const IR::MAU::Table *) const
	Determines whether the given table is executed on all paths.
bool	is_empty () const
	Determines whether this graph is empty.
std::vector< const IR::MAU::Table * >	topological_sort () const

Static Public Member Functions
static std::string	viz_node_name (const IR::MAU::Table *tbl)

Public Attributes
std::optional< std::map< const IR::MAU::Table *, std::set< const IR::MAU::Table * > > >	dominators
	The dominator set for each table in the graph. Lazily computed.
bool	emptyFlowGraph = true
Graph	g
	The underlying Boost graph backing this FlowGraph.
std::optional< gress_t >	gress
BFSPathFinder	path_finder
	Helper for find_path.
Reachability< Graph >	reachability
std::set< const IR::MAU::Table * >	tables
	All tables in this graph, excluding the nullptr table, used to represent the sink node.
std::map< const IR::MAU::Table *, typename Graph::vertex_descriptor >	tableToVertex
	Maps each table to its associated graph vertex.
ordered_map< const IR::MAU::Table *, int >	tableToVertexIndex
	Maps each table to its corresponding vertex ID in the Boost graph.
Graph::vertex_descriptor	v_sink
	The sink node, representing the exit point (i.e., entry to the deparser).
Graph::vertex_descriptor	v_source
	The source node, representing the entry point (i.e., entry from the parser).
std::map< typename Graph::vertex_descriptor, const IR::MAU::Table * >	vertexToTable
	Reverse map of above.

Friends
std::ostream &	operator<< (std::ostream &out, const FlowGraph &fg)

Detailed Description

Represents a control-flow graph between the tables in a program, reflecting the logical control flow through the program.

Member Function Documentation

add_edge()

std::pair< typename Graph::edge_descriptor, bool > FlowGraph::add_edge ( const IR::MAU::Table * src, const IR::MAU::Table * dst, const cstring edge_label )

inline

Return an edge descriptor from the given src to the given dst, creating the edge if one doesn't already exist. The returned bool is true when this is a newly-created edge.

add_vertex()

Graph::vertex_descriptor FlowGraph::add_vertex ( const IR::MAU::Table * table )

inline

Returns

the vertex associated with the given table, creating the vertex if one does not already exist.

can_reach()

bool FlowGraph::can_reach ( const IR::MAU::Table * t1, const IR::MAU::Table * t2 ) const

inline

Returns

true iff there is a path in the flow graph from t1 to t2. Passing nullptr for t1 or t2 designates the sink node (consider it the deparser). Tables are not considered reachable from themselves unless they are part of a cycle in the graph.

find_path()

std::vector< const IR::MAU::Table * > FlowGraph::find_path ( const IR::MAU::Table * src, const IR::MAU::Table * dst )

inline

Returns

a path from one table to another. If no path is found, an empty path is returned. If non-empty, the returned path will always contain at least two elements: the src and the dst.

get_ctrl_dependency_info()

const cstring FlowGraph::get_ctrl_dependency_info ( typename Graph::edge_descriptor edge ) const

inline

Returns

the control-flow annotation for the given edge.

get_dominators()

const std::set< const IR::MAU::Table * > FlowGraph::get_dominators

(

const IR::MAU::Table *

table

)

const

Returns

the dominator set of the given table. If the IR is well-formed (i.e., the flow graph is a DAG), then passing nullptr for table will produce the set of tables that are always executed.

get_tables()

const std::set< const IR::MAU::Table * > FlowGraph::get_tables ( ) const

inline

Returns

all tables in this graph.

get_vertex() [1/2]

Graph::vertex_descriptor FlowGraph::get_vertex ( const IR::MAU::Table * tbl ) const

inline

Returns

the vertex in the flow graph corresponding to a Table object.

get_vertex() [2/2]

const IR::MAU::Table * FlowGraph::get_vertex ( typename Graph::vertex_descriptor v ) const

inline

Returns

the table pointer corresponding to a vertex in the flow graph

Friends And Related Symbol Documentation

operator<<

std::ostream & operator<< ( std::ostream & out, const FlowGraph & fg )

friend

Copyright (C) 2024 Intel Corporation

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