#include <utils.h>

Inheritance diagram for PHV::Allocation:

Classes
struct	AvailableSpot
	Available bits of this allocation. More...

struct	ConditionalConstraintData

struct	ContainerStatus

Public Types
using	ConditionalConstraint = ordered_map<PHV::FieldSlice, ConditionalConstraintData>

using	ConditionalConstraints = ordered_map<int, ConditionalConstraint>

using	const_iterator = ordered_map<PHV::Container, ContainerStatus>::const_iterator

enum class	ContainerAllocStatus { EMPTY , PARTIAL , FULL }

enum class	ExtractSource { NONE , PACKET , NON_PACKET }

using	FieldStatus = ordered_set<AllocSlice>

using	GressAssignment = std::optional<gress_t>

using	LiveRangeShrinkingMap = ordered_map<const PHV::Field *, ActionSet>

using	MutuallyLiveSlices = ordered_set<AllocSlice>

Public Member Functions
void	addARAedge (gress_t grs, const IR::MAU::Table src, const IR::MAU::Table dst) const
	Add a pair of tables in the ara_edges for a new ARA table.

bool	addDarkAllocation (const AllocSlice &slice)

virtual void	addMetadataInitialization (AllocSlice slice, LiveRangeShrinkingMap initNodes)

virtual ContainerAllocStatus	alloc_status (PHV::Container c) const

virtual void	allocate (const AllocSlice slice, LiveRangeShrinkingMap *initNodes=nullptr, bool singleGressParserGroup=false)

std::set< AvailableSpot >	available_spots () const
	Return a set of available spots of this allocation.

virtual const_iterator	begin () const =0
	Iterate through container-->allocation slices.

virtual MutuallyLiveSlices	byteSlicesByLiveness (const PHV::Container c, const AllocSlice &sl, const PragmaNoInit &noInit) const

Transaction *	clone (const Allocation &parent) const
	Extract the child from the parent transaction and return a cloned version of the difference.

cstring	commit (Transaction &view)

virtual bool	contains (PHV::Container c) const =0

virtual GressAssignment	deparserGroupGress (PHV::Container c) const

int	empty_containers (PHV::Size size) const

virtual const_iterator	end () const =0

void	foreach_slice (const PHV::Field *f, le_bitrange range, int stage, PHV::FieldUse access, std::function< void(const AllocSlice &)> cb) const

void	foreach_slice (const PHV::Field *f, le_bitrange range, std::function< void(const AllocSlice &)> cb) const

virtual void	foreach_slice (const PHV::Field *f, std::function< void(const AllocSlice &)> cb) const =0

void	foreach_slice (PHV::Container c, int stage, PHV::FieldUse access, std::function< void(const AllocSlice &)> cb) const

void	foreach_slice (PHV::Container c, le_bitrange range, int stage, PHV::FieldUse access, std::function< void(const AllocSlice &)> cb) const

void	foreach_slice (PHV::Container c, le_bitrange range, std::function< void(const AllocSlice &)> cb) const

void	foreach_slice (PHV::Container c, std::function< void(const AllocSlice &)> cb) const

const ordered_map< gress_t, ordered_map< const IR::MAU::Table , std::set< const IR::MAU::Table > > > &	getARAedges () const

virtual std::optional< ActionSet >	getInitPoints (const AllocSlice &slice) const

virtual ActionSet	getInitPointsForField (const PHV::Field *f) const

virtual const ordered_set< const PHV::Field * >	getMetadataInits (const IR::MAU::Action *act) const

const ordered_map< const IR::BFN::ParserState *, std::set< PHV::Container > > &	getParserStateToContainers (const PhvInfo &phv, const MapFieldToParserStates &field_to_parser_states) const

virtual const ContainerStatus *	getStatus (const PHV::Container &c) const =0

virtual FieldStatus	getStatus (const PHV::Field *f) const =0

const ordered_set< unsigned >	getTagalongCollectionsUsed () const

virtual GressAssignment	gress (const PHV::Container &c) const

virtual bool	isDarkReadAvailable (PHV::Container c, unsigned minStage, unsigned maxStage) const

virtual bool	isDarkWriteAvailable (PHV::Container c, unsigned minStage, unsigned maxStage) const

