Inheritance diagram for DecidePlacement:

[legend]

Classes
class	Backfill

class	BacktrackManagement

class	BacktrackPlacement

class	FinalPlacement

struct	GroupPlace

class	PlacementScore

class	ResourceBasedAlloc

struct	save_placement_t

Public Member Functions
	DecidePlacement (TablePlacement &s)

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 Visitor *	clone () const

virtual ControlFlowVisitor *	controlFlowVisitor ()

virtual void	end_apply ()

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 Visitor &	flow_clone ()

virtual void	flow_merge (Visitor &)

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

Additional Inherited Members
Public Types inherited from P4::Visitor
typedef Visitor_Context	Context

Static Public Member Functions inherited from P4::Visitor
static cstring	demangle (const char *)

static bool	warning_enabled (const Visitor *visitor, int warning_kind)

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

cstring	internalName

SplitFlowVisit_base *&	split_link

SplitFlowVisit_base *	split_link_mem = nullptr

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

Class Documentation

◆ DecidePlacement::save_placement_t

struct DecidePlacement::save_placement_t

Structure that saves various backtracking point for each table. The first index being the stage where this backtracking point is located and the second is the backtracking point itself. We use two maps to carry global and local backtracking point for each table. Global refer to the earliest time this table was placable per stage while local is rebuilt when a table is eligible and have a different backtrack count than previously found. E.g.:

Stage 0 : Eligible Tables = {T0, T1, T2, T3, T4}, Placed Tables = {T0, T3} Stage 1 : Eligible Tables = {T1, T2, T4, T5}, Placed Tables = {T1, T5} Stage 2 : Eligible Tables = {T2, T4, T6}, Placed Tables = {T4}

At this point the early(global) and last_pass(local) map will be the same for all tables

T0 -> Stage 0 T1 -> Stage 0, 1 T2 -> Stage 0, 1, 2 T3 -> Stage 0 T4 -> Stage 0, 1, 2 T5 -> Stage 1 T6 -> Stage 2

At this point if we found that placing table T6 would cause a fitting issue because the downward dependency chain will exceed the resource of the underlying chip, the backtracking mechanism will kick in and try to find an earlier placement for T6. Based on our current map, T6 don't have any previous stages where it was eligible. In this case, the backtracking mechanism will look at control and data dependency for this table and might find that T4 have a control dependency on T6 and if we move that table earlier we can probably fix the T6 dependency problem. By looking at T4 mapping we can see that this table was eligible at stage 0 and 1 as well. Stage 1 will probably be selected at backtracking point if the dependency chain was only missing 1 stage. The result might look like:

Stage 0 : Eligible Tables = {T0, T1, T2, T3, T4}, Placed Tables = {T0, T3} Stage 1 : Eligible Tables = {T1, T2, T4, T5, T6}, Placed Tables = {T4, T6} Stage 2 : Eligible Tables = {T1, T2, T5}, Placed Tables = {T1, T5}

After that backtracking point, the early(global) and last_pass(local) mapping will start to diverge. The backtracking mechanism will always try to find a local point before looking at global one to increase the solution instead of changing it entirely:

   |            Local           |           Global          |

T0 -> | 0 (Same as original) | 0 | T1 -> | 1, 2 (BT include T4) | 0, 1, 2 (Stage 2 is new) | T2 -> | 1, 2 (BT include T4) | 0, 1, 2 | T3 -> | 0 (Same as original) | 0 | T4 -> | 1 (Tried flag set) | 0, 1, 2 | T5 -> | 1, 2 (BT include T4) | 1, 2 (Stage 2 is new) | T6 -> | 1 (BT include T4) | 1, 2 (Stage 1 is new) |

Class Members
map< int, BacktrackPlacement >	early
map< int, BacktrackPlacement >	last_pass

Classes

Public Member Functions

Additional Inherited Members

Class Documentation

◆ DecidePlacement::save_placement_t