#include <phv_slicing_dfs_iterator.h>

Inheritance diagram for PHV::Slicing::DfsItrContext:

Public Member Functions
	DfsItrContext (const PhvInfo &phv, const MapFieldToParserStates &field_to_states, const CollectParserInfo &parser_info, const SuperCluster *sc, const PHVContainerSizeLayout &pa, const ActionPackingValidatorInterface &action_packing_validator, const ParserPackingValidatorInterface &parser_packing_validator, const PackConflictChecker &pack_conflict, const IsReferencedChecker is_used)

bool	check_duplicate_slicing_plan (const ordered_set< SuperCluster * >)

bool	check_pack_conflict (const SuperCluster::SliceList *sl) const
	return true if there are pack_conflicts in `sl`.

std::optional< SplitDecision >	collect_aftersplit_constraints (const SuperCluster *sc) const

bool	collect_implicit_container_sz_constraint (SplitDecision decided_sz, const SuperCluster sc) const

bool	dfs (const IterateCb &yield, const ordered_set< SuperCluster * > &unchecked)

std::optional< SliceListLoc >	dfs_pick_next () const

bool	dfs_prune (const ordered_set< SuperCluster * > &unchecked)

bool	dfs_prune_invalid_packing (const SuperCluster *sc)

bool	dfs_prune_invalid_parser_packing (const SuperCluster *sc) const

bool	dfs_prune_unsat_exact_list_size_mismatch (const SplitDecision &decided_sz, const SuperCluster *sc) const

bool	dfs_prune_unsat_slicelist_constraints (const SplitDecision &constraints, const SuperCluster *sc) const

bool	dfs_prune_unsat_slicelist_max_size (const SplitDecision &constraints, const SuperCluster *sc) const
	return true if exists constraint unsat due to the limit of slice list size.

bool	dfs_prune_unwell_formed (const SuperCluster *sc) const

std::vector< SuperCluster * >	get_well_formed_no_more_split () const

void	invalidate (const SuperCluster::SliceList *sl) override

void	iterate (const IterateCb &cb) override
	iterate will pass valid slicing results to cb. Stop when cb returns false.

std::vector< SplitChoice >	make_choices (const SliceListLoc &target) const

std::optional< std::pair< SplitSchema, SplitDecision > >	make_split_meta (SuperCluster sc, SuperCluster::SliceList sl, int first_n_bits) const

bool	need_further_split (const SuperCluster::SliceList *sl) const
	return true if the slicelist needs to be further split.

void	need_to_check_duplicate ()

void	propagate_8bit_exact_container_split (SuperCluster sc, SuperCluster::SliceList target, SplitSchema schema, SplitDecision decisions) const

bool	propagate_tail_split (SuperCluster sc, const SplitDecision &constraints, const SplitDecision decisions, const SuperCluster::SliceList just_split_target, const int n_just_split_bits, SplitSchema schema) const

void	set_config (const IteratorConfig &cfg) override
	set configs.

std::optional< std::list< SuperCluster * > >	split_by_adjacent_deparsed_and_non_deparsed (SuperCluster *sc) const

std::optional< std::list< SuperCluster * > >	split_by_adjacent_no_pack (SuperCluster *sc) const

std::optional< std::list< SuperCluster * > >	split_by_deparsed_bottom_bits (SuperCluster *sc) const
	split_by_deparsed_bottom_bits will split at the beginning of deparsed_bottom_bits field.

std::optional< std::list< SuperCluster * > >	split_by_long_fieldslices (SuperCluster *sc) const

std::optional< std::list< SuperCluster * > >	split_by_pa_container_size (const SuperCluster *sc, const PHVContainerSizeLayout &pa)
	split_by_pa_container_size will split `sc` by `pa` container size.

std::optional< std::list< SuperCluster * > >	split_by_parser_write_mode (SuperCluster *sc)
	split_by_parser_write_mode will split based on incompatible parser write modes

std::optional< std::list< SuperCluster * > >	split_by_valid_container_range (SuperCluster *sc) const

Public Member Functions inherited from PHV::Slicing::IteratorInterface

Public Attributes
const ActionPackingValidatorInterface &	action_packing_validator_i

int	check_duplicate = -1

CheckWriteModeConsistency	check_write_mode_consistency_i

IteratorConfig	config_i

int	dfs_depth_i = 0

ordered_set< SuperCluster * >	done_i

const int	duplicate_check_supercluster_size = 5

bool	has_itr_i = false

const PackConflictChecker	has_pack_conflict_i

const IsReferencedChecker	is_used_i

int	n_steps_i = 0

int	n_steps_since_last_solution = 0

ordered_map< const PHV::Field *, std::pair< le_bitrange, int > >	pa_container_size_upcastings_i

const PHVContainerSizeLayout	pa_i

const ParserPackingValidatorInterface &	parser_packing_validator_i

const PhvInfo &	phv_i

std::set< SplitChoice >	reject_sizes

const SuperCluster *	sc_i

