Identify headers marked as valid/invalid in MAU pipeline and find correlations between removal of headers of interest. More...

#include <header_validity_analysis.h>

Inheritance diagram for HeaderValidityAnalysis:

[legend]

Public Types
using	ResultMap = std::map<FieldSliceSet, std::set<FieldSliceSet>>

Public Types inherited from P4::Visitor
typedef Visitor_Context	Context

Public Member Functions
	HeaderValidityAnalysis (const HeaderValidityAnalysis &)=default

	HeaderValidityAnalysis (const PhvInfo &phvInfo, const std::set< FieldSliceSet > &correlations)

	HeaderValidityAnalysis (HeaderValidityAnalysis &&)=default

HeaderValidityAnalysis *	clone () const override

void	end_apply () override

HeaderValidityAnalysis &	flow_clone () override

void	flow_merge (Visitor &v) override

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

bool	preorder (const IR::MAU::Action *act) override

bool	preorder (const IR::MAU::Instruction *instruction) override

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 ControlFlowVisitor *	controlFlowVisitor ()

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

Public Attributes
std::map< const PHV::FieldSlice , std::set< FieldSliceSet >, PHV::FieldSlice::Less >	interestedCorrelations
	The correlations that the client is interested in, indexed by POV bit.

const PhvInfo &	phvInfo

SymBitMatrix	povBitsAlwaysInvalidateTogether

SymBitMatrix	povBitsAlwaysValidateTogether

std::map< const PHV::Field , std::set< const IR::MAU::Action > >	povBitsInvalidateActions

std::set< const PHV::Field * >	povBitsSetInvalidInMau

std::set< const PHV::Field * >	povBitsSetValidInMau

std::map< const PHV::Field , std::set< const IR::MAU::Action > >	povBitsUpdateActions

std::map< const PHV::Field , std::set< const IR::MAU::Action > >	povBitsUpdateOrInvalidateActions

std::map< const PHV::Field , std::set< const IR::MAU::Action > >	povBitsUpdateOrValidateActions

std::map< const PHV::Field , std::set< const IR::MAU::Action > >	povBitsValidateActions

ResultMap	resultMap
	The output of this analysis.

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

cstring	internalName

SplitFlowVisit_base *&	split_link

SplitFlowVisit_base *	split_link_mem = nullptr

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)

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

Identify headers marked as valid/invalid in MAU pipeline and find correlations between removal of headers of interest.

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

Finds correlations between the removal of headers in the MAU pipeline. In the back end, header removal is represented by the clearing of POV bits, so this analysis really looks at the correlation between when POV bits are cleared.

The input of this analysis is a set expressing the correlations that the client of the analysis is interested in. This is done to avoid any unnecessary exponential blow-up in the size of the result: the input acts as a filter on the results produced.

As a running example, consider a pipeline whose behaviour looks like:

if (foo) { h1.setInvalid(); h2.setInvalid(); } else { h1.setInvalid(); h3.setInvalid(); }

h3.setValid();

if (bar) h4.setInvalid(); if (baz) h5.setInvalid();

Let S1 be the set {{pov1, pov2, pov3, pov4, pov5}}. Given as input to the analysis, S1 indicates that the client is interested in all correlations between all headers.

Let S2 be the set {{pov1, pov2}, {pov2, pov3}, {pov2, pov4}}. Given as input, this set indicates that we are only interested in pairwise correlations between h2 and h1, h3, and h4.

The output of this analysis is a map, wherein each set S in the input is mapped to subsets of S that might be cleared. There may be multiple subsets when different paths through the pipeline result in different POV bits being cleared.

If a header is removed and subsequently added, in the output of this analysis, it will still appear as having been removed.

Given S1 as input to the analysis, the result would resemble

{pov1, po2, pov3, pov4, pov5} ↦ {{pov1, pov2}, {pov1, pov2, pov4}, {pov1, pov2, pov5}, {pov1, pov2, pov4, pov5}, {pov1, pov3}, {pov1, pov3, pov4}, {pov1, pov3, pov5}, {pov1, pov3, pov4, pov5}}

We can expect this kind of result to be exponential in the number of headers.

Alternatively, if S2 were given as input, the result would be:

{pov1, pov2} ↦ {{pov1}, {pov1, pov2}} {pov2, pov3} ↦ {{pov2}, {pov3}} {pov2, pov4} ↦ {{}, {pov2}, {pov4}, {pov2, pov4}}

For clients only interested in pairwise correlations, we can expect the result to be quadratic in the number of headers.

Constructor & Destructor Documentation

◆ HeaderValidityAnalysis()

HeaderValidityAnalysis::HeaderValidityAnalysis	(	const PhvInfo &	phvInfo,
		const std::set< FieldSliceSet > &	correlations )

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

Member Function Documentation

◆ clone()

HeaderValidityAnalysis * HeaderValidityAnalysis::clone ( ) const

overridevirtual

Reimplemented from P4::Visitor.

◆ end_apply()

void HeaderValidityAnalysis::end_apply ( )

overridevirtual

Reimplemented from P4::Visitor.

◆ flow_clone()

HeaderValidityAnalysis & HeaderValidityAnalysis::flow_clone ( )

overridevirtual

Reimplemented from P4::Visitor.

◆ flow_merge()

void HeaderValidityAnalysis::flow_merge ( Visitor & )

overridevirtual

Merge the given visitor into this visitor at a joint point in the control flow graph. Should update @this and leave the other unchanged.

Reimplemented from P4::Visitor.

Public Types

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ HeaderValidityAnalysis()

Member Function Documentation

◆ clone()

◆ end_apply()

◆ flow_clone()

◆ flow_merge()