#include <OperationDAG.hh>

Inheritance diagram for OperationDAG:

Collaboration diagram for OperationDAG:

Public Member Functions
bool	isNull () const

	OperationDAG ()

	OperationDAG (const class OperationPimpl &op)

	OperationDAG (const OperationDAG &other)

virtual	~OperationDAG ()

bool	isTrivial () const

int	stepsToRoot (const OperationDAGNode &node) const

const OperationDAG::NodeSet &	endNodes () const

const class OperationPimpl &	operation () const

void	setOperation (const class OperationPimpl &op)

Public Member Functions inherited from BoostGraph< OperationDAGNode, OperationDAGEdge >
	BoostGraph (bool allowLoopEdges=true)

	BoostGraph (const TCEString &name, bool allowLoopEdges=true)

	BoostGraph (const BoostGraph &other, bool allowLoopEdges=true)

	~BoostGraph ()

int	nodeCount () const

int	edgeCount () const

Node &	node (const int index) const

Node &	node (const int index, bool cacheResult) const

virtual Edge &	edge (const int index) const

virtual void	addNode (Node &node)

virtual Edge &	outEdge (const Node &node, const int index) const

virtual Edge &	inEdge (const Node &node, const int index) const

virtual EdgeSet	outEdges (const Node &node) const

virtual EdgeSet	inEdges (const Node &node) const

virtual EdgeSet	rootGraphOutEdges (const Node &node) const

virtual EdgeSet	rootGraphInEdges (const Node &node) const

virtual Edge &	rootGraphInEdge (const Node &node, const int index) const

virtual Edge &	rootGraphOutEdge (const Node &node, const int index) const

virtual int	rootGraphInDegree (const Node &node) const

virtual int	rootGraphOutDegree (const Node &node) const

virtual int	outDegree (const Node &node) const

virtual int	inDegree (const Node &node) const

virtual Node &	tailNode (const Edge &edge) const

virtual Node &	headNode (const Edge &edge) const

virtual void	connectNodes (const Node &nTail, const Node &nHead, Edge &e)

virtual void	disconnectNodes (const Node &nTail, const Node &nHead)

virtual void	moveInEdges (const Node &source, const Node &destination)

virtual void	moveOutEdges (const Node &source, const Node &destination)

virtual void	moveInEdge (const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)

virtual void	moveOutEdge (const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false)

virtual void	copyInEdge (const Node &destination, Edge &edge, const Node *tail=NULL)

virtual void	copyOutEdge (const Node &destination, Edge &edge, const Node *head=NULL)

virtual void	removeNode (Node &node)

virtual void	removeEdge (Edge &e)

virtual void	dropNode (Node &node)

virtual void	dropEdge (Edge &edge)

virtual bool	hasEdge (const Node &nTail, const Node &nHead) const

virtual NodeSet	rootNodes () const
	useful utility functions More...

virtual NodeSet	sinkNodes () const

virtual NodeSet	successors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const

virtual NodeSet	predecessors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const

int	maxPathLength (const OperationDAGNode &node) const

int	maxSinkDistance (const OperationDAGNode &node) const

int	maxSourceDistance (const OperationDAGNode &node) const

bool	isInCriticalPath (const OperationDAGNode &node) const

int	height () const

void	findAllPaths () const

void	detachSubgraph (BoostGraph &subGraph)

BoostGraph *	parentGraph ()

BoostGraph *	rootGraph ()

const BoostGraph *	rootGraph () const

bool	hasNode (const Node &) const

virtual const TCEString &	name () const

void	setName (const TCEString &newName)

bool	hasPath (OperationDAGNode &src, const OperationDAGNode &dest) const

void	restoreNodeFromParent (OperationDAGNode &node)

bool	detectIllegalCycles () const

EdgeSet	connectingEdges (const Node &nTail, const Node &nHead) const

Public Member Functions inherited from GraphBase< OperationDAGNode, OperationDAGEdge >
	GraphBase ()

virtual	~GraphBase ()

virtual TCEString	dotString () const

virtual void	writeToDotFile (const TCEString &fileName) const

Static Public Attributes
static OperationDAG	null

Private Attributes
const class OperationPimpl *	op_

std::map< const OperationDAGNode *, int, OperationDAGNode::Comparator >	stepMap_
	Map of known step counts, if dag is changed this must be cleared. More...