std::vector< const SuperCluster::SliceList * >	slicelist_on_stack_i

assoc::hash_map< FieldSlice, AfterSplitConstraint >	split_decisions_i

ordered_set< SuperCluster * >	to_be_split_i

const SuperCluster::SliceList *	to_invalidate = nullptr

ordered_map< const SuperCluster::SliceList *, int >	to_invalidate_sl_counter

Static Public Attributes
static constexpr int	to_invalidate_max_ignore = 8

Detailed Description

DfsItrContext implements the Slicing Iterator using DFS. Because caller won't be using DfsItrContext directly(protected by pImpl), to make white-box testing possible, all functions are public.

Member Function Documentation

◆ collect_aftersplit_constraints()

std::optional< SplitDecision > PHV::Slicing::DfsItrContext::collect_aftersplit_constraints ( const SuperCluster * sc ) const

collect_aftersplit_constraints returns AfterSplitConstraints on the fieldslice of sc based on split_decisions_i and pa_container_size_upcastings_i.

◆ collect_implicit_container_sz_constraint()

bool PHV::Slicing::DfsItrContext::collect_implicit_container_sz_constraint	(	SplitDecision *	decided_sz,
		const SuperCluster *	sc ) const

collect additional implicit container size constraint and save them to decided_sz, if it can be expressed. Otherwise, if will only check whether the implicit container size constraint can be satisfied. TODO: this function is created initially for the most common case of egress::eg_intr_md.egress_port that has (1) ^bit[0..15]; (2) no_split; (3) deparsed_bottom_bits because of these three constraints, this field can only be allocated to 16-bit container. There can be more special cases for these implicit (hard to be generalized).

◆ dfs()

bool PHV::Slicing::DfsItrContext::dfs	(	const IterateCb &	yield,
		const ordered_set< SuperCluster * > &	unchecked )

dfs search valid slicing. unchecked are superclusters that needs to be checked for pruning.

◆ dfs_pick_next()

std::optional< SliceListLoc > PHV::Slicing::DfsItrContext::dfs_pick_next ( ) const

dfs_pick_next return the next slice list to be split. There are some heuristics for returning the slicelist that has most constraints.

◆ dfs_prune()

bool PHV::Slicing::DfsItrContext::dfs_prune ( const ordered_set< SuperCluster * > & unchecked )

pruning strategies return true if found any unsatisfactory case. This function will return true if any of the following pruning strategies returns true. TODO: non-const because it may call invalidate();

◆ dfs_prune_invalid_packing()

bool PHV::Slicing::DfsItrContext::dfs_prune_invalid_packing ( const SuperCluster * sc )

return true if there exists packing that make it impossible to to synthesize actions. TODO: non-const because it may call invalidate();

◆ dfs_prune_unsat_exact_list_size_mismatch()

bool PHV::Slicing::DfsItrContext::dfs_prune_unsat_exact_list_size_mismatch	(	const SplitDecision &	decided_sz,
		const SuperCluster *	sc ) const