virtual MutuallyLiveSlices	liverange_overlapped_slices (const PHV::Container c, const std::vector< AllocSlice > &slices) const

virtual Transaction	makeTransaction () const
	Create a Transaction based on this Allocation.

virtual ExtractSource	parserExtractGroupSource (PHV::Container c) const

virtual GressAssignment	parserGroupGress (PHV::Container c) const

std::string	printARAedges () const

virtual void	removeAllocatedSlice (const ordered_set< PHV::AllocSlice > &slices)

virtual size_t	size () const =0

ordered_set< PHV::AllocSlice >	slices (const PHV::Field *f) const

ordered_set< PHV::AllocSlice >	slices (const PHV::Field *f, int stage, PHV::FieldUse access) const

ordered_set< PHV::AllocSlice >	slices (const PHV::Field *f, le_bitrange range) const

ordered_set< PHV::AllocSlice >	slices (const PHV::Field *f, le_bitrange range, int stage, PHV::FieldUse access) const

ordered_set< AllocSlice >	slices (PHV::Container c) const

ordered_set< AllocSlice >	slices (PHV::Container c, int stage, PHV::FieldUse access) const

ordered_set< AllocSlice >	slices (PHV::Container c, le_bitrange range) const

ordered_set< AllocSlice >	slices (PHV::Container c, le_bitrange range, int stage, PHV::FieldUse access) const

virtual MutuallyLiveSlices	slicesByLiveness (const PHV::Container c, const AllocSlice &sl) const

virtual MutuallyLiveSlices	slicesByLiveness (const PHV::Container c, std::vector< AllocSlice > &slices) const

virtual std::vector< MutuallyLiveSlices >	slicesByLiveness (PHV::Container c) const

virtual cstring	toString () const

Protected Member Functions
	Allocation (const PhvInfo &phv, const PhvUse &uses, bool isTrivial=false)

ordered_map< AllocSlice, ActionSet > &	get_meta_init_points () const

Protected Attributes
ordered_map< gress_t, ordered_map< const IR::MAU::Table , std::set< const IR::MAU::Table > > >	ara_edges

ordered_map< PHV::Container, ContainerStatus >	container_status_i

assoc::hash_map< PHV::Size, ordered_map< ContainerAllocStatus, int > >	count_by_status_i

ordered_map< PHV::Container, bitvec >	dark_containers_read_allocated_i

ordered_map< PHV::Container, bitvec >	dark_containers_write_allocated_i

ordered_map< const PHV::Field *, FieldStatus >	field_status_i

DarkInitMap	init_map_i
	Initialization information about allocating to dark containers during certain stages.

ordered_map< const IR::MAU::Action , ordered_set< const PHV::Field > >	init_writes_i

bool	isTrivial

ordered_map< AllocSlice, ActionSet >	meta_init_points_i

const PhvInfo *	phv_i

ordered_map< const IR::BFN::ParserState *, std::set< PHV::Container > >	state_to_containers_i
	parser state to containers

const PhvUse *	uses_i

Friends
class	AllocationReport

class	Transaction

Detailed Description

Keep track of the allocation of field slices to container slices, as well as the gress assignment of containers. Support speculative allocation and rollbacks with the Transaction mechanism.

Class Documentation

◆ PHV::Allocation::ContainerStatus

struct PHV::Allocation::ContainerStatus

This struct tracks PHV container state that can change during the course of allocation, such as the thread to which this container must be assigned, or the field slices that have been allocated to it. Because PHV allocation queries container status many, many times, this struct also contains a derived alloc_status, which summarizes the state of the container.

Class Members
ContainerAllocStatus	alloc_status
GressAssignment	deparserGroupGress
GressAssignment	gress
ExtractSource	parserExtractGroupSource
GressAssignment	parserGroupGress
ordered_set< AllocSlice >	slices

Member Function Documentation

◆ addDarkAllocation()

bool PHV::Allocation::addDarkAllocation ( const AllocSlice & slice )

Add slice allocated to a dark container to the current Allocation object.

Returns: true if the addition was successful.

◆ addMetadataInitialization()