OperationDAG::NodeSet	endNodes_
	Set of root nodes of DAG, must be cleared if dag is changed. More...

Additional Inherited Members
Public Types inherited from BoostGraph< OperationDAGNode, OperationDAGEdge >
typedef std::set< OperationDAGNode *, typename OperationDAGNode ::Comparator >	NodeSet

typedef std::set< OperationDAGEdge *, typename OperationDAGEdge ::Comparator >	EdgeSet

typedef OperationDAGNode	Node
	The (base) node type managed by this graph. More...

typedef OperationDAGEdge	Edge
	The (base) edge type managed by this graph. More...

Public Types inherited from GraphBase< OperationDAGNode, OperationDAGEdge >
typedef std::set< OperationDAGNode *, typename OperationDAGNode ::Comparator >	NodeSet

typedef std::set< OperationDAGEdge *, typename OperationDAGEdge ::Comparator >	EdgeSet

typedef OperationDAGNode	Node
	Node type of this graph (possibly, a base class). More...

typedef OperationDAGEdge	Edge
	Edge type of this graph (possibly, a base class). More...

Protected Types inherited from BoostGraph< OperationDAGNode, OperationDAGEdge >
typedef std::set< RemovedEdgeDatum >	RemovedEdgeMap

typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, Node , Edge >	Graph
	Internal graph type, providing actual graph-like operations. This type definition relies on bundled properties of boost library, which need the host compiler to support partial template specialisation. More...

typedef boost::graph_traits< Graph >	GraphTraits
	Traits characterising the internal graph type. More...

typedef GraphTraits::out_edge_iterator	OutEdgeIter
	Output edge iterator type. More...

typedef GraphTraits::in_edge_iterator	InEdgeIter
	Input edge iterator type. More...

typedef GraphTraits::edge_iterator	EdgeIter
	Iterator type for the list of all edges in the graph. More...

typedef GraphTraits::vertex_iterator	NodeIter
	Iterator type for the list of all nodes in the graph. More...

typedef GraphTraits::edge_descriptor	EdgeDescriptor
	Type with which edges of the graph are seen internally. More...

typedef GraphTraits::vertex_descriptor	NodeDescriptor
	Type with which nodes of the graph are seen internally. More...

typedef hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions >	EdgeDescMap

typedef hash_map< const Node *, NodeDescriptor, GraphHashFunctions >	NodeDescMap

typedef std::vector< std::vector< int > >	PathCache

Protected Member Functions inherited from BoostGraph< OperationDAGNode, OperationDAGEdge >
Node &	tailNode (const Edge &edge, const NodeDescriptor &headNode) const

Node &	headNode (const Edge &edge, const NodeDescriptor &tailNode) const

virtual void	connectNodes (const Node &nTail, const Node &nHead, Edge &e, GraphBase< OperationDAGNode, OperationDAGEdge > *modifier, bool creatingSG=false)

void	moveInEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)

virtual void	moveOutEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)

virtual void	removeNode (Node &node, BoostGraph *modifierGraph)

virtual void	removeEdge (Edge &e, const OperationDAGNode tailNode, const OperationDAGNode headNode, BoostGraph *modifierGraph=NULL)

bool	hasEdge (const Node &nTail, const Node &nHead, const Edge &edge) const

bool	hasEdge (const Edge &edge, const Node nTail=NULL, const Node nHead=NULL) const

void	restoreRemovedEdges (RemovedEdgeMap removedEdges)

EdgeDescriptor	descriptor (const Edge &e) const

NodeDescriptor	descriptor (const Node &n) const

EdgeDescriptor	edgeDescriptor (const NodeDescriptor &tailNode, const Edge &e) const

EdgeDescriptor	edgeDescriptor (const Edge &e, const NodeDescriptor &headNode) const

EdgeDescriptor	connectingEdge (const Node &nTail, const Node &nHead) const

void	replaceNodeWithLastNode (OperationDAGNode &dest)

void	calculatePathLengths () const

void	calculatePathLengthsFast () const

void	calculateSinkDistance (const OperationDAGNode &node, int len, bool looping=false) const

void	calculateSourceDistances (const OperationDAGNode *startNode=NULL, int startingLength=0, bool looping=false) const

void	calculatePathLengthsOnConnect (const OperationDAGNode &nTail, const OperationDAGNode &nHead, OperationDAGEdge &e)

