PHV::v2::AllocatorBase Class Reference

#include <allocator_base.h>

Inheritance diagram for PHV::v2::AllocatorBase:

Classes
class	DfsListsAllocator
struct	DfsState

Public Member Functions
	AllocatorBase (const PhvKit &kit)
PHV::Transaction	alloc_deparser_zero_cluster (const ScoreContext &ctx, const PHV::Allocation &alloc, const PHV::SuperCluster *sc, PhvInfo &phv) const
AllocResult	alloc_strided_super_clusters (const ScoreContext &ctx, const Allocation &alloc, const SuperCluster *sc, const ContainerGroupsBySize &groups, AllocatorMetrics &alloc_metrics, const int max_n_slicings=64) const
AllocResult	try_sliced_super_cluster (const ScoreContext &ctx, const Allocation &alloc, const SuperCluster *sc, const ContainerGroupsBySize &groups, AllocatorMetrics &alloc_metrics) const
	ALLOCATION functions common to trivial and greedy allocation.

Protected Types
using	DfsAllocCb = std::function<bool(const Transaction &)>
	internal type of callback.

Protected Member Functions
AllocResult	alloc_stride (const ScoreContext &ctx, const Allocation &alloc, const std::vector< FieldSlice > &stride, const ContainerGroupsBySize &groups, AllocatorMetrics &alloc_metrics) const
const AllocError *	check_container_scope_constraints (const Allocation &alloc, const std::vector< AllocSlice > &candidates, const Container &c) const
std::set< PHV::Size >	compute_valid_container_sizes (const SuperCluster *sc) const
const AllocError *	is_container_bytes_ok (const Allocation &alloc, const std::vector< AllocSlice > &candidates, const Container &c) const
const AllocError *	is_container_gress_ok (const Allocation &alloc, const AllocSlice &sl, const Container &c) const
const AllocError *	is_container_solitary_ok (const Allocation &alloc, const AllocSlice &candidate, const Container &c) const
const AllocError *	is_container_type_ok (const AllocSlice &sl, const Container &c) const
	CONSTRAINT CHECKING Functions common to trivial and greedy allocation.
const AllocError *	is_container_write_mode_ok (const Allocation &alloc, const AllocSlice &sl, const Container &c) const
std::vector< const SuperCluster::SliceList * > *	make_alloc_order (const ScoreContext &ctx, const SuperCluster *sc, const PHV::Size width) const
Transaction	make_speculated_alloc (const ScoreContext &ctx, const Allocation &alloc, const SuperCluster *sc, const std::vector< AllocSlice > &candidates, const Container &candidates_cont) const
std::vector< int >	make_start_positions (const ScoreContext &ctx, const SuperCluster::SliceList *sl, const PHV::Size width) const
std::optional< Transaction >	try_hints (const ScoreContext &ctx, const Allocation &alloc, const ContainerGroup &group, const ActionSourceCoPackMap &action_hints_map, ordered_set< PHV::FieldSlice > &allocated, ScAllocAlignment &hint_enforced_alignments, AllocatorMetrics &alloc_metrics) const
SomeContScopeAllocResult	try_slices_adapter (const ScoreContext &ctx, const Allocation &alloc, const FieldSliceAllocStartMap &fs_starts, const ContainerGroup &group, std::optional< Container > c, AllocatorMetrics &alloc_metrics) const
ContScopeAllocResult	try_slices_to_container (const ScoreContext &ctx, const Allocation &alloc, const FieldSliceAllocStartMap &fs_starts, const Container &c, AllocatorMetrics &alloc_metrics, const bool skip_mau_checks=false) const
SomeContScopeAllocResult	try_slices_to_container_group (const ScoreContext &ctx, const Allocation &alloc, const FieldSliceAllocStartMap &fs_starts, const ContainerGroup &group, AllocatorMetrics &alloc_metrics) const
AllocResult	try_super_cluster_to_container_group (const ScoreContext &ctx, const Allocation &alloc, const SuperCluster *sc, const ContainerGroup &group, AllocatorMetrics &alloc_metrics) const
AllocResult	try_wide_arith_slices_to_container_group (const ScoreContext &ctx, const Allocation &alloc, const ScAllocAlignment &alignment, const SuperCluster::SliceList *lo, const SuperCluster::SliceList *hi, const ContainerGroup &group, AllocatorMetrics &alloc_metrics) const
const AllocError *	verify_can_pack (const ScoreContext &ctx, const Allocation &alloc, const SuperCluster *sc, const std::vector< AllocSlice > &candidates, const Container &c, ActionSourceCoPackMap &co_pack_hints) const

