Array of linked list that maintains the dependencies between producing instructions and consuming instructions. More...

#include <dep_graph.hh>

Public Types
typedef DependencyEntry< DynInstPtr >	DepEntry

Public Member Functions
	DependencyGraph ()
	Default construction. More...

	~DependencyGraph ()

void	resize (int num_entries)
	Resize the dependency graph to have num_entries registers. More...

void	reset ()
	Clears all of the linked lists. More...

void	insert (PhysRegIndex idx, const DynInstPtr &new_inst)
	Inserts an instruction to be dependent on the given index. More...

void	setInst (PhysRegIndex idx, const DynInstPtr &new_inst)
	Sets the producing instruction of a given register. More...

void	clearInst (PhysRegIndex idx)
	Clears the producing instruction. More...

void	remove (PhysRegIndex idx, const DynInstPtr &inst_to_remove)
	Removes an instruction from a single linked list. More...

DynInstPtr	pop (PhysRegIndex idx)
	Removes and returns the newest dependent of a specific register. More...

bool	empty () const
	Checks if the entire dependency graph is empty. More...

bool	empty (PhysRegIndex idx) const
	Checks if there are any dependents on a specific register. More...

void	dump ()
	Debugging function to dump out the dependency graph. More...

Public Attributes
uint64_t	nodesTraversed

uint64_t	nodesRemoved

Private Attributes
std::vector< DepEntry >	dependGraph
	Array of linked lists. More...

int	numEntries
	Number of linked lists; identical to the number of registers. More...

unsigned	memAllocCounter

Detailed Description

template<class DynInstPtr>
class DependencyGraph< DynInstPtr >

Array of linked list that maintains the dependencies between producing instructions and consuming instructions.

Each linked list represents a single physical register, having the future producer of the register's value, and all consumers waiting on that value on the list. The head node of each linked list represents the producing instruction of that register. Instructions are put on the list upon reaching the IQ, and are removed from the list either when the producer completes, or the instruction is squashed.

Definition at line 71 of file dep_graph.hh.

Member Typedef Documentation

◆ DepEntry

template<class DynInstPtr >

typedef DependencyEntry<DynInstPtr> DependencyGraph< DynInstPtr >::DepEntry

Definition at line 74 of file dep_graph.hh.

Constructor & Destructor Documentation

◆ DependencyGraph()

template<class DynInstPtr >

DependencyGraph< DynInstPtr >::DependencyGraph ( )

inline

Default construction.

Must call resize() prior to use.

Definition at line 77 of file dep_graph.hh.

◆ ~DependencyGraph()

template<class DynInstPtr >

DependencyGraph< DynInstPtr >::~DependencyGraph

Definition at line 139 of file dep_graph.hh.

Member Function Documentation

◆ clearInst()

template<class DynInstPtr >

void DependencyGraph< DynInstPtr >::clearInst ( PhysRegIndex idx )

inline

Clears the producing instruction.

Definition at line 97 of file dep_graph.hh.

References DependencyGraph< DynInstPtr >::dependGraph.

◆ dump()

template<class DynInstPtr >

void DependencyGraph< DynInstPtr >::dump

Debugging function to dump out the dependency graph.

Definition at line 269 of file dep_graph.hh.

References cprintf(), ArmISA::i, DependencyEntry< DynInstPtr >::inst, and DependencyEntry< DynInstPtr >::next.

◆ empty() [1/2]

template<class DynInstPtr >

bool DependencyGraph< DynInstPtr >::empty

Checks if the entire dependency graph is empty.

Definition at line 258 of file dep_graph.hh.

References ArmISA::i.

◆ empty() [2/2]

template<class DynInstPtr >

bool DependencyGraph< DynInstPtr >::empty ( PhysRegIndex idx ) const

inline

Checks if there are any dependents on a specific register.

Definition at line 110 of file dep_graph.hh.

References DependencyGraph< DynInstPtr >::dependGraph.

◆ insert()

template<class DynInstPtr >

void DependencyGraph< DynInstPtr >::insert	(	PhysRegIndex	idx,
		const DynInstPtr &	new_inst
	)