void	sinkDistDecreased (const OperationDAGNode &n) const

void	sourceDistDecreased (const OperationDAGNode &n) const

virtual int	edgeWeight (OperationDAGEdge &e, const OperationDAGNode &n) const

void	clearDescriptorCache (EdgeSet edges)

void	constructSubGraph (BoostGraph &subGraph, NodeSet &nodes)

Protected Attributes inherited from BoostGraph< OperationDAGNode, OperationDAGEdge >
std::map< const OperationDAGNode *, int, typename OperationDAGNode ::Comparator >	sourceDistances_

std::map< const OperationDAGNode *, int, typename OperationDAGNode ::Comparator >	sinkDistances_

std::map< const OperationDAGNode *, int, typename OperationDAGNode ::Comparator >	loopingSourceDistances_

std::map< const OperationDAGNode *, int, typename OperationDAGNode ::Comparator >	loopingSinkDistances_

int	height_

Graph	graph_
	The internal graph structure. More...

EdgeDescMap	edgeDescriptors_

NodeDescMap	nodeDescriptors_

BoostGraph< OperationDAGNode, OperationDAGEdge > *	parentGraph_

std::vector< BoostGraph< OperationDAGNode, OperationDAGEdge > * >	childGraphs_

TCEString	name_

int	sgCounter_

std::set< Edge * >	ownedEdges_

bool	allowLoopEdges_

PathCache *	pathCache_

Detailed Description

Definition at line 43 of file OperationDAG.hh.

Constructor & Destructor Documentation

◆ OperationDAG() [1/3]

OperationDAG::OperationDAG ( )

Definition at line 43 of file OperationDAG.cc.

                            :
      BoostGraph<OperationDAGNode,OperationDAGEdge>("NULL_DAG") {
 }

◆ OperationDAG() [2/3]

OperationDAG::OperationDAG ( const class OperationPimpl & op )

◆ OperationDAG() [3/3]

OperationDAG::OperationDAG ( const OperationDAG & other )

Copy constructor.

Parameters

name	The graph can be named for debugging purposes.

Definition at line 62 of file OperationDAG.cc.

                                                     : 
     BoostGraph<OperationDAGNode,OperationDAGEdge>(other) {
 }

◆ ~OperationDAG()

OperationDAG::~OperationDAG ( )

virtual

Destructor.

Deletes all Nodes. Edges are destroyed by destructor of base class.

Definition at line 91 of file OperationDAG.cc.

                             {
     for (int i = 0; i < nodeCount(); i++) {
         delete &node(i);
     }
 }

References BoostGraph< OperationDAGNode, OperationDAGEdge >::node(), and BoostGraph< OperationDAGNode, OperationDAGEdge >::nodeCount().

Here is the call graph for this function:

Member Function Documentation

◆ endNodes()

const OperationDAG::NodeSet & OperationDAG::endNodes ( ) const

Returns set of end nodes of a DAG.

Returns: Set of end nodes of a DAG.

Definition at line 137 of file OperationDAG.cc.

                              {
     if (endNodes_.empty()) {
         for (int i = 0; i < nodeCount(); i++) {
             OperationDAGNode& curr = node(i);
             if (outDegree(curr) == 0) {
                 endNodes_.insert(&curr);
             }
         }
     }
     return endNodes_;
 } 

References endNodes_, BoostGraph< OperationDAGNode, OperationDAGEdge >::node(), BoostGraph< OperationDAGNode, OperationDAGEdge >::nodeCount(), and BoostGraph< OperationDAGNode, OperationDAGEdge >::outDegree().

Referenced by MemoryAliasAnalyzer::findTwoPartAddressOperands(), MemoryAliasAnalyzer::mausOfOperation(), TDGen::operationPattern(), TDGen::subPattern(), and TDGen::writeEmulationPattern().

Here is the call graph for this function:

◆ isNull()

bool OperationDAG::isNull ( ) const

inline

Definition at line 48 of file OperationDAG.hh.

48 { return this == &null; }

Referenced by OperationDAGBehavior::canBeSimulated(), ProGeTools::canGenerateFromDAG(), Automagic::canGenerateFromDAG(), OperationPimpl::clear(), OperationDAGSelector::createExpandedDAG(), OperationPimpl::dag(), Automagic::dagLatency(), ProGeTools::dagLatency(), OperationPimpl::setDagCode(), and OperationDAGDialog::updateDAG().