void PHV::Allocation::addMetadataInitialization	(	PHV::AllocSlice	slice,
		LiveRangeShrinkingMap	initNodes )

virtual

Uniform convenience abstraction for adding a metadata initialization node to the allocation object.

◆ alloc_status()

PHV::Allocation::ContainerAllocStatus PHV::Allocation::alloc_status ( PHV::Container c ) const

virtual

Returns: the allocation status of c and fails if c is not present.

◆ allocate()

void PHV::Allocation::allocate	(	const AllocSlice	slice,
		LiveRangeShrinkingMap *	initNodes = nullptr,
		bool	singleGressParserGroup = false )

virtual

Assign @slice to @slice.container, updating the gress information of the container and its MAU group if necessary. Fails if the gress of @slice.field does not match any gress in the MAU group.

Note that this adds new slices but does not remove or overwrite existing slices.

Assign slice to slice.container, updating the gress information of the container and its MAU group if necessary. Fails if the gress of slice.field does not match any gress in the MAU group.

◆ begin()

virtual const_iterator PHV::Allocation::begin ( ) const

pure virtual

Iterate through container-->allocation slices.

Implemented in PHV::ConcreteAllocation, and PHV::Transaction.

◆ commit()

cstring PHV::Allocation::commit ( Transaction & view )

Update this allocation with any new allocation in view. Note that this may add new slices but does not remove or overwrite existing slices.

◆ contains()

virtual bool PHV::Allocation::contains ( PHV::Container c ) const

pure virtual

Returns: true if this allocation owns c.

Implemented in PHV::ConcreteAllocation, and PHV::Transaction.

◆ deparserGroupGress()

PHV::Allocation::GressAssignment PHV::Allocation::deparserGroupGress ( PHV::Container c ) const

virtual

Returns: the gress of c's deparser group, if any. If a container holds deparsed fields, then its gress must match that of its deparser group.

◆ empty_containers()

int PHV::Allocation::empty_containers ( PHV::Size size ) const

Returns: the number of empty containers of size size.

◆ end()

virtual const_iterator PHV::Allocation::end ( ) const

pure virtual

Implemented in PHV::Transaction.

◆ get_meta_init_points()

ordered_map< AllocSlice, ActionSet > & PHV::Allocation::get_meta_init_points ( ) const

inlineprotected

Returns: the meta_init_points_i map for the current allocation object.

◆ getARAedges()

const ordered_map< gress_t, ordered_map< const IR::MAU::Table *, std::set< const IR::MAU::Table * > > > & PHV::Allocation::getARAedges ( ) const

inline

Returns: the map of source tables to the set of target tables connected through the ARA overlays

◆ getInitPoints()

std::optional< PHV::ActionSet > PHV::Allocation::getInitPoints ( const AllocSlice & slice ) const

virtual

Returns: the set of actions where slice must be initialized for overlay enabled by live range shrinking.

Reimplemented in PHV::Transaction.

◆ getInitPointsForField()

PHV::ActionSet PHV::Allocation::getInitPointsForField ( const PHV::Field * f ) const

virtual

Returns: the set of initialization actions for the field f.

Reimplemented in PHV::Transaction.

◆ getMetadataInits()

const ordered_set< const PHV::Field * > PHV::Allocation::getMetadataInits ( const IR::MAU::Action * act ) const

virtual

Returns: all the fields that must be initialized in action act.

Reimplemented in PHV::Transaction.

◆ getParserStateToContainers()

const ordered_map< const IR::BFN::ParserState *, std::set< PHV::Container > > & PHV::Allocation::getParserStateToContainers	(	const PhvInfo &	phv,
		const MapFieldToParserStates &	field_to_parser_states ) const

Returns: map from parser state to containers

◆ getStatus() [1/2]

virtual const ContainerStatus * PHV::Allocation::getStatus ( const PHV::Container & c ) const

pure virtual

Uniform abstraction for accessing a container state.

Returns: the ContainerStatus of this allocation, if present. Failing that, check its ancestors. If has no status yet, return nullptr.

Implemented in PHV::ConcreteAllocation, and PHV::Transaction.

◆ getStatus() [2/2]

virtual FieldStatus PHV::Allocation::getStatus ( const PHV::Field * f ) const