return true if exists a metadata list that will join two exact_containers lists of different sizes. For example:; sl_1: [f1<16>, f2<8>, f3<8>[0:1], f3<8>[2:7]], total 32, exact. sl_2: [f2'<8>, f4<8>[0:3], f4<8>[4:7]], total 16, exact. sl_3: [md1<2>, pad<2>, md2<4>] rotational clusters: {f3[0:1], md1}, {f4<8>[0:3], md2} sl_3 will join sl_1 and sl_2 into one super cluster, and we can infer that this cluster is invalid because exact slice list sizes are not the same.

◆ dfs_prune_unsat_slicelist_constraints()

bool PHV::Slicing::DfsItrContext::dfs_prune_unsat_slicelist_constraints	(	const SplitDecision &	constraints,
		const SuperCluster *	sc ) const

return true if constraints for a slice list cannot be all satisfied. Check for cases like: 32 xxx 16 [fs1<8>, fs2<8>, fs3<16>] it's unsat because fs1 was decided to be allocated into 32-bit container while for fs3 it's 16-bit container. However, in the above layout it's impossible. We run a greedy algorithm looking for cases but may have false negatives.

◆ dfs_prune_unwell_formed()

bool PHV::Slicing::DfsItrContext::dfs_prune_unwell_formed ( const SuperCluster * sc ) const

dfs_prune_unwell_formed: return true if (1) sc cannot be split further and is not well_formed. (2) a slicelist in sc that cannot be split further has pack conflicts.

◆ get_well_formed_no_more_split()

std::vector< SuperCluster * > PHV::Slicing::DfsItrContext::get_well_formed_no_more_split ( ) const

get_well_formed_no_more_split returns super clusters that all the slice lists does not need_further_split, and the cluster is well_formed.

◆ invalidate()

void PHV::Slicing::DfsItrContext::invalidate ( const SuperCluster::SliceList * sl )

overridevirtual

invalidate is the feedback mechanism for allocation algorithm to ask iterator not to produce slicing result contains sl. Caller can This DFS iterator will respect the list of top-most stack frame, i.e., the most recent decision made by DFS.

Implements PHV::Slicing::IteratorInterface.

◆ iterate()

void PHV::Slicing::DfsItrContext::iterate ( const IterateCb & cb )

overridevirtual

iterate will pass valid slicing results to cb. Stop when cb returns false.

Implements PHV::Slicing::IteratorInterface.

◆ make_choices()

std::vector< SplitChoice > PHV::Slicing::DfsItrContext::make_choices ( const SliceListLoc & target ) const

return possible SplitChoice on target. When minimal_packing_mode is false, results are sorted with a set of heuristics that choices with more packing opportunities (generally larger container-sized chunks), ,split at field boundaries, and better chances to split between ref/unref fields, are placed at lower indexes. See implementation for more details on heuristics. If minimal_packing_mode is true, then we will prefer to split with less packing of fieldslices.

◆ make_split_meta()

std::optional< std::pair< SplitSchema, SplitDecision > > PHV::Slicing::DfsItrContext::make_split_meta	(	SuperCluster *	sc,
		SuperCluster::SliceList *	sl,
		int	first_n_bits ) const

make_split_meta will generate schema and decision to split out first first_n_bits of sl under sc.When a conflicting split decision is found,

Returns: std::nullopt.

◆ propagate_8bit_exact_container_split()

void PHV::Slicing::DfsItrContext::propagate_8bit_exact_container_split	(	SuperCluster *	sc,
		SuperCluster::SliceList *	target,
		SplitSchema *	schema,
		SplitDecision *	decisions ) const

propagate_8bit_exact_container_split propagates the 8bit split decision on target to other slice lists in sc, as long as there is one exact_containers field slices in rotational clusters of splitted slices of list. If we are splitting out an 8-bit slice list with exact_containers constraint, then we can infer that all other slices in the the same rotational cluster with slices that were just split out, need to be split by the bytes (counting from the beginning of lists) that contains them.

◆ propagate_tail_split()

bool PHV::Slicing::DfsItrContext::propagate_tail_split	(	SuperCluster *	sc,
		const SplitDecision &	constraints,
		const SplitDecision *	decisions,
		const SuperCluster::SliceList *	just_split_target,
		const int	n_just_split_bits,
		SplitSchema *	schema ) const

If we found that any field slice in the last byte of a slice list has a decided size, then we can split the tail out so that the packing is materialized as early as possible.

returns decision of fs made by this round and all previous rounds.

Do not split cross the bytes that we just split out. If incorrect, it will fail very soon later.

◆ set_config()

void PHV::Slicing::DfsItrContext::set_config ( const IteratorConfig & cfg )

inlineoverridevirtual

set configs.

Implements PHV::Slicing::IteratorInterface.

◆ split_by_adjacent_deparsed_and_non_deparsed()

std::optional< std::list< SuperCluster * > > PHV::Slicing::DfsItrContext::split_by_adjacent_deparsed_and_non_deparsed ( SuperCluster * sc ) const

split_by_adjacent_deparsed_and_non_deparsed will split sc between deparsed and non-deparsed field.

◆ split_by_adjacent_no_pack()

std::optional< std::list< SuperCluster * > > PHV::Slicing::DfsItrContext::split_by_adjacent_no_pack ( SuperCluster * sc ) const

split_by_adjacent_no_pack will split sc at byte boundary if two adjacent fields cannot be packed into one container.

◆ split_by_long_fieldslices()

std::optional< std::list< SuperCluster * > > PHV::Slicing::DfsItrContext::split_by_long_fieldslices ( SuperCluster * sc ) const

split_by_long_fieldslices will split fieldslices that its length is greater or equal to 64 bits, using 32-bit container if possible.

◆ split_by_valid_container_range()

std::optional< std::list< SuperCluster * > > PHV::Slicing::DfsItrContext::split_by_valid_container_range ( SuperCluster * sc ) const

split_by_valid_container_range will split based on valid container range constraint that a field cannot be packed fields after it, when its valid container range is equal to the size of the field.

Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Member Function Documentation

◆ collect_aftersplit_constraints()

◆ collect_implicit_container_sz_constraint()

◆ dfs()

◆ dfs_pick_next()

◆ dfs_prune()

◆ dfs_prune_invalid_packing()

◆ dfs_prune_unsat_exact_list_size_mismatch()

◆ dfs_prune_unsat_slicelist_constraints()

◆ dfs_prune_unwell_formed()

◆ get_well_formed_no_more_split()

◆ invalidate()

◆ iterate()

◆ make_choices()

◆ make_split_meta()

◆ propagate_8bit_exact_container_split()

◆ propagate_tail_split()

◆ set_config()

◆ split_by_adjacent_deparsed_and_non_deparsed()

◆ split_by_adjacent_no_pack()

◆ split_by_long_fieldslices()

◆ split_by_valid_container_range()