Protected Attributes
const PhvKit &	kit_i

Detailed Description

AllocatorBase contains all reusable functions for PHV allocation, mostly 3 categories: (1) constraint checking functions that their names usually start with is_. (2) helper functions starts with make_* or compute_*. (3) allocation functions: const-qualified functions that returns an AllocResult.

Member Function Documentation

alloc_deparser_zero_cluster()

PHV::Transaction PHV::v2::AllocatorBase::alloc_deparser_zero_cluster	(	const ScoreContext &	ctx,
		const PHV::Allocation &	alloc,
		const PHV::SuperCluster *	sc,
		PhvInfo &	phv ) const

This function will always successfully allocate fieldslices of sc to deparser zero optimization containers, which are B0 for ingress, B16 for egress. phv.addZeroContainer() will be called to add used deparser-zero containers. NOTE: if sc is fully-clot allocated, it will be ignored. premise: (1) sc must be deparser-zero optimization candidate.

alloc_strided_super_clusters()

AllocResult PHV::v2::AllocatorBase::alloc_strided_super_clusters	(	const ScoreContext &	ctx,
		const Allocation &	alloc,
		const SuperCluster *	sc,
		const ContainerGroupsBySize &	groups,
		AllocatorMetrics &	alloc_metrics,
		const int	max_n_slicings = 64 ) const

Try to allocate stride super cluster sc, without further slicing, to groups. Premise: (1) DO NOT pass non-strided super cluster to this function.

check_container_scope_constraints()

const AllocError * PHV::v2::AllocatorBase::check_container_scope_constraints ( const Allocation & alloc, const std::vector< AllocSlice > & candidates, const Container & c ) const

protected

Returns

error if violating any of the above is_container_* constraint.

compute_valid_container_sizes()

std::set< PHV::Size > PHV::v2::AllocatorBase::compute_valid_container_sizes ( const SuperCluster * sc ) const

protected

Returns

a set of container sizes that are okay for sc.

is_container_bytes_ok()

const AllocError * PHV::v2::AllocatorBase::is_container_bytes_ok ( const Allocation & alloc, const std::vector< AllocSlice > & candidates, const Container & c ) const

protected

Returns

error if violating max container bytes constraints on some field.

is_container_gress_ok()

const AllocError * PHV::v2::AllocatorBase::is_container_gress_ok ( const Allocation & alloc, const AllocSlice & sl, const Container & c ) const

protected

Returns

error when sl does not have the same gress assignment as c.

is_container_solitary_ok()

const AllocError * PHV::v2::AllocatorBase::is_container_solitary_ok ( const Allocation & alloc, const AllocSlice & candidate, const Container & c ) const

protected

Returns

error when trying to pack a field with solitary constraint with other fields.

is_container_type_ok()

const AllocError * PHV::v2::AllocatorBase::is_container_type_ok ( const AllocSlice & sl, const Container & c ) const

protected

CONSTRAINT CHECKING Functions common to trivial and greedy allocation.

Returns

error when sl cannot fit the container type constraint of c.

is_container_write_mode_ok()

const AllocError * PHV::v2::AllocatorBase::is_container_write_mode_ok ( const Allocation & alloc, const AllocSlice & sl, const Container & c ) const

protected

Returns

error when there is the parser write mode of sl is different from other slices allocated in containers of the same parser group.