Inserts an instruction to be dependent on the given index.

Definition at line 182 of file dep_graph.hh.

References DependencyEntry< DynInstPtr >::inst, and DependencyEntry< DynInstPtr >::next.

◆ pop()

template<class DynInstPtr >

DynInstPtr DependencyGraph< DynInstPtr >::pop ( PhysRegIndex idx )

Removes and returns the newest dependent of a specific register.

Definition at line 241 of file dep_graph.hh.

References DependencyEntry< DynInstPtr >::inst, and DependencyEntry< DynInstPtr >::next.

◆ remove()

template<class DynInstPtr >

void DependencyGraph< DynInstPtr >::remove	(	PhysRegIndex	idx,
		const DynInstPtr &	inst_to_remove
	)

Removes an instruction from a single linked list.

Definition at line 203 of file dep_graph.hh.

References DependencyEntry< DynInstPtr >::inst, and DependencyEntry< DynInstPtr >::next.

◆ reset()

template<class DynInstPtr >

void DependencyGraph< DynInstPtr >::reset

Clears all of the linked lists.

Definition at line 153 of file dep_graph.hh.

References ArmISA::i, DependencyEntry< DynInstPtr >::inst, and DependencyEntry< DynInstPtr >::next.

◆ resize()

template<class DynInstPtr >

void DependencyGraph< DynInstPtr >::resize ( int num_entries )

Resize the dependency graph to have num_entries registers.

Definition at line 145 of file dep_graph.hh.

◆ setInst()

template<class DynInstPtr >

void DependencyGraph< DynInstPtr >::setInst	(	PhysRegIndex	idx,
		const DynInstPtr &	new_inst
	)

inline

Sets the producing instruction of a given register.

Definition at line 93 of file dep_graph.hh.

References DependencyGraph< DynInstPtr >::dependGraph.

Member Data Documentation

◆ dependGraph

template<class DynInstPtr >

std::vector<DepEntry> DependencyGraph< DynInstPtr >::dependGraph

private

Array of linked lists.

Each linked list is a list of all the instructions that depend upon a given register. The actual register's index is used to index into the graph; ie all instructions in flight that are dependent upon r34 will be in the linked list of dependGraph[34].

Definition at line 123 of file dep_graph.hh.

Referenced by DependencyGraph< DynInstPtr >::clearInst(), DependencyGraph< DynInstPtr >::empty(), and DependencyGraph< DynInstPtr >::setInst().

◆ memAllocCounter

template<class DynInstPtr >

unsigned DependencyGraph< DynInstPtr >::memAllocCounter

private

Definition at line 129 of file dep_graph.hh.

◆ nodesRemoved

template<class DynInstPtr >

uint64_t DependencyGraph< DynInstPtr >::nodesRemoved

Definition at line 135 of file dep_graph.hh.

◆ nodesTraversed

template<class DynInstPtr >

uint64_t DependencyGraph< DynInstPtr >::nodesTraversed

Definition at line 133 of file dep_graph.hh.

◆ numEntries

template<class DynInstPtr >

int DependencyGraph< DynInstPtr >::numEntries

private

Number of linked lists; identical to the number of registers.

Definition at line 126 of file dep_graph.hh.

The documentation for this class was generated from the following file:

cpu/o3/dep_graph.hh

Public Types

Public Member Functions

Public Attributes

Private Attributes

Detailed Description

template<class DynInstPtr> class DependencyGraph< DynInstPtr >

Member Typedef Documentation

◆ DepEntry

Constructor & Destructor Documentation

◆ DependencyGraph()

◆ ~DependencyGraph()

Member Function Documentation

◆ clearInst()

◆ dump()

◆ empty() [1/2]

◆ empty() [2/2]

◆ insert()

◆ pop()

◆ remove()

◆ reset()

◆ resize()

◆ setInst()

Member Data Documentation

◆ dependGraph

◆ memAllocCounter

◆ nodesRemoved

◆ nodesTraversed

◆ numEntries

template<class DynInstPtr>
class DependencyGraph< DynInstPtr >