◆ isTrivial()

bool OperationDAG::isTrivial ( ) const

Returns true if dag is the simplest possible.

Returns: true if dag is the simplest possible.

Definition at line 72 of file OperationDAG.cc.

                               { 
     int opNodeCount = 0;
     for (int i = 0; i < nodeCount(); i++) {
         
         if (dynamic_cast<OperationNode*>(&node(i)) != NULL) {
             opNodeCount++;
             if (opNodeCount > 1) {
                 return false;
             }
         }
     }
     return true;
 }

References BoostGraph< OperationDAGNode, OperationDAGEdge >::node(), and BoostGraph< OperationDAGNode, OperationDAGEdge >::nodeCount().

Here is the call graph for this function:

◆ operation()

const class OperationPimpl& OperationDAG::operation ( ) const

inline

Definition at line 59 of file OperationDAG.hh.

59 { assert(op_ != nullptr); return *op_; }

References assert, and op_.

Referenced by FUGen::constantName(), FUGen::DAGNodeOperandWidth(), FUGen::subOpConnection(), and OperationDAGConverter::writeNode().

◆ setOperation()

void OperationDAG::setOperation ( const class OperationPimpl & op )

inline

Definition at line 60 of file OperationDAG.hh.

60 { op_ = &op; }

References op_.

◆ stepsToRoot()

int OperationDAG::stepsToRoot ( const OperationDAGNode & node ) const

Finds recursively step count to root for an operation and writes data to operation step map.

Once O(n), after O(log(n))

Parameters

node	Node, whose step count is wanted.

Returns: Number of maximum steps that are needed to reach this node from root nodes.

Definition at line 108 of file OperationDAG.cc.

                                                             {
     
     if (stepMap_.find(&node) == stepMap_.end()) {
         int maxSteps = 0;
  
         for (int i = 0; i < inDegree(node); i++) {
             OperationDAGNode& rootNode = tailNode(inEdge(node, i));
             int routeSteps = stepsToRoot(rootNode);            
             if (routeSteps > maxSteps) {
                 maxSteps = routeSteps;
             }
         }
         
         if (inDegree(node) == 0) {
             stepMap_[&node] = 0;
         } else {
             stepMap_[&node] = maxSteps + 1;
         }
     }
  
     return stepMap_[&node];
 }

References BoostGraph< OperationDAGNode, OperationDAGEdge >::inDegree(), BoostGraph< OperationDAGNode, OperationDAGEdge >::inEdge(), BoostGraph< OperationDAGNode, OperationDAGEdge >::node(), stepMap_, and BoostGraph< OperationDAGNode, OperationDAGEdge >::tailNode().

Referenced by OperationDAGConverter::writeNode().

Here is the call graph for this function:

Member Data Documentation

◆ endNodes_

OperationDAG::NodeSet OperationDAG::endNodes_

mutableprivate

Set of root nodes of DAG, must be cleared if dag is changed.

Definition at line 68 of file OperationDAG.hh.

Referenced by endNodes().

◆ null

OperationDAG OperationDAG::null

static

Definition at line 47 of file OperationDAG.hh.

Referenced by OperationPimpl::addDag(), OperationPimpl::dag(), OperationPimpl::removeDag(), OperationPimpl::setDagCode(), and OperationDAGSelector::OperationDAGList::smallestNodeCount().

◆ op_

const class OperationPimpl* OperationDAG::op_

private

Definition at line 62 of file OperationDAG.hh.

Referenced by operation(), and setOperation().

◆ stepMap_

std::map<const OperationDAGNode*, int, OperationDAGNode::Comparator> OperationDAG::stepMap_

mutableprivate

Map of known step counts, if dag is changed this must be cleared.

Definition at line 66 of file OperationDAG.hh.

Referenced by stepsToRoot().

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

Public Member Functions

Static Public Attributes

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ OperationDAG() [1/3]

◆ OperationDAG() [2/3]

◆ OperationDAG() [3/3]

◆ ~OperationDAG()

Member Function Documentation

◆ endNodes()

◆ isNull()

◆ isTrivial()

◆ operation()

◆ setOperation()

◆ stepsToRoot()

Member Data Documentation

◆ endNodes_

◆ null

◆ op_

◆ stepMap_