Classes
struct	StageInfo

Public Types
enum	dependencies_t { NONE = 1 , CONTROL_ACTION = (1 << 1) , CONTROL_COND_TRUE = (1 << 2) , CONTROL_COND_FALSE = (1 << 3) , CONTROL_TABLE_HIT = (1 << 4) , CONTROL_TABLE_MISS = (1 << 5) , CONTROL_DEFAULT_NEXT_TABLE = (1 << 6) , CONTROL_EXIT = (1 << 19) , IXBAR_READ = (1 << 7) , ACTION_READ = (1 << 8) , OUTPUT = (1 << 9) , REDUCTION_OR_READ = (1 << 10) , REDUCTION_OR_OUTPUT = (1 << 11) , CONT_CONFLICT = (1 << 12) , ANTI_EXIT = (1 << 13) , ANTI_TABLE_READ = (1 << 14) , ANTI_ACTION_READ = (1 << 15) , ANTI_NEXT_TABLE_DATA = (1 << 16) , ANTI_NEXT_TABLE_CONTROL = (1 << 17) , ANTI_NEXT_TABLE_METADATA = (1 << 18) , CONCURRENT = 0 }

typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_table_t, const IR::MAU::Table * >, dependencies_t >	Graph

enum	mau_dependencies_t { MAU_DEP_MATCH = 2 , MAU_DEP_ACTION = 1 , MAU_DEP_CONCURRENT = 0 }

using	MinEdgeInfo = std::pair<const IR::MAU::Table *, dependencies_t>

Public Member Functions
std::pair< typename Graph::edge_descriptor *, bool >	add_edge (const IR::MAU::Table src, const IR::MAU::Table dst, dependencies_t edge_label)

Graph::vertex_descriptor	add_vertex (const IR::MAU::Table *label)

void	clear ()

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

TableGraphNode	create_node (const int id, const IR::MAU::Table *tbl) const

int	critical_path_length () const

int	dependence_tail_size (const IR::MAU::Table *t) const

int	dependence_tail_size_control (const IR::MAU::Table *t) const

int	dependence_tail_size_control_anti (const IR::MAU::Table *t) const

int	dependence_tail_size_control_anti_split (const IR::MAU::Table *t) const

void	fill_dep_stages_from_topo (const std::vector< ordered_set< DependencyGraph::Graph::vertex_descriptor > > &topo, bool include_stages, const TableSummary *summary)

DependencyGraph::mau_dependencies_t	find_mau_dependency (const IR::MAU::Table from, const IR::MAU::Table to)

std::optional< std::string >	get_ctrl_dependency_info (typename Graph::edge_descriptor edge) const

std::optional< ordered_map< std::pair< const PHV::Field , DependencyGraph::dependencies_t >, std::pair< ordered_set< const IR::MAU::Action >, ordered_set< const IR::MAU::Action * > > > >	get_data_dependency_info (const IR::MAU::Table upstream, const IR::MAU::Table downstream) const

std::optional< ordered_map< const PHV::Field , std::pair< ordered_set< const IR::MAU::Action >, ordered_set< const IR::MAU::Action * > > > >	get_data_dependency_info (typename Graph::edge_descriptor edge) const

DependencyGraph::dependencies_t	get_dependency (const IR::MAU::Table t1, const IR::MAU::Table t2) const

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

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

const std::vector< const IR::MAU::Table * > &	happens_before_dependences (const IR::MAU::Table *t) const

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

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

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

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

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

bool	happens_phys_before_recursive (const IR::MAU::Table t1, const IR::MAU::TableSeq s) const

bool	has_back_edge (const IR::MAU::Table src, const IR::MAU::Table dst)

bool	has_cycle ()

bool	is_anti_edge (DependencyGraph::dependencies_t dep) const

bool	is_ctrl_edge (DependencyGraph::dependencies_t dep) const

bool	is_edge_critical (typename Graph::edge_descriptor e) const

bool	is_non_directional_edge (DependencyGraph::dependencies_t dep) const

int	max_stage (const IR::MAU::Table *t) const

int	min_stage (const IR::MAU::Table *t) const

void	print_container_access (std::ostream &out) const

void	print_dep_type_map (std::ostream &out) const

void	to_json (Util::JsonObject *dgJson, const FlowGraph &fg, cstring passContext, bool placed)

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

Static Public Member Functions
static cstring	dep_to_name (dependencies_t dep)

static void	dump_viz (std::ostream &out, const DependencyGraph &dg)

static dependencies_t	get_control_edge_type (cstring annot)

Public Attributes
ordered_map< const IR::MAU::Table , ordered_set< const IR::MAU::Table > >	container_conflicts

std::map< const IR::MAU::Table *, std::map< const PHV::Container, bool > >	containers_read_alu_

std::map< const IR::MAU::Table *, std::map< const PHV::Container, bool > >	containers_read_xbar_