ignore deparser zero candidates if their extracts have been removed.

make_alloc_order()

std::vector< const SuperCluster::SliceList * > * PHV::v2::AllocatorBase::make_alloc_order ( const ScoreContext & ctx, const SuperCluster * sc, const PHV::Size width ) const

protected

Returns

a vector of slice list that covers all field slices of sc. SliceLists are sorted in the order of suggested allocation by (1) slice list with fixed alignment.

make_speculated_alloc()

Transaction PHV::v2::AllocatorBase::make_speculated_alloc ( const ScoreContext & ctx, const Allocation & alloc, const SuperCluster * sc, const std::vector< AllocSlice > & candidates, const Container & candidates_cont ) const

protected

Generate pseudo AllocSlices for field slices that have not been allocated, but their allocation can be speculated upfront: when there is only one valid starting position.

Returns

a transaction that contains the pseudo AllocSlices. we can infer that field slices will be allocated to a container with corresponding starting positions. This will allow can_pack function to check constraints from action reading(writing) side, even if destination(source) has not been allocated yet.

make_start_positions()

std::vector< int > PHV::v2::AllocatorBase::make_start_positions ( const ScoreContext & ctx, const SuperCluster::SliceList * sl, const PHV::Size width ) const

protected

Returns

a vector a starting postions for sl in width-sized containers. The starting positions might be sorted for more efficient searching, see implementation.

try_hints()

std::optional< Transaction > PHV::v2::AllocatorBase::try_hints ( const ScoreContext & ctx, const Allocation & alloc, const ContainerGroup & group, const ActionSourceCoPackMap & action_hints_map, ordered_set< PHV::FieldSlice > & allocated, ScAllocAlignment & hint_enforced_alignments, AllocatorMetrics & alloc_metrics ) const

protected

Try to allocate by action_hints to group. This function will add allocated field slices to allocated.

we found one hint allocated, commit and break.

try_sliced_super_cluster()

AllocResult PHV::v2::AllocatorBase::try_sliced_super_cluster	(	const ScoreContext &	ctx,
		const Allocation &	alloc,
		const SuperCluster *	sc,
		const ContainerGroupsBySize &	groups,
		AllocatorMetrics &	alloc_metrics ) const

ALLOCATION functions common to trivial and greedy allocation.

Try to allocate sc, without further slicing, to groups. Premise: (1) DO NOT pass fully clot-allocated clusters to this function. If does, fields will be double-allocated. (2) DO NOT pass deparser-zero-candidate cluster to this function, because they will not be allocated to zero containers, Unless the correctness of their allocation does not matter, e.g., in trivial allocator, as they are not referenced in MAU.

try_slices_adapter()

SomeContScopeAllocResult PHV::v2::AllocatorBase::try_slices_adapter ( const ScoreContext & ctx, const Allocation & alloc, const FieldSliceAllocStartMap & fs_starts, const ContainerGroup & group, std::optional< Container > c, AllocatorMetrics & alloc_metrics ) const

protected

A helper function that will call try_slices_to_container if c is specified (not std::nullopt). Otherwise, it will call try_slices_to_container_group with group.

try_slices_to_container()

ContScopeAllocResult PHV::v2::AllocatorBase::try_slices_to_container ( const ScoreContext & ctx, const Allocation & alloc, const FieldSliceAllocStartMap & fs_starts, const Container & c, AllocatorMetrics & alloc_metrics, const bool skip_mau_checks = false ) const

protected

Try to allocate fieldslices with starting positions defined in fs_starts to container c. Various container-level constraints will be checked. When skip_mau_checks are true, mau-related checks will be skipped, e.g., verify_can_pack. It should only be true when allocator is trying to allocate stride clusters. Premises without BUG_CHECK: (1) fs_starts contains all field slices that needs to be allocated to c. They should never exceed the width of the container, i.e., max_i(start_i + size_i) < c.width(). (2) allocating to c will not violate pa_container_size pragma specified on field slices in fs_starts: (3) if there were wide_arithmetic slices, if lo(hi), c must have even(odd) index. Also caller needs to allocate them to adjacent even-odd pair containers. (4) if deparsed/exact_container, total number of bits must be equal to the width of c. (5) field slices of an aligned cluster, including slices that have already been allocated in alloc, and slices to be allcoated in fs_starts, must have the same starting index in container. This function, and all the functions this function will invoke, will not check this constraint. Failed to respect this rule will get an action analysis error in later passes.

