#include <ControlDependenceGraph.hh>

Inheritance diagram for ControlDependenceGraph:

Collaboration diagram for ControlDependenceGraph:

Public Types
enum	CompareResult { A_BEFORE_B , B_BEFORE_A , ANY_ORDER , UNORDERABLE , ERROR }

Public Types inherited from BoostGraph< ControlDependenceNode, ControlDependenceEdge >
typedef std::set< ControlDependenceNode *, typename GraphNode::Comparator >	NodeSet

typedef std::set< ControlDependenceEdge *, typename GraphEdge::Comparator >	EdgeSet

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

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

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

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

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

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

Public Member Functions
	ControlDependenceGraph (const ControlFlowGraph &cGraph)

virtual	~ControlDependenceGraph ()

int	alignment () const

TTAProgram::Program *	program () const

ControlDependenceNode &	entryNode ()

void	analyzeCDG ()

bool	analyzed () const

int	componentCount () const

Public Member Functions inherited from BoostGraph< ControlDependenceNode, ControlDependenceEdge >
	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

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 ControlDependenceNode &node) const

int	maxSinkDistance (const ControlDependenceNode &node) const

int	maxSourceDistance (const ControlDependenceNode &node) const

bool	isInCriticalPath (const ControlDependenceNode &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 (ControlDependenceNode &src, const ControlDependenceNode &dest) const

void	restoreNodeFromParent (ControlDependenceNode &node)

bool	detectIllegalCycles () const

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

Public Member Functions inherited from GraphBase< GraphNode, GraphEdge >
	GraphBase ()

virtual	~GraphBase ()

virtual int	outDegree (const Node &node) const =0

virtual int	inDegree (const Node &node) const =0

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

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

virtual EdgeSet	outEdges (const Node &node) const =0

virtual EdgeSet	inEdges (const Node &node) const =0

virtual Node &	tailNode (const Edge &edge) const =0

virtual Node &	headNode (const Edge &edge) const =0

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

virtual EdgeSet	connectingEdges (const Node &nTail, const Node &nHead) const =0

virtual TCEString	dotString () const

virtual void	writeToDotFile (const TCEString &fileName) const

virtual void	addNode (Node &node)=0

virtual void	removeNode (Node &node)=0

virtual void	removeEdge (Edge &e)=0

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

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

Private Types
typedef std::map< ControlFlowGraph::NodeDescriptor, int >	PostOrderMap
	Stores data to compute post order relation on CFG.

typedef boost::associative_property_map< PostOrderMap >	PostOrder

typedef std::map< NodeDescriptor, int >	CDGOrderMap
	Stores data to compute post order relation on CDG and strong components.

typedef boost::associative_property_map< CDGOrderMap >	CDGOrder

typedef std::map< NodeDescriptor, NodeDescriptor >	DescriptorMap
	Storage for relations between nodes.

typedef boost::associative_property_map< DescriptorMap >	Descriptors

typedef std::map< NodeDescriptor, boost::default_color_type >	ColorMap
	Storage for color property used by dfs.

typedef boost::associative_property_map< ColorMap >	Color

typedef std::pair< Node *, Edge::CDGEdgeType >	SourceType

typedef std::vector< SourceType >	DependentOn

typedef std::vector< BasicBlockNode * >	BlockVector

typedef std::map< Node , DependentOn , Node::Comparator >	DependenceMap

Private Member Functions
void	computeDependence ()

void	createPostDominanceTree (BlockVector &nodes, PostOrder &postOrder)

void	detectControlDependencies (BlockVector &nodes, std::vector< Node * > &cdNodes, PostOrder &postOrder, DependenceMap &dependencies)

void	eliminateMultipleOutputs ()

bool	findSubset (DependentOn , DependentOn , Node *)

int	nearestCommonDom (std::vector< int > &iDom, int node1, int node2) const

int	detectStrongComponents (CDGOrderMap &components, DescriptorMap &roots)

void	computeRegionInfo (const CDGOrderMap &orderMap)

void	computeEECInfo (const CDGOrderMap &orderMap)

CompareResult	compareSiblings (Node a, Node b) const

void	regionHelper (Node *, Node::NodesInfo &)

void	computeRelations (const CDGOrderMap &orderMap)

void	processRegion (Node *region)

ControlDependenceEdge &	createControlDependenceEdge (Node &bTail, Node &bHead, Edge::CDGEdgeType edgeValue=Edge::CDEP_EDGE_NORMAL)

Private Attributes
TTAProgram::Program *	program_

TTAProgram::Address	startAddress_

int	alignment_

ControlFlowGraph *	cGraph_

std::vector< int >	iDomTree_

std::vector< std::set< Node * > >	strongComponents_

bool	analyzed_
	Indicates that CDG already has data required for serialization.

Node *	entryNode_
	Stores reference to entryNode of the graph.

bool	componentsDetected_

Additional Inherited Members
Protected Types inherited from BoostGraph< ControlDependenceNode, ControlDependenceEdge >
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.

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

typedef GraphTraits::out_edge_iterator	OutEdgeIter
	Output edge iterator type.

typedef GraphTraits::in_edge_iterator	InEdgeIter
	Input edge iterator type.

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

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

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

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

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< ControlDependenceNode, ControlDependenceEdge >
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< ControlDependenceNode, ControlDependenceEdge > *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 ControlDependenceNode tailNode, const ControlDependenceNode 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 (ControlDependenceNode &dest)

void	calculatePathLengths () const

void	calculatePathLengthsFast () const

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

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

void	calculatePathLengthsOnConnect (const ControlDependenceNode &nTail, const ControlDependenceNode &nHead, ControlDependenceEdge &e)

void	sinkDistDecreased (const ControlDependenceNode &n) const

void	sourceDistDecreased (const ControlDependenceNode &n) const

virtual int	edgeWeight (ControlDependenceEdge &e, const ControlDependenceNode &n) const

void	clearDescriptorCache (EdgeSet edges)

void	constructSubGraph (BoostGraph &subGraph, NodeSet &nodes)

Protected Member Functions inherited from GraphBase< GraphNode, GraphEdge >
virtual bool	hasNode (const Node &) const =0

Protected Attributes inherited from BoostGraph< ControlDependenceNode, ControlDependenceEdge >
std::unordered_map< const ControlDependenceNode *, int >	sourceDistances_

std::unordered_map< const ControlDependenceNode *, int >	sinkDistances_

std::unordered_map< const ControlDependenceNode *, int >	loopingSourceDistances_

std::unordered_map< const ControlDependenceNode *, int >	loopingSinkDistances_

int	height_

Graph	graph_
	The internal graph structure.

EdgeDescMap	edgeDescriptors_

NodeDescMap	nodeDescriptors_

BoostGraph< ControlDependenceNode, ControlDependenceEdge > *	parentGraph_

std::vector< BoostGraph< ControlDependenceNode, ControlDependenceEdge > * >	childGraphs_

TCEString	name_

int	sgCounter_

std::set< Edge * >	ownedEdges_

bool	allowLoopEdges_

PathCache *	pathCache_

Detailed Description

Graph-based program representation.

Definition at line 65 of file ControlDependenceGraph.hh.

Member Typedef Documentation

◆ BlockVector

typedef std::vector<BasicBlockNode*> ControlDependenceGraph::BlockVector

private

Definition at line 102 of file ControlDependenceGraph.hh.

◆ CDGOrder

typedef boost::associative_property_map<CDGOrderMap> ControlDependenceGraph::CDGOrder

private

Definition at line 92 of file ControlDependenceGraph.hh.

◆ CDGOrderMap

typedef std::map<NodeDescriptor, int> ControlDependenceGraph::CDGOrderMap

private

Stores data to compute post order relation on CDG and strong components.

Definition at line 91 of file ControlDependenceGraph.hh.

◆ Color

typedef boost::associative_property_map<ColorMap> ControlDependenceGraph::Color

private

Definition at line 98 of file ControlDependenceGraph.hh.

◆ ColorMap

typedef std::map<NodeDescriptor, boost::default_color_type > ControlDependenceGraph::ColorMap

private

Storage for color property used by dfs.

Definition at line 97 of file ControlDependenceGraph.hh.

◆ DependenceMap

typedef std::map<Node*, DependentOn*, Node::Comparator> ControlDependenceGraph::DependenceMap

private

Definition at line 104 of file ControlDependenceGraph.hh.

◆ DependentOn

typedef std::vector<SourceType> ControlDependenceGraph::DependentOn

private

Definition at line 101 of file ControlDependenceGraph.hh.

◆ DescriptorMap

typedef std::map<NodeDescriptor, NodeDescriptor> ControlDependenceGraph::DescriptorMap

private

Storage for relations between nodes.

Definition at line 94 of file ControlDependenceGraph.hh.

◆ Descriptors

typedef boost::associative_property_map<DescriptorMap> ControlDependenceGraph::Descriptors

private

Definition at line 95 of file ControlDependenceGraph.hh.

◆ PostOrder

typedef boost::associative_property_map<PostOrderMap> ControlDependenceGraph::PostOrder

private

Definition at line 89 of file ControlDependenceGraph.hh.

◆ PostOrderMap

typedef std::map<ControlFlowGraph::NodeDescriptor, int> ControlDependenceGraph::PostOrderMap

private

Stores data to compute post order relation on CFG.

Definition at line 88 of file ControlDependenceGraph.hh.

◆ SourceType

typedef std::pair<Node*, Edge::CDGEdgeType> ControlDependenceGraph::SourceType

private

Definition at line 100 of file ControlDependenceGraph.hh.

Member Enumeration Documentation

◆ CompareResult

enum ControlDependenceGraph::CompareResult

Enumerator
A_BEFORE_B
B_BEFORE_A
ANY_ORDER
UNORDERABLE
ERROR

Definition at line 69 of file ControlDependenceGraph.hh.

                       {
        A_BEFORE_B, // Subgraph A must be scheduled before subgraph B
        B_BEFORE_A, // vice versa
        ANY_ORDER,  // Any order is acceptable
        UNORDERABLE, // Can not be ordered, needs additional predicate
        ERROR      // Try again with reordered nodes TODO: remove this!
    };

Constructor & Destructor Documentation

◆ ControlDependenceGraph()

ControlDependenceGraph::ControlDependenceGraph ( const ControlFlowGraph & cGraph )

Reads ControlFlowGraph of procedure and creates ControlDependenceGraph

Parameters

cGraph Control Flow Graph

Definition at line 96 of file ControlDependenceGraph.cc.

                                     :
    BoostGraph<Node, Edge>(cGraph.name()) ,
    startAddress_(TTAProgram::NullAddress::instance()),
    analyzed_(false), entryNode_(NULL), componentsDetected_(false) {
 
    program_ = cGraph.program();
    alignment_ = cGraph.alignment();
    cGraph_ = &const_cast<ControlFlowGraph&>(cGraph);
    computeDependence();
}

References ControlFlowGraph::alignment(), alignment_, cGraph_, computeDependence(), ControlFlowGraph::program(), and program_.

Here is the call graph for this function:

◆ ~ControlDependenceGraph()

ControlDependenceGraph::~ControlDependenceGraph ( )

virtual

Definition at line 79 of file ControlDependenceGraph.cc.

                                                {
    // removeNode() also removes edges and deletes them
    while (nodeCount() > 0) {
        ControlDependenceNode* n = &node(0);
        removeNode(*n);
        delete n;
    }
    for (unsigned int i = 0; i < strongComponents_.size(); i++) {
        strongComponents_[i].clear();
    }
    strongComponents_.clear();
}

References BoostGraph< ControlDependenceNode, ControlDependenceEdge >::node(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::nodeCount(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::removeNode(), and strongComponents_.

Here is the call graph for this function:

Member Function Documentation

◆ alignment()

int ControlDependenceGraph::alignment ( ) const

Returns an alignment of procedure in original POM

Returns: Alignment take from original POM

Definition at line 672 of file ControlDependenceGraph.cc.

                                        {
    return alignment_;
}

References alignment_.

◆ analyzeCDG()

void ControlDependenceGraph::analyzeCDG ( )

Performs serialization of ControlDependenceGraph, turning it into Control Flow Graph.

Returns: ControlFlowGraph representation of CDG

Exceptions

InvalidData in case serialization of graph is not possible

Find all strong components (loops) in a graph, loop entry nodes will have number identifying for which loop component they are entries and the strongComponents_ will contains all nodes that are part of each component

map to store post order information for all the nodes of a graph From now on, post order info in lastMap will not change

map to store color information during dfs

boost::on_finish_vertex will give us post order numbering

Sort nodes in post order, starting from entry node

Computes "region" information, for each node X, set of nodes that are executed when X is executed (for node Z, on all paths from X to entry, if node Z is region all children of Z will be in "region" of X

Computes "eec" information, for each node X, set of nodes that are executed when any node in subgraph of X is executed, computed using region information

Definition at line 744 of file ControlDependenceGraph.cc.

                                   {
    // CDG was previously analyzed
    if (analyzed()) {
        return;
    }
    if (Application::verboseLevel() > DEBUG_LEVEL) {
        Application::logStream() << (boost::format(
            "\tStarting CDG serialization for %s with %d nodes and %d edges.\n")
            % name() % nodeCount() % edgeCount()).str();
    }
 
    CDGOrderMap componentMap;
    DescriptorMap rootMap;
    auto timer = std::chrono::steady_clock::now();
    /// Find all strong components (loops) in a graph, loop entry nodes
    /// will have number identifying for which loop component they are entries
    /// and the strongComponents_ will contains all nodes that are part
    /// of each component
    int componentCount = detectStrongComponents(componentMap, rootMap);
    long elapsed = std::chrono::duration_cast<std::chrono::seconds>(
                       std::chrono::steady_clock::now() - timer)
                       .count();
    if (Application::verboseLevel() > DEBUG_LEVEL) {
        Application::logStream() << (boost::format(
        "\t\tStrong components: %d components, %d minutes and %d seconds.\n")
            % componentCount % (elapsed/60) % (elapsed%60)).str();
    }
 
    /// map to store post order information for all the nodes of a graph
    /// From now on, post order info in lastMap will not change
    CDGOrderMap lastMap;
    CDGOrder lastOrder(lastMap);
    /// map to store color information during dfs
    ColorMap colorMap;
    Color colorsDFS(colorMap);
    int fStamp(-1);
    /// boost::on_finish_vertex will give us post order numbering
    boost::time_stamper<CDGOrder, int, boost::on_finish_vertex>
        lastOrderStamper(lastOrder, fStamp);
    timer = std::chrono::steady_clock::now();  // restart
    /// Sort nodes in post order, starting from entry node
    boost::depth_first_visit(
        graph_, descriptor(entryNode()),
        boost::make_dfs_visitor(lastOrderStamper), colorsDFS);
    elapsed = std::chrono::duration_cast<std::chrono::seconds>(
                  std::chrono::steady_clock::now() - timer)
                  .count();
    if (Application::verboseLevel() > DEBUG_LEVEL) {
        Application::logStream() << (boost::format(
            "\t\tPost order: %d minutes and %d seconds.\n")
            % (elapsed/60) % (elapsed%60)).str();
    }
 
    timer = std::chrono::steady_clock::now();  // restart
    /// Computes "region" information, for each node X, set of nodes that are
    /// executed when X is executed (for node Z, on all paths from X to entry,
    /// if node Z is region all children of Z will be in "region" of X
    computeRegionInfo(lastMap);
    elapsed = std::chrono::duration_cast<std::chrono::seconds>(
                  std::chrono::steady_clock::now() - timer)
                  .count();
    if (Application::verboseLevel() > DEBUG_LEVEL) {
        Application::logStream() << (boost::format(
            "\t\tRegion: %d minutes and %d seconds.\n")
            % (elapsed/60) % (elapsed%60)).str();
    }
 
    timer = std::chrono::steady_clock::now();  // restart
    /// Computes "eec" information, for each node X, set of nodes that are
    /// executed when any node in subgraph of X is executed, computed using
    /// region information
    computeEECInfo(lastMap);
    elapsed = std::chrono::duration_cast<std::chrono::seconds>(
                  std::chrono::steady_clock::now() - timer)
                  .count();
    if (Application::verboseLevel() > DEBUG_LEVEL) {
        Application::logStream() << (boost::format(
            "\t\tEEC: %d minutes and %d seconds.\n")
            % (elapsed/60) % (elapsed%60)).str();
    }
    analyzed_ = true;
    timer = std::chrono::steady_clock::now();  // restart
#if 0
    // This is really not needed, just for comparing with PDG edge generation
    // if necessary
    computeRelations(lastMap);
    elapsed = std::chrono::duration_cast<std::chrono::seconds>(
                  std::chrono::steady_clock::now() - timer)
                  .count();
    if (Application::verboseLevel() > DEBUG_LEVEL) {
        Application::logStream() << (boost::format(
            "\t\tRelations: %d minutes and %d seconds.\n")
            % (elapsed/60) % (elapsed%60)).str();
    }
#endif
}

References analyzed(), analyzed_, componentCount(), computeEECInfo(), computeRegionInfo(), computeRelations(), DEBUG_LEVEL, BoostGraph< ControlDependenceNode, ControlDependenceEdge >::descriptor(), detectStrongComponents(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::edgeCount(), entryNode(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::graph_, Application::logStream(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::name(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::nodeCount(), and Application::verboseLevel().

Referenced by ControlDependenceGraphPass::handleControlDependenceGraph().

Here is the call graph for this function:

◆ analyzed()

bool ControlDependenceGraph::analyzed ( ) const

inline

Definition at line 84 of file ControlDependenceGraph.hh.

84{ return analyzed_; }

References analyzed_.

Referenced by analyzeCDG(), ProgramDependenceGraph::ProgramDependenceGraph(), and ProgramDependenceGraph::serializePDG().

◆ compareSiblings()

ControlDependenceGraph::CompareResult ControlDependenceGraph::compareSiblings	(	Node *	a,
		Node *	b
	)		const

private

Defined relation between two sibling nodes based on their type and eec info

FIXME: Unique region node rule is broken when creating loop entry nodes (removing loop back edge) and creating new region for incoming edges into loop entry - there can be another region which already has same set of dependences and loop entry was supposed to be child of that, but was not. Problem with detection of subsets of dependencies when creating region nodes!

Definition at line 1223 of file ControlDependenceGraph.cc.

                                                              {
    bool AinA = false;
    bool BinB = false;
    bool BinA = false;
    bool AinB = false;
    // both a and b are simple basic blocks, order is given by data dependencies
    // no need to test eec info
    if (a->isBBNode() && b->isBBNode()
        && !a->isPredicateNode() && !b->isPredicateNode()) {
        return ANY_ORDER;
    }
 
    if (AssocTools::containsKey(a->eec(), a)) {
        AinA = true;
    }
    if (AssocTools::containsKey(b->eec(), b)) {
        BinB = true;
    }
    if (AssocTools::containsKey(a->eec(), b)) {
        BinA = true;
    }
    if (AssocTools::containsKey(b->eec(), a)) {
        AinB = true;
    }
    if ((a->isLoopEntryNode() || a->isPredicateNode())
        && (b->isBBNode() && !b->isPredicateNode())
        && AinA == true) {
        if (a->isLastNode()) {
            return B_BEFORE_A;
        }
        return ANY_ORDER;
    }
    if ((a->isLoopEntryNode() || a->isPredicateNode())
        && (b->isLoopEntryNode() || b->isPredicateNode())
        && AinA == true && BinB == true) {
        if (a->isLastNode()) {
            return B_BEFORE_A;
        }
        if (b->isLastNode()) {
            return A_BEFORE_B;
        }
        return ANY_ORDER;
    }
    if ((a->isLoopEntryNode() || a->isPredicateNode())
        && (b->isBBNode() && !b->isPredicateNode())
        && AinA == false) {
        return B_BEFORE_A;
    }
    if ((a->isLoopEntryNode() || a->isPredicateNode())
        && (b->isLoopEntryNode() || b->isPredicateNode())
        && AinA == false && BinB == true) {
        return B_BEFORE_A;
    }
    if ((a->isLoopEntryNode() || a->isPredicateNode())
        && (b->isLoopEntryNode() || b->isPredicateNode())
        && AinA == false && BinB == false) {
        return UNORDERABLE;
    }
    if ((a->isRegionNode() && AinB == true)
        && (b->isBBNode() || b->isLoopEntryNode() || b->isPredicateNode())) {
        return B_BEFORE_A;
    }
    if ((a->isRegionNode() && AinB == false)
        && (b->isLoopEntryNode() || b->isPredicateNode())
        && AinB == false) {
        return UNORDERABLE;
    }
    if ((a->isRegionNode() && AinB == false)
        && (b->isRegionNode() && BinA == true)) {
        return B_BEFORE_A;
    }
    if ((a->isRegionNode() && AinB == false)
        && (b->isRegionNode() && BinA == false)) {
        return UNORDERABLE;
    }
    if ((a->isLoopCloseNode() && AinB == true)
        && (b->isBBNode() || b->isPredicateNode() || b->isLoopEntryNode()
            || b->isRegionNode())) {
        return B_BEFORE_A;
    }
    if ((a->isLoopCloseNode() && AinB == false)
        && (b->isPredicateNode() || b->isLoopEntryNode()
            || b->isRegionNode())) {
        return UNORDERABLE;
    }
    /// FIXME:
    /// Unique region node rule is broken when creating loop
    /// entry nodes (removing loop back edge) and creating new region for
    /// incoming edges into loop entry - there can be another region
    /// which already has same set of dependences and loop entry was
    /// supposed to be child of that, but was not. Problem with detection
    /// of subsets of dependencies when creating region nodes!
    if ((a->isRegionNode() && AinB == true)
        && (b->isRegionNode() && BinA == true)) {
        if (a->isLastNode()) {
            return B_BEFORE_A;
        }
        if (b->isLastNode()) {
            return A_BEFORE_B;
        }
        return ANY_ORDER;
    }
    return ERROR;
}

References A_BEFORE_B, ANY_ORDER, B_BEFORE_A, AssocTools::containsKey(), ControlDependenceNode::eec(), ERROR, ControlDependenceNode::isBBNode(), ControlDependenceNode::isLastNode(), ControlDependenceNode::isLoopCloseNode(), ControlDependenceNode::isLoopEntryNode(), ControlDependenceNode::isPredicateNode(), ControlDependenceNode::isRegionNode(), and UNORDERABLE.

Referenced by processRegion().

Here is the call graph for this function:

◆ componentCount()

int ControlDependenceGraph::componentCount ( ) const

inline

Definition at line 85 of file ControlDependenceGraph.hh.

85{ return strongComponents_.size(); }

References strongComponents_.

Referenced by analyzeCDG(), ProgramDependenceGraph::copyRegionEECComponent(), and detectStrongComponents().

◆ computeDependence()

void ControlDependenceGraph::computeDependence ( )

private

Compute control flow post-dominance information (in the form of an immediate post-dominator tree). Compute the control dependencies of the control flow graph using the pre-computed tree of immediate post-dominators.

The base algorithm implemented is described in K.D. Cooper, T.J. Harvey, K. Kennedy: "A Simple, Fast Dominance Algorithm" and Ferrante, Ottenstein, Warren: "The Program Dependence Graphs and Its Use in Optimisation"

Exceptions

Throws InvalidData exception in case CFG can not be analyzed

Removes artificial Exit node, it is not dependent on anything Move edges from Entry's child region to Entry and delete region

Definition at line 121 of file ControlDependenceGraph.cc.

                                          {
 
    BlockVector nodes;
    PostOrderMap poMap;
    PostOrder postOrder(poMap);
 
    createPostDominanceTree(nodes, postOrder);
    // For each edge we have  to record what is predicate it is controlled
    // by...
    DependenceMap dependencies;
    std::vector<Node*> cdNodes;
    detectControlDependencies(nodes, cdNodes, postOrder, dependencies);
 
    // edge added while creating CD dependencies, not part of CFG by
    // itself so it should be removed now that we have dominance tree
    cGraph_->removeEntryExitEdge();
    // set of control dependencies for given region node
    DependenceMap regionNodes;
 
    // Creates region node for each set of control dependencies
    // and adds the record to regionNodes
    for (unsigned int i = 0; i < iDomTree_.size();  i++) {
        Node* cNode = cdNodes[i];
        if (cNode->isEntryNode() || cNode->isExitNode()) {
            // Exit postdominate every node including Entry so
            // they do not have any dependencies
            continue;
        }
        DependenceMap::iterator rItr;
        rItr = regionNodes.begin();
        bool found = false;
        // Find if previously created region node have subset of dependencies
        // of currently tested node. If so, replace subset with dependence
        // on previously created region node
        // TODO: The tested set of created nodes should be sorted from
        // largest to smallest
        while (rItr != regionNodes.end()) {
            if (!MapTools::containsKey(dependencies, cNode)) {
                TCEString msg = (boost::format(
                    "Node %s of procedure %s is missing dependencies. "
                    "Most likely CFG with unreachable BB. Can not create CDG!")
                    % cNode->toString() % name()).str();
                throw InvalidData(__FILE__, __LINE__, __func__, msg);
            }
            if (findSubset(
                dependencies[cNode], (*rItr).second, (*rItr).first)){
                found = true;
            }
            rItr ++;
        }
        if (found == true && dependencies[cNode]->size() == 1) {
            // only one dependence and is identical
            // with already existing one, just create edge to existing region
            createControlDependenceEdge(
                *dependencies[cNode]->at(0).first, *cNode);
            continue;
        }
        if (dependencies[cNode]->size() > 0) {
            // Create new region node and add edge from it to tested node
            // record set of dependences for future reuse
            Node* newNode = new Node(Node::CDEP_NODE_REGION);
            addNode(*newNode);
            DependentOn* dOn = new DependentOn(*(dependencies[cNode]));
            regionNodes.insert(
                std::pair<Node*, DependentOn*>(newNode, dOn));
            createControlDependenceEdge(*newNode, *cNode);
        }
    }
 
    // create dependent edges INTO region nodes
    DependenceMap::iterator regionItr;
    regionItr = regionNodes.begin();
    while (regionItr != regionNodes.end()) {
        // For each region node, add edge from all nodes it is depending on
        // into the region node
        for (unsigned int i = 0; i < (*regionItr).second->size(); i++) {
            createControlDependenceEdge(
                *(*regionItr).second->at(i).first, *(*regionItr).first,
                (*regionItr).second->at(i).second);
        }
        regionItr++;
    }
 
    eliminateMultipleOutputs();
    /// Removes artificial Exit node, it is not dependent on anything
    /// Move edges from Entry's child region to Entry and delete region
    for (int i = 0; i < nodeCount(); i++) {
        Node& testNode = node(i);
        if (testNode.isExitNode()) {
            if (outDegree(testNode) == 0 && inDegree(testNode) == 0) {
                removeNode(testNode);
                delete &testNode;
                continue;
            }
        }
 
        if (testNode.isEntryNode()) {
            if (outDegree(testNode) != 1) {
                TCEString msg = (boost::format(
                    "Entry node of procedure %s has more then one child node."
                    "Invalid graph!") % name()).str();
                throw ModuleRunTimeError(__FILE__, __LINE__, __func__, msg);
            }
            Edge& edge = outEdge(testNode, 0);
            Node& entryChild = headNode(edge);
            moveOutEdges(entryChild, testNode);
            removeNode(entryChild);
            delete &entryChild;
        }
    }
    MapTools::deleteAllValues(regionNodes);
    MapTools::deleteAllKeys(regionNodes);
    MapTools::deleteAllValues(dependencies);
    MapTools::deleteAllKeys(dependencies);
    cdNodes.clear();
    nodes.clear();
}

Referenced by ControlDependenceGraph().

Here is the call graph for this function:

◆ computeEECInfo()

void ControlDependenceGraph::computeEECInfo ( const CDGOrderMap & orderMap )

private

Compute the "eec" information for each node of graph. Eec is used to determine order in which sibling subgraphs needs to be scheduled in resulting cfg.

"eec" of node X is set of nodes that will be executed in case any of the nodes in subgraph of X will be executed.

Parameters

orderMap post order map of CDG graph, nodes augmented with "region" information, "eec" information will be added.

eec already exists, skip

Found close node, eec(node) == intersection of all close nodes of same loop region(node) (close node is as leaf node)

Found leaf node, eec(node) == region(node)

if node is predicate we also store pseudo information for part of basic block which does not compute predicate itself, it is just set of statements - leafs

Not a leaf node, eec(x) = intersection(eec(children(x)) \ children(x)

Definition at line 1108 of file ControlDependenceGraph.cc.

                                                                  {
    int mapSize = orderMap.size();
    for (int i = 0; i < mapSize; i++) {
        NodeDescriptor des =
            MapTools::keyForValue<NodeDescriptor>(
            orderMap, i);
        Node* node = graph_[des];
         /// eec already exists, skip
         if (node->eec().size() > 0) {
            continue;
         }
        /// Found close node, eec(node) == intersection of all close
        /// nodes of same loop region(node) (close node is as leaf node)
        if (node->isLoopCloseNode() && node->eec().size() == 0) {
           std::vector<Node*> closeNodes;
           std::set<Node*> component = strongComponents_[node->component()];
          // collect all loop close nodes of same loop
           for (std::set<Node*>::iterator si = component.begin();
               si != component.end(); si++) {
               if ((*si)->isLoopCloseNode()) {
                   closeNodes.push_back(*si);
               } else if ((*si)->isRegionNode()
                    || (*si)->isPredicateNode()) {
                    (*si)->setLastNode();
                }
           }
           Node::NodesInfo finalInfo;
           Node::NodesInfo storeResult;
           finalInfo.insert(node->region().begin(),node->region().end());
           for (unsigned int i = 0; i < closeNodes.size(); i++) {
                SetTools::intersection(
                finalInfo, closeNodes[i]->region(), storeResult);
                finalInfo.swap(storeResult);
                storeResult.clear();
            }
            // add intersection of all region infos to each close node in loop
            for (unsigned j = 0; j < closeNodes.size(); j++) {
                Node* result = closeNodes[j];
                if(result->eec().size() != 0) {
                    TCEString msg = (boost::format(
                        "Close node %s in %s already has eec!\n")
                        % result->toString() % node->toString()).str();
                    throw ModuleRunTimeError(__FILE__, __LINE__, __func__, msg);
                }
                for (Node::NodesInfo::iterator k = finalInfo.begin();
                    k != finalInfo.end(); k++) {
                    result->addToEEC(**k);
                }
            }
            continue;
         }
        if (outDegree(*node) == 0) {
            /// Found leaf node, eec(node) == region(node)
            Node::NodesInfo regionX = node->region();
            for (Node::NodesInfo::iterator t = regionX.begin();
                t != regionX.end(); t++) {
                node->addToEEC( **t);
            }
            continue;
        } else {
            if (node->isPredicateNode()) {
            /// if node is predicate we also store pseudo information for
            /// part of basic block which does not compute predicate
            /// itself, it is just set of statements - leafs
                Node::NodesInfo regionX = node->region();
                for (Node::NodesInfo::iterator t = regionX.begin();
                    t != regionX.end(); t++) {
                    node->addToPseudoPredicateEEC( **t);
                }
            }
 
            /// Not a leaf node,
            /// eec(x) = intersection(eec(children(x)) \ children(x)
            NodeSet succ = successors(*node);
            Node::NodesInfo childNodes;
            // copy successors from NodeSet to NodesInfo otherwise
            // comparator function object in NodeSet makes chaos with
            // set_difference
            for (NodeSet::iterator su = succ.begin();
               su != succ.end(); su++) {
               childNodes.insert(*su);
            }
            Node::NodesInfo finalEEC;
 
            // Fill in candidate set with data from first successor
            finalEEC.insert(
               (*(childNodes.begin()))->eec().begin(),
               (*(childNodes.begin()))->eec().end());
            // compute intersection of successors eec
            for(Node::NodesInfo::iterator j = childNodes.begin();
               j != childNodes.end(); j++ ) {
               Node::NodesInfo storeResult;
               SetTools::intersection(finalEEC, (*j)->eec(), storeResult);
               finalEEC.swap(storeResult);
               storeResult.clear();
            }
            std::vector<Node*> result(finalEEC.size(), NULL);
            // compute set difference, returns iterator pointing to .end()
            // of the result
            std::vector<Node*>::iterator resultEnd =
               std::set_difference(finalEEC.begin(), finalEEC.end(),
                  childNodes.begin(), childNodes.end(), result.begin());
            // push resulting eec into the node eec info
            for (std::vector<Node*>::iterator t = result.begin();
                t != resultEnd; t++) {
                node->addToEEC(**t);
            }
        }
    }
}

References __func__, ControlDependenceNode::addToEEC(), ControlDependenceNode::eec(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::graph_, SetTools::intersection(), MapTools::keyForValue(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::node(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::outDegree(), strongComponents_, BoostGraph< ControlDependenceNode, ControlDependenceEdge >::successors(), ControlDependenceNode::toString(), and GraphNode::toString().

Referenced by analyzeCDG().

Here is the call graph for this function:

◆ computeRegionInfo()

void ControlDependenceGraph::computeRegionInfo ( const CDGOrderMap & orderMap )

private

Compute the "region" information for each node of graph. Region is used to compute "eec" to determine order in which sibling subgraphs will be in resulting cfg.

"Region" of node X is set of nodes that will be executed in case is X executed.

Parameters

orderMap post order map of CDG graph, nodes will be augmented with "region" information.

Compute "region" information using reverse post-order processing

For non loop entry nodes, simply compute region info and store it in the node

for loop entry node, find all other entry nodes of the same loop (component) final region info will be intersection of region infos from all the entry nodes in the same loop it will be same for all the nodes too (they are reachable)

Test for loop entries of same component Loop entry of one component can be regular region node of other "larger" loop

Definition at line 1040 of file ControlDependenceGraph.cc.

                                                                    {
 
   int mapSize = orderMap.size();
   if (mapSize == 0) {
      throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
         "No nodes in CDG graph for " + name() + "!");
   }
   /// Compute "region" information using reverse post-order processing
    for (int i = mapSize -1 ; i >= 0 ; i--) {
        NodeDescriptor des =
            MapTools::keyForValue<NodeDescriptor>(orderMap,i);
        Node* node = graph_[des];
        if (!node->isLoopEntryNode()) {
            /// For non loop entry nodes, simply compute region info
            /// and store it in the node
            Node::NodesInfo finalNodesInfo;
            regionHelper(node, finalNodesInfo);
 
            for (Node::NodesInfo::iterator k = finalNodesInfo.begin();
                k != finalNodesInfo.end(); k++) {
                node->addToRegion(**k);
            }
        } else if (node->region().size() == 0) {
            /// for loop entry node, find all other entry nodes
            /// of the same loop (component)
            /// final region info will be intersection of region infos from
            /// all the entry nodes in the same loop
            /// it will be same for all the nodes too (they are reachable)
            std::vector<Node*> entries;
            std::set<Node*> component = strongComponents_[node->component()];
            for (std::set<Node*>::iterator si = component.begin();
                si != component.end(); si++) {
                /// Test for loop entries of same component
                /// Loop entry of one component can be regular region node of
                /// other "larger" loop
                if ((*si)->isLoopEntryNode(node->component())) {
                    entries.push_back(*si);
                }
            }
            Node::NodesInfo finalNodesInfo;
            for (unsigned int i = 0; i < entries.size(); i++) {
                Node* entryNode = entries[i];
                regionHelper(entryNode, finalNodesInfo);
            }
            for (unsigned j = 0; j < entries.size(); j++) {
                Node* result = entries[j];
                for (Node::NodesInfo::iterator k = finalNodesInfo.begin();
                    k != finalNodesInfo.end(); k++) {
                    result->addToRegion(**k);
                }
            }
        }
    }
}

References __func__, ControlDependenceNode::addToRegion(), entryNode(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::graph_, MapTools::keyForValue(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::name(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::node(), regionHelper(), and strongComponents_.

Referenced by analyzeCDG().

Here is the call graph for this function:

◆ computeRelations()

void ControlDependenceGraph::computeRelations ( const CDGOrderMap & orderMap )

private

Computes relation between every pair of nodes in a graph that has common parent.

Parameters

orderMap Post order map of a graph

Process nodes in post order, guarantees child nodes will be processed before their parent

MoveNodes are skipped here, they are always child of region

Definition at line 1411 of file ControlDependenceGraph.cc.

                                                                    {
    /// Process nodes in post order, guarantees child nodes will be processed
    /// before their parent
    int mapSize = orderMap.size();
    for (int i = 0; i < mapSize; i++) {
        NodeDescriptor des =
            MapTools::keyForValue<NodeDescriptor>(orderMap, i);
        Node* node = graph_[des];
        /// MoveNodes are skipped here, they are always child of region
        if (node->isRegionNode()
            || node->isLoopEntryNode()
            || node->isPredicateNode()) {
            processRegion(node);
            continue;
        }
    }
}

References BoostGraph< ControlDependenceNode, ControlDependenceEdge >::graph_, MapTools::keyForValue(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::node(), and processRegion().

Referenced by analyzeCDG().

Here is the call graph for this function:

◆ createControlDependenceEdge()

ControlDependenceEdge & ControlDependenceGraph::createControlDependenceEdge	(	Node &	bTail,
		Node &	bHead,
		Edge::CDGEdgeType	edgeValue = `Edge::CDEP_EDGE_NORMAL`
	)

private

Create a control dependence edge between two basic blocks.

Creates new Control Dependence edge between two basic blocks passed as parameters

Parameters

bTail	The tail basic block.
bHead	The head basic block.

Returns: The created control dependence edge.

Definition at line 331 of file ControlDependenceGraph.cc.

                               {
 
    Edge* theEdge = 0;
    try {
        // By construction, there should not! be duplication of CD edges!!!
        if (hasEdge(bTail, bHead)) {
            theEdge = graph_[connectingEdge(bTail, bHead)];
        } else {
            theEdge = new Edge(edgeValue);
            connectNodes(bTail, bHead, *theEdge);
        }
    } catch (const ObjectAlreadyExists& e) {
        throw ObjectAlreadyExists(
            __FILE__, __LINE__, __func__, e.errorMessageStack());
    }
    return *theEdge;
}

References __func__, BoostGraph< ControlDependenceNode, ControlDependenceEdge >::connectingEdge(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::connectNodes(), Exception::errorMessageStack(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::graph_, and BoostGraph< ControlDependenceNode, ControlDependenceEdge >::hasEdge().

Referenced by computeDependence(), detectStrongComponents(), and eliminateMultipleOutputs().

Here is the call graph for this function:

◆ createPostDominanceTree()

void ControlDependenceGraph::createPostDominanceTree	(	BlockVector &	nodes,
		PostOrder &	postOrder
	)

private

Internal helper. Creates a tree of immediate post dominators for constructing a control dependencies

Parameters

nodes	Will be filled with pointers to BasicBlocks indexed by post order number
postOrder	Will be filled by post order numbers

Definition at line 361 of file ControlDependenceGraph.cc.

                          {
 
    // Add false edge from entry to exit
    cGraph_->addEntryExitEdge();
    ControlFlowGraph::ReversedGraph* revGraph_ = NULL;
    revGraph_ = &cGraph_->reversedGraph();
 
    bool modified = false;
    int counter = 0;  // NOLINT Disable claim this is unused
    std::vector<ControlFlowEdge*> addedEdges;
    BasicBlockNode& cfgExitNode = cGraph_->exitNode();
    do {
        ColorMap cMap;
        Color colors(cMap);
        modified = false;
        int tStamp(-1);
        boost::time_stamper<PostOrder, int, boost::on_finish_vertex>
                pOrderStamper(postOrder, tStamp);
        // the order of nodes within the reversed graph remains unchanged,
        // have to look for the sink node (of the original graph) when we
        // want to get the start node of the reverse graph.
        boost::depth_first_visit(
            *revGraph_, cGraph_->descriptor(cfgExitNode),
            boost::make_dfs_visitor(pOrderStamper), colors);
        // there can be just one node with post order number 0
        // if there are several, then some of them are not post
        // dominated by Exit - endless loop without break or return
        // we add and edge from one of those nodes to exit and redo
        // the dfs visit.
        std::vector<BasicBlockNode*> postZero;
        for (int i = cGraph_->nodeCount() - 1; i >=0; i--) {
            BasicBlockNode* testedNode = &cGraph_->node(i);
            if (postOrder[cGraph_->descriptor(*testedNode)] == 0) {
                postZero.push_back(testedNode);
            }
        }
        if (postZero.size() > 1) {
            for (unsigned int i = 0; i < postZero.size(); i++) {
                BasicBlockNode* testedNode = postZero[i];
                if (!testedNode->isEntryBB()) {
                    ControlFlowEdge* edge = new
                        ControlFlowEdge(
                            ControlFlowEdge::CFLOW_EDGE_LOOP_BREAK);
                    cGraph_->connectNodes(
                        *testedNode, cGraph_->exitNode(), *edge);
                    addedEdges.push_back(edge);
                    delete revGraph_;
                    revGraph_ = &cGraph_->reversedGraph();
                    modified = true;
                    break;
                }
            }
        }
        postZero.clear();
        counter++;
    } while (modified);
    delete revGraph_;
    revGraph_ = NULL;
 
    // tree of immediate dominators, mapping a node to its immediate
    // dominator; each node is represented by its inverted post-order number
    iDomTree_.resize(cGraph_->nodeCount());
    const int startNodePO = cGraph_->nodeCount() - 1;
    // create inverse map from post-order to node
    // initialise tree of immediate dominators
    nodes.resize(cGraph_->nodeCount());
    for (unsigned int i = 0; i < nodes.size(); i++) {
        nodes[postOrder[cGraph_->descriptor(cGraph_->node(i))]] =
            &(cGraph_->node(i));
        iDomTree_[i] = -1;
    }
 
    iDomTree_[startNodePO] = startNodePO;
    bool changed = true;
    while (changed) {
        changed = false;
        // traverse graph in reverse post-order, skipping start node
        for (int i = cGraph_->nodeCount() - 2; i >= 0; i--) {
            BasicBlockNode& b(*nodes[i]);
            int newDom;
            int predIndex;
            for (predIndex = 0; predIndex < cGraph_->outDegree(b);
                predIndex++) {
                BasicBlockNode& predecessor(cGraph_->headNode(
                    cGraph_->outEdge(b, predIndex)));
                int predPO = postOrder[cGraph_->descriptor(predecessor)];
                // Find first processed predecessor of b
                if (iDomTree_[predPO] != -1) {
                    break;
                }
            }
            // outgoing edges of original graph are in-edges of reverse graph
            BasicBlockNode& predecessor(cGraph_->headNode(
                cGraph_->outEdge(b, predIndex)));
            newDom = postOrder[cGraph_->descriptor(predecessor)];
            // because nodes are searched in inverse post-order, at least
            // one of predecessors of current node must have been processed
            if (newDom == -1) {
                TCEString message =
                    "Missing postOrder number of predecessor!";
                throw ModuleRunTimeError(__FILE__, __LINE__, __func__, message);
            }
 
            for (predIndex = predIndex + 1;
                predIndex < cGraph_->outDegree(b);
                predIndex++) {
                BasicBlockNode& predecessor(cGraph_->headNode(
                    cGraph_->outEdge(b, predIndex)));
                int predPO = postOrder[cGraph_->descriptor(predecessor)];
                if (iDomTree_[predPO] != -1) {
                    newDom = nearestCommonDom(iDomTree_, newDom, predPO);
                }
            }
            if (newDom != iDomTree_[i]) {
                changed = true;
                iDomTree_[i] = newDom;
            }
        }
    }
    for (unsigned int i = 0; i < addedEdges.size(); i++) {
        cGraph_->removeEdge(*addedEdges[i]);
    }
}

Referenced by computeDependence().

Here is the call graph for this function:

◆ detectControlDependencies()

void ControlDependenceGraph::detectControlDependencies	(	BlockVector &	nodes,
		std::vector< Node * > &	cdNodes,
		PostOrder &	postOrder,
		DependenceMap &	dependencies
	)

private

Internal helper. Implemented detection of control dependencies.

Parameters

nodes	Vector of basic block nodes indexed by reverse post order number
cdNodes	Vector of control dependence nodes indexed by reverse post order number
postOrder	Post order numbering of nodes
dependencies	For each node, the list of nodes it is dependent on

Basic block is either 3way jump - forbidden or it is indirect jump with edges to all data-code rellocations. We can not deal with such situation at the moment. Fix cfg to original form and throw exception

node is not predicate

Basic block is either 3way jump - forbidden or it is indirect jump with edges to all data-code rellocations. We can not deal with such situation at the moment. Fix cfg to original form and throw exception

Definition at line 545 of file ControlDependenceGraph.cc.

                                 {
 
    std::map<BasicBlockNode*, Node*> BBCD;
    for (int i = 0; i < cGraph_->nodeCount(); i++) {
        BasicBlockNode* bbNode = &cGraph_->node(i);
        int nodeOutDegree = cGraph_->outDegree(*bbNode);
        if (!MapTools::containsKey(BBCD, bbNode)) {
            Node* cd = NULL;
            Node::NodeType typeOfNode = Node::CDEP_NODE_BB;
            if (nodeOutDegree == 2 && (!bbNode->isEntryBB())) {
                // 2 out edges in CFG means BB ends with conditional jump
                // therefore it is predicate BB
                typeOfNode = Node::CDEP_NODE_PREDICATE;
            } else if(nodeOutDegree > 2){
                /// Basic block is either 3way jump - forbidden
                /// or it is indirect jump with edges to all data-code
                /// rellocations. We can not deal with such situation
                /// at the moment. Fix cfg to original form and throw exception
                cGraph_->removeEntryExitEdge();
                TCEString msg = (boost::format(
                    "Basic block %s has out degree of %d. Most likely "
                    "indirect jump. Can not create CDG for that atm.")
                    % bbNode->toString() % nodeOutDegree).str();
                throw InvalidData(__FILE__, __LINE__, __func__, msg);
            }
            cd = new Node(typeOfNode, bbNode);
            addNode(*cd);
            BBCD.insert(std::pair<BasicBlockNode*,Node*>(
                bbNode, cd));
        }
        if (nodeOutDegree < 2) {
            /// node is not predicate
            continue;
        } else if(nodeOutDegree > 2){
            /// Basic block is either 3way jump - forbidden
            /// or it is indirect jump with edges to all data-code
            /// rellocations. We can not deal with such situation
            /// at the moment. Fix cfg to original form and throw exception
            cGraph_->removeEntryExitEdge();
            TCEString msg = (boost::format(
                "Basic block %s has out degree of %d. Most likely "
                "indirect jump. Can not create CDG for that atm.")
                % bbNode->toString() % nodeOutDegree).str();
            throw InvalidData(__FILE__, __LINE__, __func__, msg);
        }
        for (int j = 0 ; j < nodeOutDegree; j++) {
            Edge::CDGEdgeType edgeType =
                Edge::CDEP_EDGE_NORMAL;
            BasicBlockNode *t = &(cGraph_->headNode(
                cGraph_->outEdge(*bbNode, j)));
 
            int nPO = postOrder[cGraph_->descriptor(*bbNode)];
            int tPO = postOrder[cGraph_->descriptor(*t)];
            int nPoDom = iDomTree_[nPO];
            if (nPoDom == tPO) {
                // t is target of n, so if it post-dominate n
                // it is immediate post dominator!
                continue;
            }
            int runnerPo = tPO;
            if (cGraph_->outEdge(*bbNode, j).isTrueEdge()) {
                edgeType = Edge::CDEP_EDGE_TRUE;
            }
            if (cGraph_->outEdge(*bbNode, j).isFalseEdge()) {
                edgeType = Edge::CDEP_EDGE_FALSE;
            }
            SourceType newSource = SourceType(
                MapTools::valueForKey<Node*>(
                BBCD, bbNode), edgeType);
 
            while (nPoDom != runnerPo) {
                // Walk through postDominator tree
                // Store found CD in multimap
                Node* runnerCD = NULL;
                if (MapTools::containsKey(BBCD, nodes[runnerPo])) {
                    runnerCD = MapTools::valueForKey<Node*>(
                        BBCD, nodes[runnerPo]);
                } else {
                    if (cGraph_->outDegree(*nodes[runnerPo]) == 2 &&
                        !nodes[runnerPo]->isEntryBB()) {
                        // 2 out edges in CFG means BB ends with conditional
                        //jump therefore it is predicate BB
                        runnerCD = new Node(
                            Node::CDEP_NODE_PREDICATE, nodes[runnerPo]);
                    } else {
                        runnerCD = new Node(
                            Node::CDEP_NODE_BB, nodes[runnerPo]);
                    }
                    addNode(*runnerCD);
                    BBCD.insert(
                        std::pair<BasicBlockNode*,Node*>(
                            nodes[runnerPo], runnerCD));
                }
                if (MapTools::containsKey(dependencies, runnerCD)) {
                    DependentOn* dep = MapTools::valueForKey<DependentOn*>(
                        dependencies, runnerCD);
                    dep->push_back(newSource);
                } else {
                    DependentOn* dep = new DependentOn;
                    dep->push_back(newSource);
                    dependencies.insert(
                        std::pair<Node*, DependentOn*>(
                            runnerCD, dep));
                }
                runnerPo = iDomTree_[runnerPo];
            }
        }
 
    }
    for (unsigned int i = 0; i < nodes.size(); i++) {
        Node* cdNode;
        cdNode = MapTools::valueForKey<Node*>(
            BBCD, nodes[i]);
        cdNodes.push_back(cdNode);
    }
    BBCD.clear();
}

References __func__, BoostGraph< ControlDependenceNode, ControlDependenceEdge >::addNode(), ControlDependenceEdge::CDEP_EDGE_FALSE, ControlDependenceEdge::CDEP_EDGE_NORMAL, ControlDependenceEdge::CDEP_EDGE_TRUE, ControlDependenceNode::CDEP_NODE_BB, ControlDependenceNode::CDEP_NODE_PREDICATE, cGraph_, MapTools::containsKey(), BoostGraph< GraphNode, GraphEdge >::descriptor(), BoostGraph< GraphNode, GraphEdge >::headNode(), iDomTree_, BasicBlockNode::isEntryBB(), MapTools::keyForValue(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), BoostGraph< GraphNode, GraphEdge >::outDegree(), BoostGraph< GraphNode, GraphEdge >::outEdge(), ControlFlowGraph::removeEntryExitEdge(), and BasicBlockNode::toString().

Referenced by computeDependence().

Here is the call graph for this function:

◆ detectStrongComponents()

int ControlDependenceGraph::detectStrongComponents	(	CDGOrderMap &	components,
		DescriptorMap &	roots
	)

private

Detects all strong components of a CDG graph (loops). Strong components are maximal sets of nodes that are reachable from each other. Each node is member of some component. If it is not in loop then node is components of it's own. Augments graph with loop entry and close nodes. Works iterativly, first detects maximal component, then proceeds to ones that are "embedded".

Parameters

components	After return contains for each node number of component to which node belongs
roots	After return contains for each node a node that is root of component to which node belongs

Returns: returns number of components in a graph

Will repeat untill all the strong components will be found Including weirdly nested :-)

Node count will change with addition of close nodes

If the number of components is identical to number of nodes there are no loops in graph

Add to strong components only those which are loops Store them as CDNode*, use of descriptors is not possible due to later addition of Nodes which will invalidate descriptors

Detects all loop entry nodes Stores Nodes which are identified as loop entry nodes together with number to which loop they belong

for each entry node, collect edges that points to it from outside the loop, deals only with newly added components

This may change in which component node it

Several nodes points to loop entry node we create dummy region node to collect those edges

Adds close nodes for each loop entry node Node and edge descriptors are invalidated here!

Create one "close" node for each loop entry

Close node is also part of component

Detect edges to loop entry node from inside component and redirect them to close node

Actually redirect edges

Back edge will be added later, after all loops are found

Test if edges were redirected successfully

In case loop entry has multiple incoming edges outside loop, we add new region to group them together

Definition at line 856 of file ControlDependenceGraph.cc.

                          {
 
    if (componentsDetected_) {
        return strongComponents_.size();
    }
 
    std::vector<std::pair<Node*, Node*> >  backEdges;
    int componentCount = 0;
    int currentComponents = 0;
    /// Will repeat untill all the strong components will be found
    /// Including weirdly nested :-)
    do {
        CDGOrder componentOrder(components);
        Descriptors componentRoots(roots);
        currentComponents = 0;
        /// Node count will change with addition of close nodes
        currentComponents =  boost::strong_components(
            graph_, componentOrder, boost::root_map(componentRoots));
 
        // for each component add vector of nodes that belongs to it
        std::vector<std::set<Node*> >  componentVector;
        componentVector.resize(componentCount + currentComponents);
 
        /// If the number of components is identical to number of nodes
        /// there are no loops in graph
        if (currentComponents == nodeCount()) {
            componentCount = strongComponents_.size();
            break;
        }
        /// Add to strong components only those which are loops
        /// Store them as CDNode*, use of descriptors is not possible
        /// due to later addition of Nodes which will invalidate
        /// descriptors
        for (CDGOrderMap::iterator iterA = components.begin();
            iterA != components.end(); iterA ++) {
                Node* cNode = graph_[(*iterA).first];
                componentVector[(*iterA).second].insert(cNode);
        }
 
        for (unsigned int i = componentCount; i < componentVector.size(); i++) {
            if (componentVector[i].size() > 1) {
                std::set<Node*>& vector = componentVector[i];
                std::set<Node*> ref;
                int componentsSize = strongComponents_.size();
                for (std::set<Node*>::iterator iterB = vector.begin();
                    iterB != vector.end();
                    iterB++) {
                    ref.insert(*iterB);
                    // Set component number
                    if ((*iterB)->component() == -1){
                        (*iterB)->setComponent(componentsSize);
                    }
                }
                strongComponents_.push_back(ref);
            }
        }
 
        /// Detects all loop entry nodes
        /// Stores Nodes which are identified as loop entry nodes
        /// together with number to which loop they belong
        std::vector<std::pair<Node*,int> > newEntry;
        /// for each entry node, collect edges that points to it from outside
        /// the loop, deals only with newly added components
        std::map<Node*, std::vector<Node*> >  incomingToEntry;
        for (unsigned int i = componentCount;
            i < strongComponents_.size();
            i++) {
            std::set<Node*>& nodes = strongComponents_[i];
            for (std::set<Node*>::iterator iterD = nodes.begin();
                iterD != nodes.end();
                iterD++) {
                EdgeSet edges = inEdges(**iterD);
                for (EdgeSet::iterator ei = edges.begin();
                    ei != edges.end();
                    ei++) {
                    Node* testedNode = &tailNode(**ei);
                    if (nodes.find(testedNode) == nodes.end()) {
                        if (!(*iterD)->isLoopEntryNode(i)) {
                            /// This may change in which component node it
                            (*iterD)->setLoopEntryNode(i);
                            newEntry.push_back(
                                std::pair<Node*,int>(*iterD,i));
                            incomingToEntry[*iterD].push_back(testedNode);
                        } else {
                        /// Several nodes points to loop entry node
                        /// we create dummy region node to collect those
                        /// edges
                           incomingToEntry[*iterD].push_back(testedNode);
                        }
                    }
                }
            }
        }
 
        /// Adds close nodes for each loop entry node
        /// Node and edge descriptors are invalidated here!
        for (unsigned int j = 0; j < newEntry.size(); j++) {
            Node* loopNode = newEntry[j].first;
            std::set<Node*>& nodes =
                strongComponents_[newEntry[j].second];
            /// Create one "close" node for each loop entry
            Node* close = new Node(Node::CDEP_NODE_LOOPCLOSE);
            close->setComponent(newEntry[j].second);
            addNode(*close);
            /// Close node is also part of component
            strongComponents_[newEntry[j].second].insert(close);
 
            /// Detect edges to loop entry node from inside component and
            /// redirect them to close node
            EdgeSet edges = inEdges(*loopNode);
            std::vector<Edge*> storeEdges;
            for (EdgeSet::iterator ei = edges.begin();
                ei != edges.end();
                ei++) {
                Node* sourceNode = &tailNode(**ei);
                if (nodes.find(sourceNode) != nodes.end()){
                    storeEdges.push_back(*ei);
                }
            }
            /// Actually redirect edges
            for (unsigned int counter = 0;
                counter < storeEdges.size();
                counter++) {
                moveInEdge(*loopNode, *close, *storeEdges[counter]);
            }
            /// Back edge will be added later, after all loops are found
            backEdges.push_back(
                std::pair<Node*, Node*>(close, loopNode));
 
            /// Test if edges were redirected successfully
            if (inDegree(*close) == 0) {
                TCEString msg = (boost::format(
                    "Close node for loop entry node %s was not connected!\n")
                    % loopNode->toString()).str();
                throw ModuleRunTimeError(__FILE__, __LINE__, __func__, msg);
            }
 
            /// In case loop entry has multiple incoming edges
            /// outside loop, we add new region to group them together
            std::vector<Node*> tmp =
               MapTools::valueForKey<std::vector<Node*> >(
                  incomingToEntry, loopNode);
            if (tmp.size() > 1) {
                Node* collect = new Node(Node::CDEP_NODE_REGION);
                addNode(*collect);
                for (unsigned int i = 0; i < tmp.size(); i++) {
                    Node* input = tmp[i];
                    EdgeDescriptor ed = connectingEdge(*input, *loopNode);
                    Edge* e = graph_[ed];
                    moveInEdge(*loopNode, *collect, *e);
                }
                ControlDependenceEdge* edge2 =
                    new ControlDependenceEdge();
                connectNodes(*collect, *loopNode, *edge2);
            }
        }
        newEntry.clear();
        componentCount = strongComponents_.size();
    } while (true);
 
    // Add edges from close nodes to their respective loop entries
   for (unsigned int i = 0; i < backEdges.size(); i++) {
      createControlDependenceEdge(
         *backEdges[i].first, *backEdges[i].second, Edge::CDEP_EDGE_LOOPCLOSE);
    }
    backEdges.clear();
    componentsDetected_ = true;
    return componentCount;
}

Referenced by analyzeCDG().

Here is the call graph for this function:

◆ eliminateMultipleOutputs()

void ControlDependenceGraph::eliminateMultipleOutputs ( )

private

Internal helper. Replaces several output edges with same truth value with region node. Combines several output edges without truth value (indirect jumps for example);

Combine all "true" children of predicate with region

Combine all "false" children of predicate with region

Definition at line 692 of file ControlDependenceGraph.cc.

                                                 {
    for (int i = 0; i < nodeCount(); i++) {
        if (outDegree(node(i)) > 1 && node(i).isBBNode()) {
            std::vector<Node*> trueLinks;
            std::vector<Node*> falseLinks;
            Node& currNode = node(i);
            int currDegree = outDegree(currNode);
            for (int j = 0; j < currDegree; j++) {
                Edge* currentOutEdge = &outEdge(currNode, j);
                if (currentOutEdge->isTrueEdge()) {
                    trueLinks.push_back(&headNode(*currentOutEdge));
                    continue;
                }
                if (currentOutEdge->isFalseEdge()) {
                    falseLinks.push_back(&headNode(*currentOutEdge));
                    continue;
                }
            }
            /// Combine all "true" children of predicate with region
            if (trueLinks.size() > 1) {
                Node* regNode = new Node(Node::CDEP_NODE_REGION);
                addNode(*regNode);
                createControlDependenceEdge(
                    currNode, *regNode, Edge::CDEP_EDGE_TRUE);
                for (unsigned int j = 0; j < trueLinks.size(); j++) {
                    createControlDependenceEdge(*regNode, *trueLinks[j]);
                    disconnectNodes(currNode, *(trueLinks[j]));
                }
            }
            /// Combine all "false" children of predicate with region
            if (falseLinks.size() > 1) {
                Node* regNode = new Node(Node::CDEP_NODE_REGION);
                addNode(*regNode);
                createControlDependenceEdge(
                    currNode, *regNode, Edge::CDEP_EDGE_FALSE);
                for (unsigned int j = 0; j < falseLinks.size(); j++) {
                    createControlDependenceEdge(*regNode, *falseLinks[j]);
                    disconnectNodes(currNode, *(falseLinks[j]));
                }
            }
        }
    }
}

Referenced by computeDependence().

Here is the call graph for this function:

◆ entryNode()

ControlDependenceNode & ControlDependenceGraph::entryNode ( )

Return the entry node of the graph. Cache it after it's found for alter use

Returns: The entry node of the graph.

Exceptions

InstanceNotFound	if the graph does not have a entry node.
ModuleRunTimeError	if the graph has multiple nodes that are recognised as entry nodes.

Definition at line 496 of file ControlDependenceGraph.cc.

                                  {
    if (entryNode_ == NULL) {
        Node* result = NULL;
        bool found = false;
        for (int i = 0; i < nodeCount(); i++) {
            if (inDegree(node(i)) == 0) {
                // sanity check
                if (!static_cast<Node&>(node(i)).isEntryNode()) {
                    // probably the entry node is not present
                    TCEString errorMsg = (boost::format(
                        "Graph %s has node %s with no input edges which is "
                        "not the entry node!\n") % name()
                        % node(i).toString()).str();
                    throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
                        errorMsg);
                }
                if (found == true) {
                    throw ModuleRunTimeError(
                        __FILE__, __LINE__, __func__,
                        "Corrupted graph. Found multiple entry nodes!");
                }
                result = dynamic_cast<Node*>(&node(i));
                found = true;
            }
        }
        if (found == false || result == NULL) {
            TCEString errorMsg = (boost::format(
                "Graph %s does not have entry node or has mutliple nodes with"
                " no input edges!") % name()).str();
            throw ModuleRunTimeError(__FILE__, __LINE__, __func__, errorMsg);
        }
        entryNode_ = result;
        return *result;
    } else {
        return *entryNode_;
    }
}

References __func__, entryNode_, BoostGraph< ControlDependenceNode, ControlDependenceEdge >::inDegree(), ControlDependenceNode::isEntryNode(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::name(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::node(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::nodeCount(), and GraphNode::toString().

Referenced by analyzeCDG(), and computeRegionInfo().

Here is the call graph for this function:

◆ findSubset()

bool ControlDependenceGraph::findSubset	(	DependentOn *	wholeSet,
		DependentOn *	subSet,
		Node *	regNode
	)

private

Internal helper. Find already existing region node in set of dependencies.

Find if set of dependencies contains a subset that has already a region node. If so, modifies dependencies to contain dependence to existing region node.

Parameters

wholeSet	Set of dependencies for node we want to test
subSet	Set corresponding to some already existing region node
regNode	Region node we are testing

Returns: True if the intersection was found

Definition at line 252 of file ControlDependenceGraph.cc.

                   {
 
    if (subSet->size() > wholeSet->size()) {
        return false;
    }
    std::vector<SourceType> missing;
    unsigned int numberOfFound = 0;
    for (unsigned int i = 0; i < wholeSet->size(); i++) {
        SourceType test = wholeSet->at(i);
        bool found = false;
        for (unsigned int j = 0; j < subSet->size(); j++) {
            SourceType tmp = subSet->at(j);
            if (test.first == tmp.first && test.second == tmp.second) {
                found = true;
                numberOfFound++;
            }
        }
        if (found == false) {
            missing.push_back(test);
        }
    }
    if (numberOfFound != subSet->size()) {
        return false;
    }
    wholeSet->clear();
    for (unsigned int i = 0; i < missing.size(); i++) {
        wholeSet->push_back(missing[i]);
    }
    wholeSet->push_back(
        SourceType(regNode,Edge::CDEP_EDGE_NORMAL));
    missing.clear();
    return true;
}

References ControlDependenceEdge::CDEP_EDGE_NORMAL.

Referenced by computeDependence().

◆ nearestCommonDom()

int ControlDependenceGraph::nearestCommonDom	(	std::vector< int > &	iDom,
		int	node1,
		int	node2
	)		const

private

Internal hepler. Compute the nearest common dominator of two nodes.

Given two nodes (identified by their traversal order), find the nearest common ancestor that dominates both.

Note: this method should go in separate immediate dominator class.

Parameters

iDom	Tree of immediate dominators.
node1	A graph node.
node2	Another graph node.

Returns: The post-order number of the nearest dominator of given nodes.

Definition at line 303 of file ControlDependenceGraph.cc.

                     {
 
    int finger1 = node1;
    int finger2 = node2;
    do {
        while (finger1 < finger2) {
            finger1 = iDom[finger1];
        }
        while (finger2 < finger1) {
            finger2 = iDom[finger2];
        }
    } while (finger1 != finger2);
    return finger1;
}

Referenced by createPostDominanceTree().

◆ processRegion()

void ControlDependenceGraph::processRegion ( Node * regionNode )

private

"Sorts" all the child nodes of a region in topological order based on their control and data dependencies.

Parameters

regionNode	Region node who's child nodes to process
cdgGraph	Control Dependence subraph

Get all child nodes of region node

node1 will be compared against all the other previously untested nodes

Test relation between siblings, should never return ERROR twice!

Definition at line 1437 of file ControlDependenceGraph.cc.

                                                      {
 
    /// Get all child nodes of region node
 
    EdgeSet edges = outEdges(*regionNode);
 
    std::vector<std::pair<Node*, Node*> > newEdges;
    for (EdgeSet::iterator ei1 = edges.begin();
        ei1 != edges.end();
        ++ei1) {
        Node* node1 = &headNode(**ei1);
 
        /// node1 will be compared against all the other previously untested
        /// nodes
        EdgeSet::iterator ei2 = ei1;
        ei2++;
        for (; ei2 != edges.end(); ++ei2) {
            Node* node2 = &headNode(**ei2);
 
            /// Test relation between siblings, should never return ERROR twice!
            CompareResult result = compareSiblings(node1, node2);
            if (result == ERROR) {
                result = compareSiblings(node2, node1);
            }
            switch(result) {
                case A_BEFORE_B:
                    newEdges.push_back(std::pair<Node*, Node*>(node1, node2));
                    break;
                case B_BEFORE_A:
                    newEdges.push_back(std::pair<Node*, Node*>(node2, node1));
                    break;
                case UNORDERABLE:
                    if(Application::verboseLevel() > DEBUG_LEVEL) {
                        Application::logStream() << (boost::format(
                            "Nodes %s and %s can not be put into any order.\n")
                            % node1->toString()% node2->toString()).str();
                    }
                    break;
                case ANY_ORDER:
                    break;
                case ERROR:
                    throw ModuleRunTimeError(
                        __FILE__, __LINE__, __func__, (boost::format(
                            "Ordering error for A='%s' and B='%s'.")
                            % node1->toString() % node2->toString()).str());
                    break;
            }
        }
    }
    return;
#if 0
    /// This is just for testing
    /// Add actuall control dependence edges for serialization
    /// Edges are really not needed here, they will be added into PDG
    for (unsigned int i = 0; i < newEdges.size(); i++) {
        ControlDependenceEdge* direction = new ControlDependenceEdge();
        connectNodes(*newEdges[i].first, *newEdges[i].second, *direction);
    }
    return;
#endif
}

References __func__, A_BEFORE_B, ANY_ORDER, B_BEFORE_A, compareSiblings(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::connectNodes(), DEBUG_LEVEL, ERROR, BoostGraph< ControlDependenceNode, ControlDependenceEdge >::headNode(), Application::logStream(), BoostGraph< ControlDependenceNode, ControlDependenceEdge >::outEdges(), ControlDependenceNode::toString(), UNORDERABLE, and Application::verboseLevel().

Referenced by computeRelations().

Here is the call graph for this function:

◆ program()

TTAProgram::Program * ControlDependenceGraph::program ( ) const

Returns the pointer to Program object of POM procedure belongs to.

Returns: Pointer to TTAProgram::Program

Definition at line 682 of file ControlDependenceGraph.cc.

                                      {
    return program_;
}

References program_.

Referenced by ProgramDependenceGraph::disassemble(), and ProgramDependenceGraph::ProgramDependenceGraph().

◆ regionHelper()

void ControlDependenceGraph::regionHelper	(	Node *	node,
		Node::NodesInfo &	finalNodesInfo
	)

private

Helper function to compute actual region information for a node. Called several times for a case when there are loop entry nodes detected.

Parameters

node	Node for which to compute region info
cdg	Filtered PDG graph with only control dependence edges
finalNodesInfo	stores actuall computed region info

Find all incoming control dependence edges

If parent's region is not yet computed (should be btw) compute it before continuing.

region(node,parent) == region(parent) U childern(parent)

region(node,parent) == region(parent)

fill in final region info with info from first of parents

region(node) = intersection(region(node,parent(node))) for all parents. finalNodesInfo is already initialized from counter 0

Definition at line 1338 of file ControlDependenceGraph.cc.

                                  {
 
    std::vector<Node::NodesInfo> tmpResult;
    /// Find all incoming control dependence edges
    EdgeSet edges = inEdges(*node);
    for (EdgeSet::iterator ei = edges.begin();
        ei != edges.end();
        ++ei) {
        Node* previous = &tailNode(**ei);
        if (previous->isRegionNode()
            || previous->isLoopEntryNode()
            || previous->isEntryNode()) {
            if (previous->region().size() == 0 &&
                !previous->isEntryNode()) {
                /// If parent's region is not yet computed (should be btw)
                /// compute it before continuing.
                Node::NodesInfo addedNodesInfo;
                regionHelper(previous, addedNodesInfo);
                for (Node::NodesInfo::iterator k = addedNodesInfo.begin();
                    k != addedNodesInfo.end();
                    k++) {
                    previous->addToRegion(**k);
                }
            }
            /// region(node,parent) == region(parent) U childern(parent)
            Node::NodesInfo tmp = previous->region();
            EdgeSet outgoingEdges = outEdges(*previous);
            for (EdgeSet::iterator ei = outgoingEdges.begin();
                ei != outgoingEdges.end();
                ++ei) {
                Node* testedNode = &headNode(**ei);
                tmp.insert(testedNode);
            }
            tmpResult.push_back(tmp);
        } else if (previous->isPredicateNode()){
        /// region(node,parent) == region(parent)
            Node::NodesInfo tmp = previous->region();
            tmpResult.push_back(tmp);
        } else {
            if (!previous->isLoopCloseNode()) {
                TCEString message = (boost::format(
                    "Node: %s , parent %s.")
                    % node->toString() % previous->toString()).str();
                throw ModuleRunTimeError(__FILE__, __LINE__, __func__, message);
            }
        }
    }
    /// fill in final region info with info from first of parents
    if (tmpResult.size() > 0) {
        finalNodesInfo.insert(
            tmpResult[0].begin(), tmpResult[0].end());
    }
    /// region(node) = intersection(region(node,parent(node)))
    /// for all parents. finalNodesInfo is already initialized from
    /// counter 0
    for (unsigned int l = 1; l < tmpResult.size(); l++) {
        Node::NodesInfo storeResult;
        SetTools::intersection(
            finalNodesInfo, tmpResult[l], storeResult);
        finalNodesInfo.swap(storeResult);
        storeResult.clear();
    }
}

Referenced by computeRegionInfo(), and regionHelper().

Here is the call graph for this function:

Member Data Documentation

◆ alignment_

int ControlDependenceGraph::alignment_

private

Definition at line 136 of file ControlDependenceGraph.hh.

Referenced by alignment(), and ControlDependenceGraph().

◆ analyzed_

bool ControlDependenceGraph::analyzed_

private

Indicates that CDG already has data required for serialization.

Definition at line 142 of file ControlDependenceGraph.hh.

Referenced by analyzeCDG(), and analyzed().

◆ cGraph_

ControlFlowGraph* ControlDependenceGraph::cGraph_

private

Definition at line 138 of file ControlDependenceGraph.hh.

Referenced by computeDependence(), ControlDependenceGraph(), createPostDominanceTree(), and detectControlDependencies().

◆ componentsDetected_

bool ControlDependenceGraph::componentsDetected_

private

Definition at line 145 of file ControlDependenceGraph.hh.

Referenced by detectStrongComponents().

◆ entryNode_

Node* ControlDependenceGraph::entryNode_

private

Stores reference to entryNode of the graph.

Definition at line 144 of file ControlDependenceGraph.hh.

Referenced by entryNode().

◆ iDomTree_

std::vector<int> ControlDependenceGraph::iDomTree_

private

Definition at line 139 of file ControlDependenceGraph.hh.

Referenced by computeDependence(), createPostDominanceTree(), and detectControlDependencies().

◆ program_

TTAProgram::Program* ControlDependenceGraph::program_

private

Definition at line 134 of file ControlDependenceGraph.hh.

Referenced by ControlDependenceGraph(), and program().

◆ startAddress_

TTAProgram::Address ControlDependenceGraph::startAddress_

private

Definition at line 135 of file ControlDependenceGraph.hh.

◆ strongComponents_

std::vector<std::set<Node*> > ControlDependenceGraph::strongComponents_

private

Definition at line 140 of file ControlDependenceGraph.hh.

Referenced by componentCount(), computeEECInfo(), computeRegionInfo(), detectStrongComponents(), and ~ControlDependenceGraph().

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

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ BlockVector

◆ CDGOrder

◆ CDGOrderMap

◆ Color

◆ ColorMap

◆ DependenceMap

◆ DependentOn

◆ DescriptorMap

◆ Descriptors

◆ PostOrder

◆ PostOrderMap

◆ SourceType

Member Enumeration Documentation

◆ CompareResult

Constructor & Destructor Documentation

◆ ControlDependenceGraph()

◆ ~ControlDependenceGraph()

Member Function Documentation

◆ alignment()

◆ analyzeCDG()

◆ analyzed()

◆ compareSiblings()

◆ componentCount()

◆ computeDependence()

◆ computeEECInfo()

◆ computeRegionInfo()

◆ computeRelations()

◆ createControlDependenceEdge()

◆ createPostDominanceTree()

◆ detectControlDependencies()

◆ detectStrongComponents()

◆ eliminateMultipleOutputs()

◆ entryNode()

◆ findSubset()

◆ nearestCommonDom()

◆ processRegion()

◆ program()

◆ regionHelper()

Member Data Documentation

◆ alignment_

◆ analyzed_

◆ cGraph_

◆ componentsDetected_

◆ entryNode_

◆ iDomTree_

◆ program_

◆ startAddress_

◆ strongComponents_