std::map< const IR::MAU::Table *, std::map< const PHV::Container, bool > >	containers_write_ = {}

ordered_map< typename Graph::edge_descriptor, std::string >	ctrl_annotations

ordered_map< typename Graph::edge_descriptor, ordered_map< const PHV::Field , std::pair< ordered_set< const IR::MAU::Action >, ordered_set< const IR::MAU::Action * > > > >	data_annotations

ordered_map< typename Graph::edge_descriptor, const PHV::Container >	data_annotations_conflicts

ordered_map< typename Graph::edge_descriptor, const std::vector< const IR::MAU::Action * > >	data_annotations_exit

ordered_map< typename Graph::edge_descriptor, const PHV::FieldSlice * >	data_annotations_metadata

ordered_map< const IR::MAU::Table , ordered_map< const IR::MAU::Table , dependencies_t > >	dep_type_map

ordered_map< std::pair< const IR::MAU::Table , const IR::MAU::Table >, DependencyGraph::dependencies_t >	dependency_map

bool	display_min_edges = false

bool	finalized

Graph	g

ordered_map< const IR::MAU::Table , std::vector< const IR::MAU::Table > >	happens_after_work_map

ordered_map< const IR::MAU::Table , ordered_set< const IR::MAU::Table > >	happens_before_control_map

ordered_map< const IR::MAU::Table , std::vector< const IR::MAU::Table > >	happens_before_work_map

ordered_map< const IR::MAU::Table , ordered_set< const IR::MAU::Table > >	happens_logi_after_map

ordered_map< const IR::MAU::Table , ordered_set< const IR::MAU::Table > >	happens_logi_before_map

ordered_map< const IR::MAU::Table , ordered_set< const IR::MAU::Table > >	happens_phys_after_map

ordered_map< const IR::MAU::Table , ordered_set< const IR::MAU::Table > >	happens_phys_before_map

ordered_map< const IR::MAU::Table *, typename Graph::vertex_descriptor >	labelToVertex

int	max_min_stage = -1

int	max_min_stage_per_gress [3] = {-1, -1, -1}

assoc::hash_map< const IR::MAU::Table *, safe_vector< MinEdgeInfo > >	min_stage_edges

ordered_map< cstring, const IR::MAU::Table * >	name_to_table

cstring	passContext

bool	placed = false

ReductionOrInfo	red_info

ordered_map< const IR::MAU::Table *, StageInfo >	stage_info

std::map< std::pair< const IR::MAU::Table , const IR::MAU::Table >, DependencyGraph::mau_dependencies_t >	table_dep_ = {}

ordered_map< const IR::MAU::Table , ordered_set< const IR::MAU::Table > >	unavoidable_container_conflicts

std::vector< ordered_set< DependencyGraph::Graph::vertex_descriptor > >	vertex_rst

Static Public Attributes
static const unsigned	ANTI

static const unsigned	CONTROL

static const unsigned	CONTROL_AND_ANTI = CONTROL \| ANTI

Friends
std::ostream &	operator<< (std::ostream &out, const DependencyGraph &dg)

Class Documentation

◆ DependencyGraph::StageInfo

struct DependencyGraph::StageInfo

Class Members
int	dep_stages
int	dep_stages_control
int	dep_stages_control_anti
int	dep_stages_control_anti_split
int	dep_stages_dom_frontier
int	max_stage
int	min_stage

Member Function Documentation

◆ critical_path_length()

int DependencyGraph::critical_path_length ( ) const

inline

Returns: the length of the dependency based critical path for the program.

◆ fill_dep_stages_from_topo()

void DependencyGraph::fill_dep_stages_from_topo	(	const std::vector< ordered_set< DependencyGraph::Graph::vertex_descriptor > > &	topo,
		bool	include_stages,
		const TableSummary *	summary )

Fill up the stage_info map value regarding dep_stages_control_anti or dep_stages_control_anti_split based on include_stages argument.

◆ find_mau_dependency()

DependencyGraph::mau_dependencies_t DependencyGraph::find_mau_dependency	(	const IR::MAU::Table *	from,
		const IR::MAU::Table *	to )

Returns the MAU stage dependency that exists from table 'from' to table 'to'. Note that this function does not know the control flow; it only checks the PHV containers written and read by the two tables. If the two tables are not on the same control flow, it is the caller's responsiblity to know they are concurrent. This function cannot be called until PHV allocation has completed. If it is, the maps accessed will not have been populated.

◆ get_dependency()

DependencyGraph::dependencies_t DependencyGraph::get_dependency	(	const IR::MAU::Table *	t1,
		const IR::MAU::Table *	t2 ) const

inline

Returns the dependency type from t1 to t2.

◆ is_anti_edge()

bool DependencyGraph::is_anti_edge ( DependencyGraph::dependencies_t dep ) const