Returns

error in AllocResult if (1) not enough space: <1> non-mutex bits occupied or has non-mutex solitary field. <2> uninitialized read + extracted. (2) cannot pack into container. (3) when container is mocha/dark/tphv, not all field slices are be valid to be allocated to the container type of c. (4) violate pa_container_type. (5) container gress match (6) parserGroupGress match, all containers must have same write mode. (7) deparser group must be the same. (8) solitary fields are not packed with other fields except for paddings fields. (9) fields in fs_starts will not violate parser extraction constraints. (5) field max container bytes constraints. NOTE: alloc slices of ignore_alloc field slices will not be generated. Possible ErrorCode: (1) NOT_ENOUGH_SPACE (2) ACTION_CANNOT_BE_SYNTHESIZED (3) *all kinds of container scope static error codes, e.g. gress, container type mismatch..

try_slices_to_container_group()

SomeContScopeAllocResult PHV::v2::AllocatorBase::try_slices_to_container_group ( const ScoreContext & ctx, const Allocation & alloc, const FieldSliceAllocStartMap & fs_starts, const ContainerGroup & group, AllocatorMetrics & alloc_metrics ) const

protected

try to find a valid container in group for fs_starts by calling try_slices_to_container on every container of group. The returned result will be the container that has the highest score based on ctx.score()->make(). Premises without BUG_CHECK: (1) AllocSlices that will be generated based on fs_starts will not exceed the size of width of group. (2) ctx score has been initialized. Possible ErrorCode: (1) NOT_ENOUGH_SPACE (2) ACTION_CANNOT_BE_SYNTHESIZED Pruning container group to improve speedup

• Skip containers of the same type (kind and size) if an empty container cannot be allocated
• Skip containers of the same equivalence class which have been tried before NOTE: Above pruning improves phv compilation times by 10x in some cases

pretty-print error messages that aggregates the same failures.

try_super_cluster_to_container_group()

AllocResult PHV::v2::AllocatorBase::try_super_cluster_to_container_group ( const ScoreContext & ctx, const Allocation & alloc, const SuperCluster * sc, const ContainerGroup & group, AllocatorMetrics & alloc_metrics ) const

protected

try to allocate sc with alignment to group. premise: (1) alloc_alignment must have been populated in ctx.

try_wide_arith_slices_to_container_group()

AllocResult PHV::v2::AllocatorBase::try_wide_arith_slices_to_container_group ( const ScoreContext & ctx, const Allocation & alloc, const ScAllocAlignment & alignment, const SuperCluster::SliceList * lo, const SuperCluster::SliceList * hi, const ContainerGroup & group, AllocatorMetrics & alloc_metrics ) const

protected

try to allocate a pair of wide_arith slice lists (lo, hi) to an even-odd pair of containers in group.

verify_can_pack()

const AllocError * PHV::v2::AllocatorBase::verify_can_pack ( const ScoreContext & ctx, const Allocation & alloc, const SuperCluster * sc, const std::vector< AllocSlice > & candidates, const Container & c, ActionSourceCoPackMap & co_pack_hints ) const

protected

Returns

AllocError if can_pack verification failed. NOTE: when c is an empty normal container, a special error with code ACTION_CANNOT_BE_SYNTHESIZED will be returned. It indicates that even if we are allocating candidates to an empty container (assume all other container-scope constraint checks have passed), we still cannot pack or allocate candidates, which usually means that we need to slice the original super cluster, which has the slice list of candidates, differently, to avoid some packings.