pure virtual

Uniform abstraction for accessing field state.

Returns: the FieldStatus of this allocation, if present. Failing that, check its ancestors. If f has no status yet, return an empty FieldStatus.

Implemented in PHV::ConcreteAllocation, and PHV::Transaction.

◆ getTagalongCollectionsUsed()

const ordered_set< unsigned > PHV::Allocation::getTagalongCollectionsUsed ( ) const

Returns: all tagalong collection IDs used

◆ gress()

PHV::Allocation::GressAssignment PHV::Allocation::gress ( const PHV::Container & c ) const

virtual

Returns: the container status of and fails if is not present.

◆ isDarkReadAvailable()

virtual bool PHV::Allocation::isDarkReadAvailable	(	PHV::Container	c,
		unsigned	minStage,
		unsigned	maxStage ) const

inlinevirtual

Returns: false if a dark container is used for the read half cycle in between stages minStage and maxStage.

Reimplemented in PHV::Transaction.

◆ isDarkWriteAvailable()

virtual bool PHV::Allocation::isDarkWriteAvailable	(	PHV::Container	c,
		unsigned	minStage,
		unsigned	maxStage ) const

inlinevirtual

Returns: false if a dark container is used for the write half cycle in between stages minStage and maxStage.

Reimplemented in PHV::Transaction.

◆ liverange_overlapped_slices()

PHV::Allocation::MutuallyLiveSlices PHV::Allocation::liverange_overlapped_slices	(	const PHV::Container	c,
		const std::vector< AllocSlice > &	slices ) const

virtual

Returns: a set of allocated slices that will live at the some stage in container c with any of the candidate slice in slices, i.e., not mutex and liverange not disjoint.

◆ makeTransaction()

PHV::Transaction PHV::Allocation::makeTransaction ( ) const

virtual

Create a Transaction based on this Allocation.

See also: PHV::Transaction for details.

◆ parserExtractGroupSource()

PHV::Allocation::ExtractSource PHV::Allocation::parserExtractGroupSource ( PHV::Container c ) const

virtual

Returns: the source of c's parser extract group. All containers in a group must have the same source.

◆ parserGroupGress()

PHV::Allocation::GressAssignment PHV::Allocation::parserGroupGress ( PHV::Container c ) const

virtual

Returns: the gress of c's parser group, if any. If a container holds extracted fields, then its gress must match that of its parser group.

◆ size()

virtual size_t PHV::Allocation::size ( ) const

pure virtual

Returns: number of containers owned by this allocation.

Implemented in PHV::ConcreteAllocation, and PHV::Transaction.

◆ slices() [1/5]

ordered_set< PHV::AllocSlice > PHV::Allocation::slices ( const PHV::Field * f ) const

inline

Returns: the set of slices allocated for the field f in this Allocation. May be empty (if f is not allocated) or contain slices that do not fully cover all bits of f (if f is only partially allocated).

◆ slices() [2/5]

ordered_set< PHV::AllocSlice > PHV::Allocation::slices	(	const PHV::Field *	f,
		le_bitrange	range ) const

Returns: all slices allocated for f that include any part of range in the field portion of the allocated slice. May be empty (if f is not allocated) or contain slices that do not fully cover all bits of f (if f is only partially allocated).

◆ slices() [3/5]

ordered_set< PHV::AllocSlice > PHV::Allocation::slices ( PHV::Container c ) const

Returns: all the slices allocated to c.

◆ slices() [4/5]

ordered_set< PHV::AllocSlice > PHV::Allocation::slices	(	PHV::Container	c,
		int	stage,
		PHV::FieldUse	access ) const

Returns: all the slices allocated to c and valid in the stage stage.

◆ slices() [5/5]

ordered_set< PHV::AllocSlice > PHV::Allocation::slices	(	PHV::Container	c,
		le_bitrange	range ) const

Returns: all the slices allocated to c that overlap with range.

◆ slicesByLiveness() [1/2]

PHV::Allocation::MutuallyLiveSlices PHV::Allocation::slicesByLiveness	(	const PHV::Container	c,
		const AllocSlice &	sl ) const

virtual