Returns: boolean indicating if an edge is a type of anti edge

◆ is_ctrl_edge()

bool DependencyGraph::is_ctrl_edge ( DependencyGraph::dependencies_t dep ) const

Returns: boolean indicating if an edge is a type of control edge

◆ is_edge_critical()

bool DependencyGraph::is_edge_critical ( typename Graph::edge_descriptor e ) const

Returns: boolean indicating if an edge is critical, i.e. appears in the min_stage_edges

◆ is_non_directional_edge()

bool DependencyGraph::is_non_directional_edge ( DependencyGraph::dependencies_t dep ) const

Returns: boolean indicating if an edge is non-directional (tables can't share the same stage, but could be placed in any order)

Member Data Documentation

◆ ANTI

const unsigned DependencyGraph::ANTI

static

Initial value:

= ANTI_EXIT | ANTI_TABLE_READ | ANTI_ACTION_READ |

ANTI_NEXT_TABLE_DATA | ANTI_NEXT_TABLE_METADATA

◆ container_conflicts

ordered_map<const IR::MAU::Table *, ordered_set<const IR::MAU::Table *> > DependencyGraph::container_conflicts

A map of all tables that cannot be placed in the same stage as the key table, because they share an ALU operation over a container. The following example will indicate why this is a problem:

action a1(bit<4> x1) { hdr.data.x1 = x1; } action a2(bit<4> x2) { hdr.data.x2 = x2; }

table t1 { key = { hdr.data.f1; } actions = { a1; } default_action = a1(1); } table t2 { key = { hdr.data.f1; } actions = { a2; } default_action = a2(1); }

apply { t1.apply(); t2.apply(); }

Now let's say that hdr.data.x1 and hdr.data.x2 are in the same 8 bit PHV container, i.e. B0. In the instruction memory, a1 and a2 will have its own VLIW instruction, which itself contains an opcode for every single PHV ALU. All actions in the ALUs run in parallel, and the individual operations to each ALU are brought in as a portion of one stage VLIW instruction.

This stage VLIW instruction is formed by ORing together all actions (each of which is its own VLIW instruction) that are intended to be run in the stage. Thus if a1 and a2 were to be run in the same stage, their operations over container B0 would be ORed together. In general ORing these opcodes will lose the meaning of the original operation.

Note that the constraint does not apply if the actions themselves are mutually exclusive, i.e. if the apply statement looked like the following:

apply { if (hdr.data.f1 == 1) { t1.apply() } else { t2.apply() } }

then it would be impossible for a1 and a2 to ever be called in the same packet, and thus the opcode for B0 would never be mucked up by the OR.

However, this is not to be considered an action dependency. If t2 were action dependent on t1, then t1 would have to happen before t2. This is not the case for this program as t2 does not affect any of the values that t1 is working on. Instead it just affects the containers

◆ containers_read_alu_

std::map<const IR::MAU::Table *, std::map<const PHV::Container, bool> > DependencyGraph::containers_read_alu_

Initial value:

=

{}

◆ containers_read_xbar_

std::map<const IR::MAU::Table *, std::map<const PHV::Container, bool> > DependencyGraph::containers_read_xbar_

Initial value:

=

{}

◆ CONTROL

const unsigned DependencyGraph::CONTROL

static

Initial value:

=
        CONTROL_ACTION | CONTROL_COND_TRUE | CONTROL_COND_FALSE | CONTROL_TABLE_HIT |
        CONTROL_TABLE_MISS | CONTROL_DEFAULT_NEXT_TABLE | CONTROL_EXIT | ANTI_NEXT_TABLE_CONTROL

◆ max_min_stage_per_gress

int DependencyGraph::max_min_stage_per_gress[3] = {-1, -1, -1}

The largest value of min_stage encountered when determining min_stage values for table, across all tables in the program. The minimum number of stages required by the program is 1 + max_min_stage (stage numbers start from 0, 1, ..., n-1)

◆ unavoidable_container_conflicts

ordered_map<const IR::MAU::Table *, ordered_set<const IR::MAU::Table *> > DependencyGraph::unavoidable_container_conflicts

Unavoid container conflicts due to parde constraints. This will be a subset of the above container_conflicts.

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

table_dependency_graph.h
mau/table_dependency_graph.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Friends

Class Documentation

◆ DependencyGraph::StageInfo

Member Function Documentation

◆ critical_path_length()

◆ fill_dep_stages_from_topo()

◆ find_mau_dependency()

◆ get_dependency()

◆ is_anti_edge()

◆ is_ctrl_edge()

◆ is_edge_critical()

◆ is_non_directional_edge()

Member Data Documentation

◆ ANTI

◆ container_conflicts

◆ containers_read_alu_

◆ containers_read_xbar_

◆ CONTROL

◆ max_min_stage_per_gress

◆ unavoidable_container_conflicts