Returns: a set of slices allocated to c that are all live at the same time as sl The previous function (slicesByLiveness(c)) constructs a vector of sets of slices that are live in the container at the same time; the same slice may be found in multiple sets in this case. By contrast, slicesByLiveness(c, sl) uses the mutex_i member to determine all the field slices that are not mutually exclusive with the candidate slice, and returns a set of all such slices. For example, suppose the following slices are allocated to a container c:

c[4:7]<--f2[0:3]

c[4:7]<--f3[0:3]

where f2 and f3 are overlaid and hence mutex_i(f2, f3) = true. If slice sl is f1[0:3], such that mutex_i(f1, f2) = false and mutex_i(f1, f3) = false, a call to slicesByLiveness(c, f1[0:3]) would return the set {f2[0:3], f3[0:3]}.

◆ slicesByLiveness() [2/2]

std::vector< PHV::Allocation::MutuallyLiveSlices > PHV::Allocation::slicesByLiveness ( PHV::Container c ) const

virtual

The allocation manager keeps a list of combinations of slices that are live in the container at the same time, as well as the thread assignment of the container (if any). For example, suppose the following slices are allocated to a container c:

c[0:3]<–f1[0:3] c[4:7]<–f2[0:3] c[4:7]<–f3[0:3]

where f2 and f3 are overlaid. There are then two sets of slices that are live in the container at the same time:

c[0:3]<–f1[0:3] c[4:7]<–f2[0:3]

and

c[0:3]<–f1[0:3] c[4:7]<–f3[0:3]

When analyzing cohabit constraints, it's important to only compare fields that are live.

Note that the same slice may appear in more than one list.

Returns: the sets of slices allocated to that can be live at the same time.

◆ toString()

cstring PHV::Allocation::toString ( ) const

virtual

Returns: a pretty-printed representation of this Allocation.

Member Data Documentation

◆ ara_edges

ordered_map<gress_t, ordered_map<const IR::MAU::Table *, std::set<const IR::MAU::Table *> > > PHV::Allocation::ara_edges

mutableprotected

For each gress keep track of potential control flow edges implied from/to AlwaysRunAction tables

◆ dark_containers_write_allocated_i

ordered_map<PHV::Container, bitvec> PHV::Allocation::dark_containers_write_allocated_i

mutableprotected

Dark containers allocated in this allocation mapped to the stages that they are allocated to. The read map captures the allocation from the perspective of a read of that container while the write map captures the allocation from the perspective of a write to that container.

◆ init_writes_i

ordered_map<const IR::MAU::Action *, ordered_set<const PHV::Field *> > PHV::Allocation::init_writes_i

mutableprotected

Structure that remembers actions at which metadata initialization for various fields has been added.

◆ meta_init_points_i

ordered_map<AllocSlice, ActionSet> PHV::Allocation::meta_init_points_i

mutableprotected

Structure that remembers the actions at which metadata fields need to be initialized for a particular allocation object.

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Class Documentation

◆ PHV::Allocation::ContainerStatus

Member Function Documentation

◆ addDarkAllocation()

◆ addMetadataInitialization()

◆ alloc_status()

◆ allocate()

◆ begin()

◆ commit()

◆ contains()

◆ deparserGroupGress()

◆ empty_containers()

◆ end()

◆ get_meta_init_points()

◆ getARAedges()

◆ getInitPoints()

◆ getInitPointsForField()

◆ getMetadataInits()

◆ getParserStateToContainers()

◆ getStatus() [1/2]

◆ getStatus() [2/2]

◆ getTagalongCollectionsUsed()

◆ gress()

◆ isDarkReadAvailable()

◆ isDarkWriteAvailable()

◆ liverange_overlapped_slices()

◆ makeTransaction()

◆ parserExtractGroupSource()

◆ parserGroupGress()

◆ size()

◆ slices() [1/5]

◆ slices() [2/5]

◆ slices() [3/5]

◆ slices() [4/5]

◆ slices() [5/5]

◆ slicesByLiveness() [1/2]

◆ slicesByLiveness() [2/2]

◆ toString()

Member Data Documentation

◆ ara_edges

◆ dark_containers_write_allocated_i

◆ init_writes_i

◆ meta_init_points_i