#include <DataDependenceGraph.hh>

Inheritance diagram for DataDependenceGraph:

Collaboration diagram for DataDependenceGraph:

Classes
struct	UndoData

Public Types
enum	AntidependenceLevel { NO_ANTIDEPS , INTRA_BB_ANTIDEPS , SINGLE_BB_LOOP_ANTIDEPS , ALL_ANTIDEPS }

enum	DumpFileFormat { DUMP_DOT , DUMP_XML }

enum	EdgeWeightHeuristics { EWH_HEURISTIC , EWH_REAL , EWH_DEFAULT = EWH_HEURISTIC }

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

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

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

typedef DataDependenceEdge	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
	DataDependenceGraph (std::set< TCEString > allParamRegs, const TCEString &name="", AntidependenceLevel antidependenceLevel=ALL_ANTIDEPS, BasicBlockNode *ownedBBN=NULL, bool containsProcedure=false, bool noLoopEdges=false)

virtual	~DataDependenceGraph ()

const BasicBlockNode &	getBasicBlockNode (const MoveNode &mn) const

BasicBlockNode &	getBasicBlockNode (MoveNode &mn)

void	setBasicBlockNode (const MoveNode &mn, BasicBlockNode &bbn)

int	programOperationCount () const

ProgramOperation &	programOperation (int index)

const ProgramOperation &	programOperation (int index) const

ProgramOperationPtr	programOperationPtr (int index)

DataDependenceEdge *	onlyRegisterEdgeIn (MoveNode &mn) const

DataDependenceEdge *	onlyRegisterEdgeOut (MoveNode &mn) const

void	addNode (MoveNode &moveNode)

void	addNode (MoveNode &moveNode, MoveNode &relatedNode)

void	addNode (MoveNode &moveNode, BasicBlockNode &bblock)

void	addProgramOperation (ProgramOperationPtr po)

void	dropProgramOperation (ProgramOperationPtr po)

int	edgeLatency (const DataDependenceEdge &edge, int ii, const MoveNode tail, const MoveNode head) const

int	earliestCycle (const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegWaRs=false, bool ignoreRegWaWs=false, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false, bool assumeBypassing=false) const

int	latestCycle (const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegAntideps=false, bool ignoreUnscheduledSuccessors=true, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false) const

bool	hasUnscheduledSuccessors (const MoveNode &mn) const

bool	hasUnscheduledPredecessors (const MoveNode &mn) const

int	smallestCycle () const

int	largestCycle () const

int	scheduledNodeCount () const

NodeSet	unscheduledMoves () const

NodeSet	scheduledMoves () const

NodeSet	movesAtCycle (int cycle) const

MoveNode *	onlyGuardDefOfMove (MoveNode &moveNode)

MoveNode *	lastGuardDefMove (MoveNode &moveNode)

NodeSet	guardDefMoves (const MoveNode &moveNode)

MoveNode *	lastScheduledRegisterRead (const TTAMachine::BaseRegisterFile &rf, int registerIndex, int lastCycleToTest=INT_MAX) const

NodeSet	lastScheduledRegisterReads (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

NodeSet	lastScheduledRegisterGuardReads (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

NodeSet	lastScheduledRegisterWrites (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

MoveNode *	firstScheduledRegisterRead (const TTAMachine::BaseRegisterFile &rf, int registerIndex, int firstCycleToTest=0) const

MoveNode *	firstScheduledRegisterWrite (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

NodeSet	firstScheduledRegisterWrites (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

NodeSet	firstScheduledRegisterReads (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

MoveNode *	lastScheduledRegisterKill (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

MoveNode *	firstScheduledRegisterKill (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

int	lastRegisterCycle (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

int	firstRegisterCycle (const TTAMachine::BaseRegisterFile &rf, int registerIndex) const

void	sanityCheck () const

virtual TCEString	dotString () const
	Dot printing related methods.

virtual void	setCycleGrouping (bool flag)

virtual void	setProgramOperationNodes (bool flag)

void	writeToXMLFile (std::string fileName) const

bool	mergeAndKeepAllowed (MoveNode &sourceNode, MoveNode &userNode)

TCEString	removeRAWEdges (MoveNode &sourceNode, MoveNode &userNode)

bool	isLoopBypass (MoveNode &sourceNode, MoveNode &userNode)

bool	mergeAndKeepUser (MoveNode &resultNode, MoveNode &userNode, bool force=false)

bool	mergeAndKeepSource (MoveNode &resultNode, MoveNode &userNode, bool force=false)

void	unMergeUser (MoveNode &resultNode, MoveNode &mergedNode, bool loopBypass=false)

void	guardConverted (MoveNode &guardSrc, MoveNode &dst)

void	guardRestored (MoveNode &guardSrc, MoveNode &dst)

bool	resultUsed (MoveNode &resultNode)

bool	resultUsed (MoveNode &resultNode, MoveNode *regCopy)

void	removeNode (MoveNode &node)

void	deleteNode (MoveNode &node)

void	setEdgeWeightHeuristics (EdgeWeightHeuristics ewh)

int	edgeWeight (DataDependenceEdge &e, const MoveNode &hNode) const

bool	predecessorsReady (MoveNode &node) const

bool	successorsReady (MoveNode &node) const

bool	otherSuccessorsScheduled (MoveNode &node, const NodeSet &ignoredNodes) const

void	setMachine (const TTAMachine::Machine &machine)

const TTAMachine::Machine &	machine () const

bool	connectOrDeleteEdge (const MoveNode &tailNode, const MoveNode &headNode, DataDependenceEdge *edge)

DataDependenceGraph *	createSubgraph (NodeSet &nodes, bool includeLoops=false)

DataDependenceGraph *	createSubgraph (TTAProgram::CodeSnippet &cs, bool includeLoops=false)

DataDependenceGraph *	createSubgraph (std::list< TTAProgram::CodeSnippet * > &codeSnippets, bool includeLoops=false)

DataDependenceGraph *	trueDependenceGraph (bool removeMemAntideps=true, bool ignoreMemDeps=false)

DataDependenceGraph *	criticalPathGraph ()

DataDependenceGraph *	memoryDependenceGraph ()

MoveNode &	nodeOfMove (const TTAProgram::Move &move)

void	dropBackEdges ()

void	fixInterBBAntiEdges (BasicBlockNode &bbn1, BasicBlockNode &bbn2, bool loopEdges)

void	copyDependencies (const MoveNode &src, MoveNode &dst, bool ignoreSameBBBackedges, bool moveOverLoopEdge=true)

void	copyIncomingGuardEdges (const MoveNode &src, MoveNode &dst)

void	copyOutgoingGuardWarEdges (const MoveNode &src, MoveNode &dst)

NodeSet	guardRawPredecessors (const MoveNode &node) const

DataDependenceEdge *	onlyIncomingGuard (const MoveNode &mn) const

MoveNode *	onlyRegisterRawSource (const MoveNode &mn, int allowGuardEdges=2, int backEdges=0) const

NodeSet	onlyRegisterRawDestinations (const MoveNode &mn, bool allowGuardEdges=false, bool allowBackEdges=false) const

std::map< DataDependenceEdge , MoveNode , DataDependenceEdge::Comparator >	onlyRegisterRawDestinationsWithEdges (const MoveNode &mn, bool allowBackEdges) const

NodeSet	regWarSuccessors (const MoveNode &node) const

NodeSet	regRawSuccessors (const MoveNode &node) const

NodeSet	regWawSuccessors (const MoveNode &node) const

NodeSet	regDepSiblings (const MoveNode &mn) const

NodeSet	regRawPredecessors (const MoveNode &node, int backedges=0) const

void	createRegisterAntiDependenciesBetweenNodes (NodeSet &nodes)

bool	exclusingGuards (const MoveNode &mn1, const MoveNode &mn2) const

bool	sameGuards (const MoveNode &mn1, const MoveNode &mn2) const

int	rWarEdgesOut (MoveNode &mn)

int	regRawSuccessorCount (const MoveNode &mn, bool onlyScheduled)

bool	guardsAllowBypass (const MoveNode &defNode, const MoveNode &useNode, bool loopBypass=false)

const MoveNode *	onlyRegisterRawAncestor (const MoveNode &node, const std::string &sp) const

EdgeSet	copyDepsOver (MoveNode &node, bool anti, bool raw)

void	copyDepsOver (MoveNode &node1, MoveNode &node2, bool anti, bool raw)

void	combineNodes (MoveNode &node1, MoveNode &node2, MoveNode &destination)

std::pair< MoveNode , MoveNode >	findLoopLimitAndIndex (MoveNode &jumpMove)

std::pair< MoveNode *, int >	findLoopIndexUpdate (MoveNode *indexMove)

MoveNode *	findLoopIndexInit (MoveNode &updateMove)

bool	writesJumpGuard (const MoveNode &moveNode)

void	moveFUDependenciesToTrigger (MoveNode &trigger)

LiveRange *	findLiveRange (MoveNode &lrNode, bool writingNode, bool guardUseNode) const

MoveNode *	findLimitingAntidependenceSource (MoveNode &mn)

MoveNode *	findLimitingAntidependenceDestination (MoveNode &mn)

DataDependenceGraph::UndoData	sourceRenamed (MoveNode &mn)

DataDependenceGraph::UndoData	guardRenamed (MoveNode &mn)

DataDependenceGraph::UndoData	destRenamed (MoveNode &mn)

void	renamedSimpleLiveRange (MoveNode &src, MoveNode &dest, MoveNode &antidepPoint, DataDependenceEdge &lrEdge, const TCEString &oldReg, const TCEString &newReg)

void	copyExternalInEdges (MoveNode &nodeCopy, const MoveNode &source)

void	copyExternalOutEdges (MoveNode &nodeCopy, const MoveNode &source)

DataDependenceGraph::EdgeSet	updateRegWrite (const MoveNodeUse &mnd, const TCEString &reg, TTAProgram::BasicBlock &bb)

void	updateRegUse (const MoveNodeUse &mnd, const TCEString &reg, TTAProgram::BasicBlock &bb)

void	removeIncomingGuardEdges (MoveNode &node)

void	removeOutgoingGuardWarEdges (MoveNode &node)

bool	hasAllRegisterAntidependencies ()

bool	hasSingleBBLoopRegisterAntidependencies ()

bool	hasIntraBBRegisterAntidependencies ()

bool	hasRegWaw (const MoveNodeUse &mnu, std::set< MoveNodeUse > targets) const

bool	isNotAvoidable (const DataDependenceEdge &edge) const

bool	isLoopInvariant (const MoveNode &mn) const

bool	hasOtherRegWawSources (const MoveNode &mn) const

MoveNode *	findBypassSource (const MoveNode &mn)

void	copyIncomingRawEdges (const MoveNode &src, MoveNode &dst)

void	fixAntidepsAfterLoopUnmergeUser (MoveNode &sourceNode, MoveNode &mergedNode, const TCEString &reg)

void	setNodeBB (MoveNode &mn, BasicBlockNode &bblock, DataDependenceGraph *updater)

void	undo (UndoData &undoData)

EdgeSet	operationInEdges (const MoveNode &node) const

EdgeSet	registerAndRAInEdges (const MoveNode &node) const

Public Member Functions inherited from BoostGraph< MoveNode, DataDependenceEdge >
	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 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	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 MoveNode &node) const

int	maxSinkDistance (const MoveNode &node) const

int	maxSourceDistance (const MoveNode &node) const

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

void	restoreNodeFromParent (MoveNode &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 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 Member Functions
bool	queueRawPredecessors (NodeSet &queue, NodeSet &finalDest, NodeSet &predQueue, NodeSet &predFinalDest, bool guard) const

bool	rWawRawEdgesOutUncond (MoveNode &mn)

int	rAntiEdgesIn (MoveNode &mn)

bool	isRootGraphProcedureDDG ()

bool	hasEqualEdge (const MoveNode &tailNode, const MoveNode &headNode, const DataDependenceEdge &edge) const

int	getOperationLatency (const TCEString &name) const

Private Attributes
std::set< TCEString >	allParamRegs_

std::map< const TTAProgram::Move , MoveNode >	nodesOfMoves_

POList	programOperations_

std::map< const MoveNode , BasicBlockNode >	moveNodeBlocks_

bool	cycleGrouping_
	Dot printing related variables. Group the printed MoveNodes according to their cycles.

bool	dotProgramOperationNodes_
	The moves belonging to the same program operation are merged to a single node. Reduces the complexity of the graph.

const TTAMachine::Machine *	machine_

int	delaySlots_

std::map< TCEString, int >	operationLatencies_

int	rrCost_

BasicBlockNode *	ownedBBN_

bool	procedureDDG_

AntidependenceLevel	registerAntidependenceLevel_

EdgeWeightHeuristics	edgeWeightHeuristics_
	The heuristics to use to weight edges in the longest path computation.

Additional Inherited Members
Protected Types inherited from BoostGraph< MoveNode, DataDependenceEdge >
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< MoveNode, DataDependenceEdge >
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< MoveNode, DataDependenceEdge > *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 MoveNode tailNode, const MoveNode 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 (MoveNode &dest)

void	calculatePathLengths () const

void	calculatePathLengthsFast () const

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

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

void	calculatePathLengthsOnConnect (const MoveNode &nTail, const MoveNode &nHead, DataDependenceEdge &e)

void	sinkDistDecreased (const MoveNode &n) const

void	sourceDistDecreased (const MoveNode &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< MoveNode, DataDependenceEdge >
std::unordered_map< const MoveNode *, int >	sourceDistances_

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

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

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

int	height_

Graph	graph_
	The internal graph structure.

EdgeDescMap	edgeDescriptors_

NodeDescMap	nodeDescriptors_

BoostGraph< MoveNode, DataDependenceEdge > *	parentGraph_

std::vector< BoostGraph< MoveNode, DataDependenceEdge > * >	childGraphs_

TCEString	name_

int	sgCounter_

std::set< Edge * >	ownedEdges_

bool	allowLoopEdges_

PathCache *	pathCache_

Detailed Description

Definition at line 67 of file DataDependenceGraph.hh.

Member Enumeration Documentation

◆ AntidependenceLevel

enum DataDependenceGraph::AntidependenceLevel

Enumerator
NO_ANTIDEPS
INTRA_BB_ANTIDEPS
SINGLE_BB_LOOP_ANTIDEPS
ALL_ANTIDEPS

Definition at line 78 of file DataDependenceGraph.hh.

                             {
        NO_ANTIDEPS,
        INTRA_BB_ANTIDEPS,
        SINGLE_BB_LOOP_ANTIDEPS,
        ALL_ANTIDEPS
    };

◆ DumpFileFormat

enum DataDependenceGraph::DumpFileFormat

Enumerator
DUMP_DOT
DUMP_XML

Definition at line 85 of file DataDependenceGraph.hh.

                        {
        DUMP_DOT,
        DUMP_XML
    };

◆ EdgeWeightHeuristics

enum DataDependenceGraph::EdgeWeightHeuristics

Enumerator
EWH_HEURISTIC	Weights memory dependencies more, etc.
EWH_REAL	Height returns the minimum cycle count for the schedule given enough resources.
EWH_DEFAULT

Definition at line 90 of file DataDependenceGraph.hh.

                              {        
        EWH_HEURISTIC,   ///< Weights memory dependencies more, etc.
        EWH_REAL,        ///< Height returns the minimum cycle count for the
                         ///< schedule given enough resources.
        EWH_DEFAULT = EWH_HEURISTIC
    };

Constructor & Destructor Documentation

◆ DataDependenceGraph()

DataDependenceGraph::DataDependenceGraph	(	std::set< TCEString >	allParamRegs,
		const TCEString &	name = `""`,
		AntidependenceLevel	antidependenceLevel = `ALL_ANTIDEPS`,
		BasicBlockNode *	ownedBBN = `NULL`,
		bool	containsProcedure = `false`,
		bool	noLoopEdges = `false`
	)

Constructor.

Parameters

name	The graph can be named for debugging purposes.
containsProcedure	whether the DDG contains complete procedure.
ownedBBN	if the DDG should delete a BBn at destructor.
containsProcedure	if the ddg contains a whole procedure.
if	the ddg should not accept loop edges.
antidependenceLevel	level of register antidependencies which this ddg should contain.

Definition at line 78 of file DataDependenceGraph.cc.

                      :
    BoostGraph<MoveNode, DataDependenceEdge>(name, !noLoopEdges), 
    allParamRegs_(allParamRegs), cycleGrouping_(true), 
    dotProgramOperationNodes_(false),
    machine_(NULL), delaySlots_(0), rrCost_(3), ownedBBN_(ownedBBN),
    procedureDDG_(containsProcedure), 
    registerAntidependenceLevel_(antidependenceLevel),
    edgeWeightHeuristics_(EWH_HEURISTIC) {
}

◆ ~DataDependenceGraph()

DataDependenceGraph::~DataDependenceGraph ( )

virtual

Deletes all MoveNodes and ProgramOperations.

Definition at line 95 of file DataDependenceGraph.cc.

                                          {
 
    if (parentGraph_ == NULL) {
 
        //delete nodes.
        int nc = nodeCount();
        for (int i = 0; i < nc; i++) {
            delete &node(i, false);
        }
        programOperations_.clear();
    }
    if (ownedBBN_ != NULL) {
        delete ownedBBN_;
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), ownedBBN_, BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, and programOperations_.

Here is the call graph for this function:

Member Function Documentation

◆ addNode() [1/3]

void DataDependenceGraph::addNode ( MoveNode & moveNode )

virtual

Adds a node into the graph.

This method should not be called by the user, used internally

Parameters

moveNode moveNode being added.

Reimplemented from BoostGraph< MoveNode, DataDependenceEdge >.

Definition at line 144 of file DataDependenceGraph.cc.

                                               {
    BoostGraph<MoveNode, DataDependenceEdge>::addNode(moveNode);
    if (moveNode.isMove()) {
        nodesOfMoves_[&moveNode.move()] = &moveNode;
    }
}

References BoostGraph< GraphNode, GraphEdge >::addNode(), MoveNode::isMove(), MoveNode::move(), and nodesOfMoves_.

Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), RegisterCopyAdder::addConnectionRegisterCopiesImmediate(), addNode(), addNode(), LoopPrologAndEpilogBuilder::build(), LLVMTCEDataDependenceGraphBuilder::buildLocalDDG(), DataDependenceGraphBuilder::constructIndividualBB(), DataDependenceGraphBuilder::constructIndividualFromInlineAsmBB(), DataDependenceGraphBuilder::createRegisterDeps(), MoveNodeDuplicator::duplicateMoveNode(), CopyingDelaySlotFiller::getMoveNode(), BFRegCopy::operator()(), and PreOptimizer::tryToRemoveGuardInversingOp().

Here is the call graph for this function:

◆ addNode() [2/3]

void DataDependenceGraph::addNode	(	MoveNode &	moveNode,
		BasicBlockNode &	bblock
	)

Adds a node into the graph.

Parameters

moveNode	moveNode being added.
bblock	Basic block where the move logically belongs.

Definition at line 158 of file DataDependenceGraph.cc.

                                                                       {
    addNode(moveNode);
    setNodeBB(moveNode, bblock, NULL);
}

References addNode(), and setNodeBB().

Here is the call graph for this function:

◆ addNode() [3/3]

void DataDependenceGraph::addNode	(	MoveNode &	moveNode,
		MoveNode &	relatedNode
	)

Adds a node into the graph.

Parameters

moveNode	moveNode being added.
relatedNode	another node already existing in the graph where this movenode relates to. , for example is created by splitting that

Todo:: : also add to subgrapsh which have the related node?

Definition at line 172 of file DataDependenceGraph.cc.

                                                                      {
    addNode(moveNode);
    setNodeBB(moveNode, getBasicBlockNode(relatedNode), NULL);
    ///  @todo: also add to subgrapsh which have the related node?
}

References addNode(), getBasicBlockNode(), and setNodeBB().

Here is the call graph for this function:

◆ addProgramOperation()

void DataDependenceGraph::addProgramOperation ( ProgramOperationPtr po )

Adds a program operation to the graph, and its parent graphs.

Parameters

po	ProgramOperation being added.

Definition at line 298 of file DataDependenceGraph.cc.

                                                               {
    for (int i = 0; i < programOperationCount(); i++) {
        if (programOperations_[i] == po) {
            return;
        }
    }
    programOperations_.push_back(po);
    if (parentGraph_ != NULL) {
        dynamic_cast<DataDependenceGraph*>(parentGraph_)
            ->addProgramOperation(po);
    }
}

References addProgramOperation(), BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, programOperationCount(), and programOperations_.

Referenced by addProgramOperation(), LLVMTCEDataDependenceGraphBuilder::buildLocalDDG(), DataDependenceGraphBuilder::processResultRead(), DataDependenceGraphBuilder::processTriggerPO(), and BFRemoveLoopChecksAndJump::undoOnlyMe().

Here is the call graph for this function:

◆ combineNodes()

void DataDependenceGraph::combineNodes	(	MoveNode &	node1,
		MoveNode &	node2,
		MoveNode &	destination
	)

Definition at line 2782 of file DataDependenceGraph.cc.

                                                             {
 
    DataDependenceGraph::NodeDescriptor nd1 = descriptor(node1);
    DataDependenceGraph::NodeDescriptor nd2 = descriptor(node2);
 
    moveOutEdges(node2, destination);
    moveInEdges(node1, destination);
 
    EdgeSet oEdges1 = outEdges(node1);
    EdgeSet iEdges2 = inEdges(node2);
 
    // copy WARs over.
    for (EdgeSet::iterator i = oEdges1.begin(); i != oEdges1.end(); i++) {
        DataDependenceEdge& oEdge = **i;
 
        if ((oEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER
             || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA) && 
            oEdge.dependenceType() == DataDependenceEdge::DEP_WAR) {
 
            MoveNode& head = headNode(oEdge,nd1);
            if (&head == &node2) {
                continue;
            }
            moveOutEdge(node1, destination, oEdge);
        }
    }
 
    for (EdgeSet::iterator i = iEdges2.begin(); i != iEdges2.end(); i++) {
        DataDependenceEdge& iEdge = **i;
        
        if ((iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER
             || iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) && 
            (iEdge.dependenceType() == DataDependenceEdge::DEP_WAR 
             || iEdge.dependenceType() == DataDependenceEdge::DEP_WAW)) {
 
            MoveNode& tail = tailNode(iEdge,nd2);
            if (&tail == &node1) {
                continue;
            }
            moveInEdge(node2, destination, iEdge);
        }
    }
}

Referenced by PreOptimizer::tryToRemoveGuardInversingOp().

Here is the call graph for this function:

◆ connectOrDeleteEdge()

bool DataDependenceGraph::connectOrDeleteEdge	(	const MoveNode &	tailNode,
		const MoveNode &	headNode,
		DataDependenceEdge *	edge
	)

Connects nodes with an edge if equal edge between nodes not exists. If equal edge already exists, deletes the given edge.

Parameters

tailNode	tail node of edge
headNode	head node of edge
edge	edge which is added to graph or deleted.

Returns: true if connected, false if already existed.

Definition at line 3355 of file DataDependenceGraph.cc.

                              {
    if (hasEqualEdge(tailNode, headNode, *edge)) {
        delete edge;
        return false;
    } else {
        connectNodes(tailNode, headNode, *edge);
        return true;
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), hasEqualEdge(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by DataDependenceGraphBuilder::checkAndCreateMemDep(), copyDepsOver(), copyDepsOver(), DataDependenceGraphBuilder::createOperationEdges(), createRegisterAntiDependenciesBetweenNodes(), DataDependenceGraphBuilder::createRegisterAntideps(), DataDependenceGraphBuilder::createSideEffectEdges(), fixInterBBAntiEdges(), DataDependenceGraphBuilder::processRegUse(), RegisterRenamer::updateAntiEdgesFromLRTo(), updateRegUse(), and updateRegWrite().

Here is the call graph for this function:

◆ copyDependencies()

void DataDependenceGraph::copyDependencies	(	const MoveNode &	src,
		MoveNode &	dst,
		bool	ignoreSameBBBackedges,
		bool	moveOverLoopEdge = `true`
	)

Copies all dependencies going to and from a movenode to another

Creates copy of all edges going to and from an movenode and make them to point to and fro another movenode.

Parameters

src	movenode to copy dependencies from
dst	movenode to copy dependencies to

Todo:: should this method be in base class? would require graphedge.clone()

Definition at line 3816 of file DataDependenceGraph.cc.

                           {
    // performance optimization 
    NodeDescriptor nd = descriptor(src);
 
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    std::pair<InEdgeIter, InEdgeIter> iEdges =
        boost::in_edges(nd, graph_);
 
    for (InEdgeIter ii = iEdges.first; ii != iEdges.second; ii++) {
        EdgeDescriptor ed = *ii;
        DataDependenceEdge* edge = graph_[ed];
        MoveNode* tail = graph_[boost::source(ed, graph_)];
        if (ignoreSameBBBackedges && edge->isBackEdge() &&
            &getBasicBlockNode(src) == &getBasicBlockNode(*tail)) {
            continue;
        }
        DataDependenceEdge* newEdge = new DataDependenceEdge(
            *edge, (moveOverLoopEdge && tail != &src && tail != &dst));
        connectNodes(*tail, dst, *newEdge);
    }
 
    std::pair<OutEdgeIter, OutEdgeIter> oEdges =
        boost::out_edges(nd, graph_);
 
    for (OutEdgeIter oi = oEdges.first; oi != oEdges.second; oi++) {
        EdgeDescriptor ed = *oi;
        DataDependenceEdge* edge = graph_[ed];
        MoveNode* head = graph_[boost::target(ed, graph_)];
        if (ignoreSameBBBackedges && edge->isBackEdge() &&
            &getBasicBlockNode(src) == &getBasicBlockNode(*head)) {
            continue;
        }
        DataDependenceEdge* newEdge = new DataDependenceEdge(
            *edge, (moveOverLoopEdge && head != &src && head != &dst));
        connectNodes(dst, *head, *newEdge);
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), getBasicBlockNode(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and GraphEdge::isBackEdge().

Referenced by MoveNodeDuplicator::duplicateMoveNode(), and CopyingDelaySlotFiller::getMoveNode().

Here is the call graph for this function:

◆ copyDepsOver() [1/2]

DataDependenceGraph::EdgeSet DataDependenceGraph::copyDepsOver	(	MoveNode &	node,
		bool	anti,
		bool	raw
	)

Copies dependencies over the node, like when the node is being deleted.

Converts WaR + WaW to WaR and WaW + WaW to WaW.

Parameters

node	node whose in- and outgoing antideps are being combined/copied.

Definition at line 2422 of file DataDependenceGraph.cc.

                                                                     {
 
    EdgeSet createdEdges;
 
    DataDependenceGraph::NodeDescriptor nd = descriptor(node);
 
    EdgeSet iEdges = inEdges(node);
    EdgeSet oEdges = outEdges(node);
 
    // Loop thru all outedges.
    for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
        DataDependenceEdge& oEdge = **i;
        
        // Care about WaW edges. (WaW+Waw -> Waw, WaR+WaW->War)
        // Also raw edges (raw+raw -> raw)
        if ((oEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER
             || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA) && 
            (((oEdge.dependenceType() == DataDependenceEdge::DEP_WAW && anti)||
              (oEdge.dependenceType() == DataDependenceEdge::DEP_RAW && raw)))){
 
            // Then loop all incoming edges.
            for (EdgeSet::iterator j = iEdges.begin(); 
                 j != iEdges.end(); j++) {
                DataDependenceEdge& iEdge = **j;
                
                // if WAW and same register, copy edge
                if (iEdge.dependenceType() == oEdge.dependenceType() &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
                    
                    MoveNode& tail = tailNode(iEdge,nd);
                    MoveNode& head = headNode(oEdge,nd);
                    
                    if (!exclusingGuards(tail, head) ||
                        (oEdge.dependenceType() == 
                         DataDependenceEdge::DEP_RAW &&
                         oEdge.guardUse())) {
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse(), 
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        if (connectOrDeleteEdge(tail, head, edge)) {
                            createdEdges.insert(edge);
                        }
                    }
                }
 
                // if WAR and same register, and oedge was waw, copy edge.
                if (iEdge.dependenceType() == DataDependenceEdge::DEP_WAR &&
                    oEdge.dependenceType() == DataDependenceEdge::DEP_WAW &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
                    
                    MoveNode& tail = tailNode(iEdge,nd);
                    MoveNode& head = headNode(oEdge,nd);
                    
                    if (!exclusingGuards(tail, head) || iEdge.guardUse()) {
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse(), 
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        if (connectOrDeleteEdge(tail, head, edge)) {
                            createdEdges.insert(edge);
                        }
                    }
                }
            }
        }
    }
    return createdEdges;
}

Referenced by BUBasicBlockScheduler::bypassNode(), CycleLookBackSoftwareBypasser::bypassNode(), destRenamed(), mergeAndKeepSource(), BFDREEarly::operator()(), BFDRELate::operator()(), BFDRELoop::operator()(), BFPostpassDRE::operator()(), BFPostpassLoopDRE::operator()(), renamedSimpleLiveRange(), BasicBlockScheduler::tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), and PreOptimizer::tryToRemoveGuardInversingOp().

Here is the call graph for this function:

◆ copyDepsOver() [2/2]

void DataDependenceGraph::copyDepsOver	(	MoveNode &	node1,
		MoveNode &	node2,
		bool	anti,
		bool	raw
	)

Definition at line 2515 of file DataDependenceGraph.cc.

                                                           {
 
    DataDependenceGraph::NodeDescriptor nd1 = descriptor(node1);
    DataDependenceGraph::NodeDescriptor nd2 = descriptor(node2);
 
    EdgeSet iEdges1 = inEdges(node1);
    EdgeSet oEdges1 = outEdges(node1);
    EdgeSet iEdges2 = inEdges(node2);
    EdgeSet oEdges2 = outEdges(node2);
        
    // Loop through all outedges of last one
    for (EdgeSet::iterator i = oEdges2.begin(); i != oEdges2.end(); i++) {
        DataDependenceEdge& oEdge = **i;
 
        // only care about register edges
        if (!(oEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER
              || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA)) {
            continue;
        }
 
        // are we copying this type edges?
        if (!(((oEdge.dependenceType() == DataDependenceEdge::DEP_WAW||
                oEdge.dependenceType() == DataDependenceEdge::DEP_WAR) && anti) ||
              (oEdge.dependenceType() == DataDependenceEdge::DEP_RAW && raw))) {
            continue;
        }
 
        MoveNode& head = headNode(oEdge, nd2);
 
        if (oEdge.dependenceType() == DataDependenceEdge::DEP_RAW && raw) {
            // Then loop all incoming edges for raw deps
            for (EdgeSet::iterator j = iEdges1.begin(); 
                 j != iEdges1.end(); j++) {
                DataDependenceEdge& iEdge = **j;
                
                // RAW going over node.
                if (iEdge.dependenceType() == oEdge.dependenceType() &&
                    iEdge.dependenceType() == DataDependenceEdge::DEP_RAW &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
 
                    MoveNode& tail = tailNode(iEdge, nd1);
 
                    if (!exclusingGuards(tail, head) ||
                        (oEdge.dependenceType() == oEdge.guardUse())) {
 
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse() || oEdge.guardUse(),
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        connectOrDeleteEdge(tail, head, edge);
                    }
                }
            }
        }
         
        if (!anti) {
            continue;
        }
 
        if (oEdge.dependenceType() == DataDependenceEdge::DEP_WAW) {
            // Then loop all incoming edges for waw deps
            for (EdgeSet::iterator j = iEdges2.begin(); 
                 j != iEdges2.end(); j++) {
                DataDependenceEdge& iEdge = **j;
 
                // WAW going over node.
                if (iEdge.dependenceType() == oEdge.dependenceType() &&
                    iEdge.dependenceType() == DataDependenceEdge::DEP_WAW &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
 
                    MoveNode& tail = tailNode(iEdge);
 
                    if (!exclusingGuards(tail, head) && &tail != &node1) {
 
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse(), 
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        connectOrDeleteEdge(tail, head, edge);
                    }
                }
 
                // if WAR and same register, and oedge was waw, copy edge.
                if (iEdge.dependenceType() == DataDependenceEdge::DEP_WAR &&
                    oEdge.dependenceType() == DataDependenceEdge::DEP_WAW &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
                    
                    MoveNode& tail = tailNode(iEdge,nd2);
                    
                    if (!exclusingGuards(tail, head)) {
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse(), 
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        if (&tail == &head) {
                            std::cerr << "copydeps over copying edge same node(1)!" << tail.toString() << " edge:  " << edge->toString()
                                      << std::endl;
                        }
 
                        connectOrDeleteEdge(tail, head, edge);
                    }
                }
            }
        }
 
        // last one reads interesting register
        if (oEdge.dependenceType() == DataDependenceEdge::DEP_WAR) {
            for (EdgeSet::iterator j = iEdges1.begin(); 
                 j != iEdges1.end(); j++) {
                DataDependenceEdge& iEdge = **j;
                if ((iEdge.dependenceType() == DataDependenceEdge::DEP_WAR ||
                     iEdge.dependenceType() == DataDependenceEdge::DEP_WAW) &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
                    MoveNode& tail = tailNode(iEdge,nd2);
                    
                    if (!exclusingGuards(tail, head)) {
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse(), 
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        if (&tail == &head) {
                            std::cerr << "copydeps over copying edge same node(2)!" << tail.toString() << " edge:  " << edge->toString()
                                      << std::endl;
                        }
                        connectOrDeleteEdge(tail, head, edge);
                    }
                }
            }
        }
    }
 
    if (!anti) {
        return;
    }
 
    // copy WARs over.
    for (EdgeSet::iterator i = oEdges1.begin(); i != oEdges1.end(); i++) {
        DataDependenceEdge& oEdge = **i;
 
        // only care about register edges
        if (!(oEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER
              || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA)) {
            continue;
        }
 
        if (oEdge.dependenceType() == DataDependenceEdge::DEP_WAR) {
 
            MoveNode& head = headNode(oEdge,nd1);
            if (&head == &node2) {
                continue;
            }
 
            // Then loop all incoming edges for waw deps
            for (EdgeSet::iterator j = iEdges2.begin(); 
                 j != iEdges2.end(); j++) {
                DataDependenceEdge& iEdge = **j;
 
                // WAW going over node.
                if (iEdge.dependenceType() == DataDependenceEdge::DEP_WAR &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
 
                    MoveNode& tail = tailNode(iEdge,nd2);
                    if (!exclusingGuards(tail, head) && &tail != &node1) {
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse(), 
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        connectOrDeleteEdge(tail, head, edge);
                    }
                }
            }
        }
        if (oEdge.dependenceType() == DataDependenceEdge::DEP_WAW) {
            MoveNode& head = headNode(oEdge,nd1);
            if (&head == &node2) {
                continue;
            }
 
            for (EdgeSet::iterator j = iEdges1.begin(); 
                 j != iEdges1.end(); j++) {
                DataDependenceEdge& iEdge = **j;
                if ((iEdge.dependenceType() == DataDependenceEdge::DEP_WAR ||
                     iEdge.dependenceType() == DataDependenceEdge::DEP_WAW) &&
                    (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                    iEdge.data() == oEdge.data()) {
                    MoveNode& tail = tailNode(iEdge,nd2);
                    
                    if (!exclusingGuards(tail, head)) {
                        // create new edge
                        // same other properties but sum loop depth
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                iEdge.edgeReason(),
                                iEdge.dependenceType(),
                                iEdge.data(),
                                iEdge.guardUse(), 
                                false, 
                                iEdge.tailPseudo(),
                                oEdge.headPseudo(),
                                iEdge.loopDepth() + oEdge.loopDepth());
                        
                        connectOrDeleteEdge(tail, head, edge);
                    }
                }
            }
        }
    }
}

Here is the call graph for this function:

◆ copyExternalInEdges()

void DataDependenceGraph::copyExternalInEdges	(	MoveNode &	nodeCopy,
		const MoveNode &	source
	)

Copies incoming edges which come from nodes on other BB's to a node into another node. If an edge comes from inside same BB, does not copy.

Parameters

source	node containing original incoming edges.
nodeCopy	node where to copy the inedges to.

Definition at line 5323 of file DataDependenceGraph.cc.

                                                {
    const BasicBlockNode* origBB = &getBasicBlockNode(source);
    
    EdgeSet edges = inEdges(source);
    for (EdgeSet::iterator i = edges.begin(); i != edges.end(); i++) {
        Edge& edge = **i;
        MoveNode& tail = tailNode(edge);
        if (&getBasicBlockNode(tail) != origBB) {
            DataDependenceEdge* newEdge = new DataDependenceEdge(edge);
            connectNodes(tail, nodeCopy, *newEdge);
        }
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), getBasicBlockNode(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by LoopPrologAndEpilogBuilder::build().

Here is the call graph for this function:

◆ copyExternalOutEdges()

void DataDependenceGraph::copyExternalOutEdges	(	MoveNode &	nodeCopy,
		const MoveNode &	source
	)

Copies outgoing edges which goes from a node to nodes in other BB's into another node. If an edge goes to a node inside same BB, does not copy.

Parameters

source	node containing original outgoingcoming edges.
nodeCopy	node where to copy the outedges to.

Definition at line 5346 of file DataDependenceGraph.cc.

                                                {
    const BasicBlockNode* origBB = &getBasicBlockNode(source);
    
    EdgeSet edges = outEdges(source);
    for (EdgeSet::iterator i = edges.begin(); i != edges.end(); i++) {
        Edge& edge = **i;
        MoveNode& head = headNode(edge);
        if (&getBasicBlockNode(head) != origBB) {
            DataDependenceEdge* newEdge = new DataDependenceEdge(edge);
            connectNodes(nodeCopy, head, *newEdge);
        }
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), getBasicBlockNode(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().

Referenced by LoopPrologAndEpilogBuilder::build().

Here is the call graph for this function:

◆ copyIncomingGuardEdges()

void DataDependenceGraph::copyIncomingGuardEdges	(	const MoveNode &	src,
		MoveNode &	dst
	)

Copies all incoming guard dependencies going to a movenode to another

Parameters

src	movenode to copy dependencies from
dst	movenode to copy dependencies to

Definition at line 3865 of file DataDependenceGraph.cc.

                                        {
 
    // performance optimization 
    NodeDescriptor nd = descriptor(src);
 
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    std::pair<InEdgeIter, InEdgeIter> iEdges =
        boost::in_edges(nd, graph_);
 
    for (InEdgeIter ii = iEdges.first; ii != iEdges.second; ii++) {
        EdgeDescriptor ed = *ii;
        DataDependenceEdge* edge = graph_[ed];
        if (edge->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge->dependenceType() == DataDependenceEdge::DEP_RAW &&
            edge->guardUse()) {
            DataDependenceEdge* newEdge = new DataDependenceEdge(*edge);
            MoveNode& tail = *graph_[boost::source(ed, graph_)];
            connectNodes(tail, dst, *newEdge);
        }
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, and BoostGraph< MoveNode, DataDependenceEdge >::graph_.

Referenced by CopyingDelaySlotFiller::collectMoves(), BasicBlockScheduler::tryToOptimizeWaw(), and BUBasicBlockScheduler::tryToOptimizeWaw().

Here is the call graph for this function:

◆ copyIncomingRawEdges()

void DataDependenceGraph::copyIncomingRawEdges	(	const MoveNode &	src,
		MoveNode &	dst
	)

Definition at line 5770 of file DataDependenceGraph.cc.

                                                                                 {
 
    // performance optimization 
    NodeDescriptor nd = descriptor(src);
 
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    std::pair<InEdgeIter, InEdgeIter> iEdges =
        boost::in_edges(nd, graph_);
 
    for (InEdgeIter ii = iEdges.first; ii != iEdges.second; ii++) {
        EdgeDescriptor ed = *ii;
        DataDependenceEdge* edge = graph_[ed];
        if ((edge->edgeReason() == DataDependenceEdge::EDGE_REGISTER 
             || edge->edgeReason() == DataDependenceEdge::EDGE_RA) &&
            edge->dependenceType() == DataDependenceEdge::DEP_RAW &&
            !edge->guardUse()) {
            DataDependenceEdge* newEdge = new DataDependenceEdge(*edge);
            MoveNode& tail = *graph_[boost::source(ed, graph_)];
            connectNodes(tail, dst, *newEdge);
        }
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, and BoostGraph< MoveNode, DataDependenceEdge >::graph_.

Here is the call graph for this function:

◆ copyOutgoingGuardWarEdges()

void DataDependenceGraph::copyOutgoingGuardWarEdges	(	const MoveNode &	src,
		MoveNode &	dst
	)

Copies all outgoing guard war dependencies going to a movenode to another

Parameters

src	movenode to copy dependencies from
dst	movenode to copy dependencies to

Definition at line 3897 of file DataDependenceGraph.cc.

                                        {
 
    // performance optimization 
    NodeDescriptor nd = descriptor(src);
 
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    std::pair<OutEdgeIter, OutEdgeIter> oEdges =
        boost::out_edges(nd, graph_);
 
    for (OutEdgeIter oi = oEdges.first; oi != oEdges.second; oi++) {
        EdgeDescriptor ed = *oi;
        DataDependenceEdge* edge = graph_[ed];
        if (edge->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge->dependenceType() == DataDependenceEdge::DEP_WAR &&
            edge->guardUse()) {
            DataDependenceEdge* newEdge = new DataDependenceEdge(*edge);
            MoveNode& head = *graph_[boost::target(ed, graph_)];
            connectNodes(dst, head, *newEdge);
        }
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::DEP_WAR, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, and BoostGraph< MoveNode, DataDependenceEdge >::graph_.

Referenced by BasicBlockScheduler::tryToOptimizeWaw(), and BUBasicBlockScheduler::tryToOptimizeWaw().

Here is the call graph for this function:

◆ createRegisterAntiDependenciesBetweenNodes()

void DataDependenceGraph::createRegisterAntiDependenciesBetweenNodes ( DataDependenceGraph::NodeSet & nodes )

Creates antidependencies between certains nodes of a ddg.

This is used after regcopyadded to insert antideps between the temp registers added by the regcopyadder.

All nodes given to the method should be scheduled. The nodes should have already been added to the graph.

Parameters

nodes nodes whose antidependencies to add.

Definition at line 4381 of file DataDependenceGraph.cc.

                                       {
    
    typedef std::map<int, NodeSet > 
        MovesByCycles;
    MovesByCycles movesInCycles;
    typedef std::map<TCEString, NodeSet> NodeSetMap;
    
    NodeSetMap reads;
    NodeSetMap writes;
    // insert all moves int correct cycle in bookkeeping
    for (NodeSet::iterator nsIter = nodes.begin(); 
         nsIter != nodes.end(); nsIter++) {
        MoveNode* mn = *nsIter;
        assert(mn->isPlaced());
        movesInCycles[mn->cycle()].insert(mn);
    }
 
    // loop thru all cycles
    for (MovesByCycles::iterator i = movesInCycles.begin(); 
         i != movesInCycles.end(); i++) {
        
        NodeSet& nodesInCycle = i->second;
        // then check sources of all nodes in the cycle
        for (NodeSet::iterator j = nodesInCycle.begin();
             j != nodesInCycle.end(); j++) {
            MoveNode* mn = *j;
            TTAProgram::Move& move = mn->move();
            TTAProgram::Terminal& src = move.source();
            if (src.isGPR()) {
                TCEString reg = DisassemblyRegister::registerName(src);
                reads[reg].insert(mn);
            }
        }
 
        // then check destinations of all nodes in the cycle
        for (NodeSet::iterator j = nodesInCycle.begin();
             j != nodesInCycle.end(); j++) {
 
            MoveNode* mn = *j;
            TTAProgram::Move& move = mn->move();
            TTAProgram::Terminal& dst = move.destination();
            if (dst.isGPR()) {
                TCEString reg = DisassemblyRegister::registerName(dst);
 
                NodeSet& readsFromReg = reads[reg];
                NodeSet& writesToReg = writes[reg];
                
                // create the dependencies.
                // WaRs
                for (NodeSet::iterator k = readsFromReg.begin(); 
                     k != readsFromReg.end(); k++) {
                    MoveNode& prevMN = **k;
                    if (!exclusingGuards(prevMN, *mn)) {
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                DataDependenceEdge::EDGE_REGISTER,
                                DataDependenceEdge::DEP_WAR, reg);
                        connectOrDeleteEdge(**k, *mn, edge);
                    }
                }
 
                // WaWs.
                for (NodeSet::iterator k = writesToReg.begin(); 
                     k != writesToReg.end(); k++) {
                    MoveNode& prevMN = **k;
                    if (!exclusingGuards(prevMN, *mn)) {
                        DataDependenceEdge* edge = 
                            new DataDependenceEdge(
                                DataDependenceEdge::EDGE_REGISTER,
                                DataDependenceEdge::DEP_WAW, reg);
                        connectOrDeleteEdge(**k, *mn, edge);
                    }
                }
 
                // if this is unconditional, kills previous writes to the reg
                if (move.isUnconditional()) {
                    writes[reg].clear();
                    reads[reg].clear();
                }
                writes[reg].insert(mn);
            }
        }
    }
}

References assert, connectOrDeleteEdge(), MoveNode::cycle(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, exclusingGuards(), TTAProgram::Terminal::isGPR(), MoveNode::isPlaced(), TTAProgram::Move::isUnconditional(), MoveNode::move(), DisassemblyRegister::registerName(), and TTAProgram::Move::source().

Referenced by RegisterCopyAdder::operandsScheduled(), and RegisterCopyAdder::resultsScheduled().

Here is the call graph for this function:

◆ createSubgraph() [1/3]

DataDependenceGraph * DataDependenceGraph::createSubgraph	(	NodeSet &	nodes,
		bool	includeLoops = `false`
	)

Creates a subgraph of a ddg from set of cede snippets which contains instructions which contains moves in this graph.

Parameters

nodes	code being included in the subgraph
includeLoops	whether to include loop-carried dependencies

Returns: the created subgraph

Definition at line 3377 of file DataDependenceGraph.cc.

                                       {
    DataDependenceGraph* subGraph = 
        new DataDependenceGraph(
            allParamRegs_, "", registerAntidependenceLevel_, NULL, false,
            !includeLoops);
 
    if (machine_ != NULL) {
        subGraph->setMachine(*machine_);
    }
 
    constructSubGraph(*subGraph, nodes);
 
    typedef std::set<ProgramOperationPtr, ProgramOperationPtrComparator> POSet;
    POSet subgraphPOs;
 
    // copy the node -> bbn mapping.
    // also find POs to copy.
    for (int i = 0, nc = subGraph->nodeCount(); i < nc; i++) {
        MoveNode& mn = subGraph->node(i);
        BasicBlockNode* bbn = moveNodeBlocks_[&mn];
        subGraph->moveNodeBlocks_[&mn] = bbn;
        if (mn.isSourceOperation()) {
            subgraphPOs.insert(mn.sourceOperationPtr());
        }
        
        if (mn.isDestinationOperation()) {
            subgraphPOs.insert(mn.destinationOperationPtr());
        }
    }
    for (auto i: subgraphPOs) {
        subGraph->programOperations_.push_back(i);
    }
    return subGraph;
}

References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), MoveNode::destinationOperationPtr(), MoveNode::isDestinationOperation(), MoveNode::isSourceOperation(), machine_, moveNodeBlocks_, BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), programOperations_, registerAntidependenceLevel_, setMachine(), and MoveNode::sourceOperationPtr().

Referenced by BUMoveNodeSelector::BUMoveNodeSelector(), BBSchedulerController::createDDGFromBB(), createSubgraph(), createSubgraph(), and CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector().

Here is the call graph for this function:

◆ createSubgraph() [2/3]

DataDependenceGraph * DataDependenceGraph::createSubgraph	(	std::list< TTAProgram::CodeSnippet * > &	codeSnippets,
		bool	includeLoops = `false`
	)

Creates a subgraph of a ddg from set of cede snippets which contains instructions which contains moves in this graph.

Parameters

codeSnippets	code being included in the subgraph
includeLoops	whether to include loop-carried dependencies

Returns: the created subgraph

Definition at line 3563 of file DataDependenceGraph.cc.

                                                                      {
    NodeSet moveNodes;
 
    int nc = nodeCount();
    for (int i = 0; i < nc; i++) {
        MoveNode& mn = node(i,false);
        if (mn.isMove()) {
            TTAProgram::Move& move = mn.move();
            TTAProgram::Instruction& parentIns = move.parent();
            if (parentIns.isInProcedure()) { // is in code snippet
                for (std::list<TTAProgram::CodeSnippet*>::iterator iter = 
                         codeSnippets.begin(); 
                     iter != codeSnippets.end(); iter++) {
                    TTAProgram::CodeSnippet& cs = **iter;
                    if (&move.parent().parent() == &cs) {
                        moveNodes.insert(&mn);
                    }
                }
            } 
        }
    }
    return createSubgraph(moveNodes, includeLoops);
}

References createSubgraph(), TTAProgram::Instruction::isInProcedure(), MoveNode::isMove(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Instruction::parent(), and TTAProgram::Move::parent().

Here is the call graph for this function:

◆ createSubgraph() [3/3]

DataDependenceGraph * DataDependenceGraph::createSubgraph	(	TTAProgram::CodeSnippet &	cs,
		bool	includeLoops = `false`
	)

Creates a subgraph of a ddg from set of cede snippets which contains instructions which contains moves in this graph.

Parameters

cs	code being included in the subgraph
includeLoops	whether to include loop-carried dependencies

Returns: the created subgraph

Definition at line 3532 of file DataDependenceGraph.cc.

                                                   {
    NodeSet moveNodes;
    int nc = nodeCount();
    for (int i = 0; i < nc; i++) {
        MoveNode& mn = node(i,false);
        if (mn.isMove()) {
            TTAProgram::Move& move = mn.move();
            if (move.isInInstruction()) {
                TTAProgram::Instruction& parentIns = move.parent();
                if (parentIns.isInProcedure()) { // is in code snippet
                    if (&parentIns.parent() == &cs) {
                        moveNodes.insert(&mn);
                    }
                }
            } 
        }
    }
    return createSubgraph(moveNodes, includeLoops);
}

References createSubgraph(), TTAProgram::Move::isInInstruction(), TTAProgram::Instruction::isInProcedure(), MoveNode::isMove(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Instruction::parent(), and TTAProgram::Move::parent().

Here is the call graph for this function:

◆ criticalPathGraph()

DataDependenceGraph * DataDependenceGraph::criticalPathGraph ( )

Returns a version of the graph with only nodes that are in the critical path.

Definition at line 3458 of file DataDependenceGraph.cc.

                                       {
    DataDependenceGraph* subGraph = 
        new DataDependenceGraph(
            allParamRegs_, "critical path DDG",
            registerAntidependenceLevel_, NULL, false, false);
 
    if (machine_ != NULL)
        subGraph->setMachine(*machine_);
    
    NodeSet nodes;
    for (int i = 0; i < nodeCount(); ++i) {
        if (isInCriticalPath(node(i)))
            nodes.insert(&node(i));
    }
    constructSubGraph(*subGraph, nodes);
 
    return subGraph;
}

References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), BoostGraph< MoveNode, DataDependenceEdge >::isInCriticalPath(), machine_, BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), registerAntidependenceLevel_, and setMachine().

Referenced by ResourceConstraintAnalyzer::analyze(), and BasicBlockScheduler::ddgSnapshot().

Here is the call graph for this function:

◆ deleteNode()

void DataDependenceGraph::deleteNode ( MoveNode & node )

Removes a MoveNode from a graph and deletes it.

Parameters

node	MoveNode being deleted.

Definition at line 2882 of file DataDependenceGraph.cc.

                                              {
    removeNode(node);
    delete &node;
}

References BoostGraph< MoveNode, DataDependenceEdge >::node(), and removeNode().

Referenced by PreOptimizer::tryToPrecalcConstantAdd(), and PreOptimizer::tryToRemoveGuardInversingOp().

Here is the call graph for this function:

◆ destRenamed()

DataDependenceGraph::UndoData DataDependenceGraph::destRenamed ( MoveNode & mn )

Destination of a move is renamed to a register which is not used in this ddg. Removes old edges not needed anymore and updates some edges. Assumes all the RAW successors of this node are also udpated to read thr new register.

Definition at line 5055 of file DataDependenceGraph.cc.

                                             {
 
    UndoData undoData;
    undoData.newEdges = copyDepsOver(mn, true, false);
 
    TTAProgram::Terminal& term = mn.move().destination();
    const TCEString newReg = DisassemblyRegister::registerName(term);
 
    for (int i = 0 ; i < inDegree(mn); i++) {
        DataDependenceEdge& iEdge = inEdge(mn,i);
        MoveNode& tail = tailNode(iEdge);
 
        // WAR's
        if (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
             iEdge.dependenceType() == DataDependenceEdge::DEP_WAW && 
            !iEdge.headPseudo()) {
 
            TTAProgram::Terminal& writeTerm = tail.move().destination();
 
            // if this edge disappers because of the renaming?
            if (iEdge.tailPseudo() ||
                (writeTerm.isGPR() && (
                     writeTerm.index() != term.index() ||
                     &writeTerm.registerFile() != &term.registerFile()))) {
                undoData.removedEdges.insert(RemovedEdgeDatum(tail, mn, iEdge));
                removeEdge(iEdge, NULL, &mn);
                i--; // don't skip one edge here!
            } else {
                // update the edge. also other end changed
                undoData.changedDataEdges[&iEdge] = iEdge.data();
                iEdge.setData(newReg);
            }
        }
 
        if (iEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            iEdge.dependenceType() == DataDependenceEdge::DEP_WAR &&
            !iEdge.headPseudo()) {
            
            bool removeE = false;
            if (iEdge.tailPseudo()) {
                removeE = true;
                continue;
            }
 
            if (!iEdge.guardUse()) {
                TTAProgram::Terminal& readTerm = tail.move().source();
                if (readTerm.isGPR() && (
                        readTerm.index() != term.index() ||
                        &readTerm.registerFile() != &term.registerFile())) {
                    removeE = true;
                }
            }
            
            if (iEdge.guardUse()) {
                if (tail.move().isUnconditional()) {
                    removeE = true;
/* something is wrong. but ignore it for now
                    std::cerr << "failing node: " << mn.toString() << std::endl;
                    std::cerr << "failinf tail: " << tail.toString() << std::endl;
                    std::cerr << "EDGE: " << iEdge.toString() << std::endl;
                    writeToDotFile("uncond_gu_war.dot");
*/
 
                } else {
                    const TTAMachine::RegisterGuard* rg =
                        dynamic_cast<const TTAMachine::RegisterGuard*>(
                            &tail.move().guard().guard());
                    if (rg->registerFile() != &term.registerFile() ||
                        rg->registerIndex() != term.index()) {
                        removeE = true;
                    }
                }
            }
            // if this edge disappers because of the renaming?
            if (removeE) {
                undoData.removedEdges.insert(RemovedEdgeDatum(tail, mn, iEdge));
                removeEdge(iEdge, NULL, &mn);
                i--; // don't skip one edge here!
            } else {
                // update the edge. also other end changed
                undoData.changedDataEdges[&iEdge] = iEdge.data();
                iEdge.setData(newReg);
            }
        }
    }
 
    for (int i = 0; i < outDegree(mn); i++) {
        DataDependenceEdge& edge = outEdge(mn,i);
 
        if (edge.edgeReason() != DataDependenceEdge::EDGE_REGISTER) {
            continue;
        }
 
        if (edge.dependenceType() == DataDependenceEdge::DEP_RAW &&
            !edge.tailPseudo()) {
            // update the data!
            edge.setData(newReg);
 
        } else {
            if (edge.dependenceType() == DataDependenceEdge::DEP_WAW) {
                MoveNode& head = headNode(edge);
                TTAProgram::Terminal& writeTerm = head.move().destination();
 
                // if this edge disappers because of the renaming?
                if (edge.tailPseudo()) {
                    continue;
                }
                if (edge.headPseudo() ||
                    (writeTerm.isGPR() && (
                         writeTerm.index() != term.index() ||
                         &writeTerm.registerFile() != &term.registerFile()))){
                     undoData.removedEdges.insert(
                         RemovedEdgeDatum(mn, head, edge));
                    removeEdge(edge, &mn, NULL);
                    i--;
                } else {
                    // update the edge. also other end changed
                    undoData.changedDataEdges[&edge] = edge.data();
                    edge.setData(newReg);
                }
            }
        }
    }
    return undoData;
}

Referenced by BFRenameLiveRange::renameLiveRange(), and RegisterRenamer::renameLiveRange().

Here is the call graph for this function:

◆ dotString()

TCEString DataDependenceGraph::dotString ( ) const

virtual

Dot printing related methods.

Returns the graph as a string formatted in GraphViz Dot format.

This version is able to order the nodes according to their cycles to make the output more readable.

Returns: Graph represented as a Dot string.

Reimplemented from GraphBase< GraphNode, GraphEdge >.

Definition at line 1562 of file DataDependenceGraph.cc.

                                     {
 
    // TODO group based on both BB and cycle
    std::ostringstream s;
    s << "digraph " << name() << " {" << std::endl;
    
    if (cycleGrouping_ && !procedureDDG_ && !dotProgramOperationNodes_) {
        // print the "time line"
        s << "\t{" << std::endl
          << "\t\tnode [shape=plaintext];" << std::endl
          << "\t\t";
        const int smallest = smallestCycle();
        const int largest = largestCycle();
        for (int c = smallest; c <= largest; ++c) {
            s << "\"cycle " << c << "\" -> ";
        }
        s << "\"cycle " << largest + 1 << "\"; " 
          << std::endl << "\t}" << std::endl;
    
        // print the nodes that have cycles
        for (int c = smallest; c <= largest; ++c) {
            NodeSet moves = movesAtCycle(c);
            if (moves.size() > 0) {
                s << "\t{ rank = same; \"cycle " << c << "\"; ";
                for (NodeSet::iterator i = moves.begin(); 
                     i != moves.end(); ++i) {
                    Node& n = **i;        
                    s << "n" << n.nodeID() << "; ";
                }
                s << "}" << std::endl;
            }        
        }
    }
 
    // print all the nodes and their properties
    for (int i = 0; i < nodeCount(); ++i) {
        Node& n = node(i);
 
        // in PONode mode, print the node for a single move only if
        // it doesn't belong to an operation
        if (dotProgramOperationNodes_ && n.isOperationMove()) 
            continue;
 
        TCEString nodeStr(n.dotString());
        if (false && isInCriticalPath(n)) {
            // convert critical path node shapes to invtriangle to make
            // the path stand out in the graph, this slows down the
            // printout probably quite a bit, TODO: optimize by caching
            // critical path data
            nodeStr.replaceString("shape=box", "shape=invtriangle");
            nodeStr.replaceString("shape=ellipse", "shape=invtriangle");
        }
        s << "\tn" << n.nodeID() << " [" << nodeStr << "]; " << std::endl;
    }
 
    typedef std::set<ProgramOperation*> POSet;
    POSet programOps;
 
    // edges. optimized low-level routines.
    typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::edges(graph_);
    for (EdgeIter i = edges.first; i != edges.second; i++) {
        EdgeDescriptor ed = *i;
        Edge& e = *graph_[ed];
        Node& tail = *graph_[boost::source(ed, graph_)];
        Node& head = *graph_[boost::target(ed, graph_)];
 
        TCEString tailNodeId;
        TCEString headNodeId;
 
        if (dotProgramOperationNodes_ && tail.isOperationMove()) {
            if (tail.isSourceOperation()) {
                tailNodeId << "po" << tail.sourceOperation().poId();
                programOps.insert(&tail.sourceOperation());
            } else {
                tailNodeId << "po" << tail.destinationOperation().poId();
                programOps.insert(&tail.destinationOperation());
            }
        } else {
            tailNodeId << "n" << tail.nodeID();
        }
 
        if (dotProgramOperationNodes_ && head.isOperationMove()) {
            if (head.isSourceOperation()) {
                headNodeId << "po" << head.sourceOperation().poId();
                programOps.insert(&head.sourceOperation());
            } else {
                headNodeId << "po" << head.destinationOperation().poId();
                programOps.insert(&head.destinationOperation());
            }
        } else {
            headNodeId << "n" << head.nodeID();
        }
        
        if (tailNodeId == headNodeId) continue;
 
        float weight = 1.0f;
        s << "\t" << tailNodeId
          << " -> " << headNodeId << "[";
 
        if (e.isFalseDep()) {
            weight = 0.3f;
            s << "color=\"red\", ";
        }
 
        if (e.isBackEdge()) {
            s << "constraint=false,";
            weight = 0.1f;
        }
 
        if (e.edgeReason() == DataDependenceEdge::EDGE_OPERATION) {
            weight = 10.0f;
        }
 
        if (e.edgeReason() == DataDependenceEdge::EDGE_MEMORY && !e.certainAlias()) {
            weight /= 2.0f;
        }
 
        s << "label=\""
          << e.toString(tail) 
          << "\",weight=" << weight << "];" << std::endl;    
    }
 
    // implicit operand to trigger edges
    for (int i = 0; i < nodeCount() && !dotProgramOperationNodes_; ++i) {
        Node& n = node(i);
        if (n.isMove() && n.move().isTriggering() &&
            n.isDestinationOperation()) {
            ProgramOperation &dst = n.destinationOperation();
            for (int j = 0; j < dst.inputMoveCount(); ++j) {
                if (dst.inputMove(j).nodeID() != n.nodeID()) {
                    s << "\tn" << dst.inputMove(j).nodeID()
                    << " -> n" << n.nodeID() << "["
                    << "label=\"T\", weight=10.0" << "];" << std::endl;
                }
            }
        }
    }
 
    if (dotProgramOperationNodes_) {
        for (POSet::iterator i = programOps.begin(); 
             i != programOps.end(); ++i) {
            const ProgramOperation& po = **i;
            TCEString label;
 
            int lineNo = -1;
 
            for (int i = 0; i < po.inputMoveCount(); ++i) {
                label += po.inputMove(i).toString() + "\\n";
                if (po.inputMove(i).move().hasSourceLineNumber())
                    lineNo = po.inputMove(i).move().sourceLineNumber();
            }
            label += "\\n";
            for (int i = 0; i < po.outputMoveCount(); ++i) {
                label += po.outputMove(i).toString() + "\\n";
            }
 
            if (lineNo != -1)
                label << "src line: " << lineNo << "\\n";
 
            s << "\tpo" << po.poId() << " [label=\"" 
              << label << "\",shape=box];" << std::endl;
        }
    }
 
    s << "}" << std::endl;   
 
    return s.str();    
}

References DataDependenceEdge::certainAlias(), cycleGrouping_, MoveNode::destinationOperation(), dotProgramOperationNodes_, MoveNode::dotString(), DataDependenceEdge::EDGE_MEMORY, DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, TTAProgram::Move::hasSourceLineNumber(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), DataDependenceEdge::isBackEdge(), MoveNode::isDestinationOperation(), DataDependenceEdge::isFalseDep(), BoostGraph< MoveNode, DataDependenceEdge >::isInCriticalPath(), MoveNode::isMove(), MoveNode::isOperationMove(), MoveNode::isSourceOperation(), TTAProgram::Move::isTriggering(), largestCycle(), MoveNode::move(), movesAtCycle(), BoostGraph< MoveNode, DataDependenceEdge >::name(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), GraphNode::nodeID(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), ProgramOperation::poId(), procedureDDG_, TCEString::replaceString(), smallestCycle(), TTAProgram::Move::sourceLineNumber(), MoveNode::sourceOperation(), DataDependenceEdge::toString(), and MoveNode::toString().

Here is the call graph for this function:

◆ dropBackEdges()

void DataDependenceGraph::dropBackEdges ( )

Drops loop edges from a sub-DDG.

This works only with simple control structures; Only works for edges marked as loop edges. Currently loop edges spanning over multiple basic blocks may be missing.

Definition at line 3620 of file DataDependenceGraph.cc.

                                        {
    const int nc = nodeCount();
 
    // first loop thru all nodes.
    for (int n = 0; n < nc; n++) {
        NodeDescriptor nd = boost::vertex(n, graph_);
 
        // the thru all output edges of the node.
        // this is propably the fastest way to iterate over 
        // all edges of a graph. (or is just all edges faster?)
        std::pair<OutEdgeIter, OutEdgeIter> edges = 
            boost::out_edges(nd, graph_);
 
        for (OutEdgeIter ei = edges.first; ei != edges.second;) {
            DataDependenceEdge* e = graph_[(*ei)];
            if (e->isBackEdge()) {
                // remove from internal bookkeeping
                boost::remove_edge(*ei, graph_);
 
                // iterators must be resetted when deleted something.
                edges = boost::out_edges(nd, graph_);
                ei = edges.first;
 
                // remove from edge descriptor cache
                DataDependenceGraph::EdgeDescMap::iterator
                    edIter = edgeDescriptors_.find(e);
                if (edIter != edgeDescriptors_.end()) {
                    edgeDescriptors_.erase(edIter);
                }
 
                for (unsigned int i = 0; i < childGraphs_.size(); i++) {
                    childGraphs_.at(i)->dropEdge(*e);
                }    
            } else {
                ei++;
            }
        }
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::childGraphs_, BoostGraph< MoveNode, DataDependenceEdge >::edgeDescriptors_, BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::isBackEdge(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().

Here is the call graph for this function:

◆ dropProgramOperation()

void DataDependenceGraph::dropProgramOperation ( ProgramOperationPtr po )

Drops a program operation to the graph, but not its parent graphs.

Parameters

po	ProgramOperation being added.

Definition at line 361 of file DataDependenceGraph.cc.

                                                                {
    for (auto i = programOperations_.begin(); 
         i != programOperations_.end();i++) {
        if (*i == po) {
            programOperations_.erase(i);
            return;
        }
    }
}

References programOperations_.

Referenced by BFRemoveLoopChecksAndJump::operator()().

◆ earliestCycle()

int DataDependenceGraph::earliestCycle	(	const MoveNode &	moveNode,
		unsigned int	ii = `UINT_MAX`,
		bool	ignoreRegWaRs = `false`,
		bool	ignoreRegWaWs = `false`,
		bool	ignoreGuards = `false`,
		bool	ignoreFuDeps = `false`,
		bool	ignoreSameOperationEdges = `false`,
		bool	assumeBypassing = `false`
	)		const

Returns the earliest cycle this move can be scheduled at given the cycles of the dependencies.

Checks all the parent nodes of the move in the DDG and finds their max cycle if they are scheduled, if none found, 0 is returned, if at least one of the preceeding nodes is unscheduled, returns INT_MAX.

Parameters

moveNode	The move node for which to find the earliest cycle.
assumeBypassing	If the preceeding MoveNodes are register writes, assume a reading MoveNode will be able to bypass from the source to save a cycle.

Returns: The earliest cycle the move can be scheduled to according to data dependencies, INT_MAX if unknown.

Todo:: clean this up: should be the same code as the edgeWeight when EWH_REAL is used.

Definition at line 388 of file DataDependenceGraph.cc.

                                                               {
 
    if (machine_ == NULL) {
        throw InvalidData(__FILE__,__LINE__,__func__,
                          " setMachine() must be called before this");
    }
    const EdgeSet edges = inEdges(moveNode);
    int minCycle = 0;
    for (EdgeSet::const_iterator i = edges.begin(); i != edges.end(); ++i) {
        DataDependenceEdge& edge = **i;
 
        if (ignoreGuards && edge.guardUse()) {
            continue;
        }
 
        if (ignoreFuDeps && 
            (edge.edgeReason() == DataDependenceEdge::EDGE_FUSTATE ||
             edge.edgeReason() == DataDependenceEdge::EDGE_MEMORY)) {
            continue;
        }
        
        if (ignoreSameOperationEdges && 
            edge.edgeReason() == DataDependenceEdge::EDGE_OPERATION) {
            continue;
        }
 
        MoveNode& tail = tailNode(edge);
        if (&tail == &moveNode) {
            continue;
        }
 
        if (ignoreSameOperationEdges && !edge.isBackEdge() &&
            moveNode.isSourceOperation() &&
            tail.isDestinationOperation() &&
            &moveNode.sourceOperation() == &tail.destinationOperation()) {
            continue;
        }
            
 
        if (tail.isPlaced()) {
            int effTailCycle = tail.cycle();
            
            // If call, make sure all incoming deps fit into delay slots,
            // can still be later than the call itself
            // dependence type does not matter.
            if (edge.headPseudo()) {
                effTailCycle -= delaySlots_;
            } else {
                /// @todo clean this up: should be the same code as the edgeWeight 
                /// when EWH_REAL is used.
                if (edge.edgeReason() == DataDependenceEdge::EDGE_OPERATION &&
                    moveNode.isSourceOperation() && tail.inSameOperation(moveNode)) {
                    effTailCycle += getOperationLatency(edge.data());
                } else if (edge.dependenceType() == DataDependenceEdge::DEP_WAW) {
 
                    // ignore reg antidep? then skip over this edge.
                    if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER
                        && !edge.headPseudo() && 
                        ignoreRegWaWs) {
                        continue;
                    }
                    // latency does not matter with WAW. always +1.
                    effTailCycle += 1;
                } else {
                    int latency;
                    if (assumeBypassing) {
                        latency = 0;
                    } else {
                        latency = 1;
                    }
                    if (edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
                        // ignore reg antidep? then skip over this edge.
                        if (edge.edgeReason() == 
                            DataDependenceEdge::EDGE_REGISTER && 
                            !edge.headPseudo() && ignoreRegWaRs) {
                            continue;
                        }
 
                        // WAR allows writing at same cycle than reading.
                        // in WAR also the latency goes backwards, 
                        // new value can
                        // be written before old is read is latency is big.
                        if (edge.guardUse()) {
                            latency = tail.guardLatency();
                        } 
 
                        // TODO: generate some hasAutomaticBundling()
                        // property to ADF
                        if (machine_->triggerInvalidatesResults()) {
                            latency = 0;
                        }
                        effTailCycle = effTailCycle - latency + 1;
                    } else {
                        // RAW
                        if (edge.guardUse()) {
                            latency = moveNode.guardLatency();
                        }
                        // in case of RAW, we have to wait latency cycles 
                        // before we can use the written value. 
                        effTailCycle += latency;
                    }
                }
            }
 
            assert ((ii != 0 || edge.loopDepth() ==0) && 
                    "ii should not be 0 if we have an loop edge");
 
            effTailCycle -= (ii * edge.loopDepth());
            minCycle = std::max(effTailCycle, minCycle);
        } 
    }
 
    // on architectures with hw data hazard detection this is needed.
    // TODO: now does this for all input moves, not just trigger
    if (machine_->triggerInvalidatesResults() &&
        moveNode.isDestinationOperation()) {
 
        ProgramOperation& po = moveNode.destinationOperation();
        MoveNode* trigger = po.triggeringMove();
        if (trigger == nullptr || trigger == &moveNode) {
            for (int i = 0; i < po.outputMoveCount(); i++) {
                MoveNode& outMove = po.outputMove(i);
                if (hasNode(outMove)) {
                    minCycle =
                        std::max(minCycle,
                                 earliestCycle(outMove, ii,
                                               ignoreRegWaRs,
                                               ignoreRegWaWs,
                                               ignoreGuards,
                                               true, // ignoreFuDeps
                                               true)); // operation edges ignored
                }
            }
        }
    }
    return minCycle;
}

Referenced by ResourceConstraintAnalyzer::analyzeMoveNode(), CycleLookBackSoftwareBypasser::bypass(), CycleLookBackSoftwareBypasser::bypassNode(), MoveNodeGroup::earliestCycle(), earliestCycle(), ResourceConstraintAnalyzer::findResourceConstrainedParent(), ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage(), BFPushAntidepDown::operator()(), BFPushMoveUp::operator()(), BFPushMoveUp2::operator()(), BFRescheduleSuccessorsClose::operator()(), BFScheduleBU::operator()(), BFScheduleExact::operator()(), BUBasicBlockScheduler::scheduleMove(), BasicBlockScheduler::scheduleMove(), BasicBlockScheduler::scheduleOperandWrites(), BasicBlockScheduler::tryToOptimizeWaw(), and BasicBlockScheduler::tryToSwitchInputs().

Here is the call graph for this function:

◆ edgeLatency()

int DataDependenceGraph::edgeLatency	(	const DataDependenceEdge &	edge,
		int	ii,
		const MoveNode *	tail,
		const MoveNode *	head
	)		const

Definition at line 311 of file DataDependenceGraph.cc.

                                                                 {
 
    int latency = 1;
    if (edge.edgeReason() == DataDependenceEdge::EDGE_OPERATION) {
        if (head == NULL) {
            head = &headNode(edge);
        }
        if (head->isSourceOperation()) {
            if (tail == NULL) {
                tail = &tailNode(edge);
            }
            if (tail->inSameOperation(*head)) {
                latency = getOperationLatency(edge.data());
            }
        }
    } else if (edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
        latency = 0;
    }
 
    if (edge.headPseudo()) {
        latency -= delaySlots_;
    }
 
    if (edge.tailPseudo()) {
        latency += delaySlots_;
    }
 
    if (edge.guardUse()) {
        if (edge.dependenceType() == DataDependenceEdge::DEP_RAW) {
            latency += (head->guardLatency()-1);
        } else {
            if (edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
                latency -= (tail->guardLatency()-1);
            } else {
                std::cerr << "invalid guard edge: " << edge.toString();
            }
        }
    }
    return latency - ii*edge.loopDepth();
}

References delaySlots_, DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, getOperationLatency(), MoveNode::guardLatency(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), MoveNode::inSameOperation(), MoveNode::isSourceOperation(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), and GraphEdge::toString().

Referenced by BFPushDepsUp::operator()().

Here is the call graph for this function:

◆ edgeWeight()

int DataDependenceGraph::edgeWeight	(	DataDependenceEdge &	e,
		const MoveNode &	n
	)		const

virtual

Calculates a weight value for edges, to be used for path weight calculation for selector

Current implementation quite simple to have something better than fixed weight without having to analyze the machine. 3 equals about one cycle.

In order to use a version that computes the weight strictly using only the operation latencies, thus gives the minimum achievable schedule length given enough resources (with operation latencies as in the machine), call setEdgeWeightHeuristics(EWH_REAL) before calling this. To get back to the default one, call setEdgeWeightHeuristics(EWH_DEFAULT).

Todo:: EWH_HEURISTIC is incomplete. It should take in account the number of resources in the current target machine and not assume a "generic machine".

Parameters

e	edge whose weight is being measured
n	head node of the edge.

Returns: weigth of the edge.

Reimplemented from BoostGraph< MoveNode, DataDependenceEdge >.

Definition at line 2910 of file DataDependenceGraph.cc.

                                                    {
 
    if (e.weight() != -1) {
        return e.weight();
    }
 
    if (edgeWeightHeuristics_ == EWH_HEURISTIC) {
        
        if (e.headPseudo()) {
            // pseudo deps do not really limit the scheduling.
            e.setWeight(0);
            return 0;
        }
        
        switch (e.edgeReason()) {
        case DataDependenceEdge::EDGE_OPERATION: {
            int ew = getOperationLatency(e.data()) * 3;
            e.setWeight(ew);
            return ew;
        }
        case DataDependenceEdge::EDGE_MEMORY: {
            
            if (e.dependenceType() == DataDependenceEdge::DEP_RAW) {
                // the number 9 seems to work well on most benchmarks.
                // big weight for these makes stores to be scheduled earlier, 
                // which both helps register pressure and helps stores to
                // come earlier, as memory is often worse bottleneck than
                // registers or calculation.
                e.setWeight(9);
                return 9;
            }
            // for memory WaR's and WaW's this seem to work quite well,
            // forces memory ops to be scheduled before other ops.
            e.setWeight(5);
            return 5;
        }
            
        case DataDependenceEdge::EDGE_REGISTER: {
            switch (e.dependenceType()) {
                // TODO: some connectivity heuristics
            case DataDependenceEdge::DEP_RAW: {
                // push guards a bit earlier.
                int latency = 0;
 
                if (e.guardUse()) {
                    int glat = n.guardLatency();
                    // jump guard?
 
                    // for predicated control flow ops the edge weight is
                    // guard latency + delay slots, as the predicated cflow
                    // ins has to be scehduled delay slots cycles before end.
                    if (n.isMove() && n.move().isControlFlowMove()) {
                        int ew = std::max(1, 3*(glat + delaySlots_));
                        e.setWeight(ew);
                        return ew;
                    }
                    // some other predicated operation
                    int ew = std::max(1, 3 * glat);
                    e.setWeight(ew);
                    return ew;
                } else {
                    // jump address of indirect branch
                    // indirect control flow ops the delay slots is added
                    // to the edgeweight, as the indirect control flow ins
                    // has to be scehduled delay slots cycles before end.
                    if (n.isMove() && n.move().isControlFlowMove()) {
                        latency += 3*delaySlots_;
                    }
                }
                // rrcost is heurictic on how often we usually can bypass,
                // and how often we have to add extra regcopy.
                // it's anaylyzed from the machine.
                int ew = latency + rrCost_;
                e.setWeight(ew);
                return ew;
            }
            case DataDependenceEdge::DEP_WAR: {
                e.setWeight(1);
                return 1; // can be scheduled to same cycle. but put 1 still.
            }
            case DataDependenceEdge::DEP_WAW: {
                // 3 means 1 cycle. Keeps the order, but no extra delay.
                e.setWeight(3);
                return 3;
            }
            default: {
                // 3 means 1 cycle. Keeps the order, but no extra delay.
                e.setWeight(3);
                return 3;
            }
            }
        }
        case DataDependenceEdge::EDGE_RA: {
            if (n.isMove() && n.move().isJump()) {
                int ew = delaySlots_ != 0 ?
                    (delaySlots_*3)+rrCost_ : 
                    3;
                e.setWeight(ew);
                return ew;
            } else {
                e.setWeight(rrCost_);
                return rrCost_;
            }
        }
        default:
            // 3 means 1 cycle. Keeps the order, but no extra delay.
            e.setWeight(3);
            return 3; 
        }
    } else if (edgeWeightHeuristics_ == EWH_REAL) {
//        return edgeLatency(e, ii, tail, head);
//    }
       
        if (e.headPseudo()) {
            // pseudo deps do not really limit the scheduling.
            e.setWeight(0);
            return 0;
        }
        
        switch (e.edgeReason()) {
        case DataDependenceEdge::EDGE_OPERATION: {
            return getOperationLatency(e.data());
        }
        case DataDependenceEdge::EDGE_MEMORY: {
            if (e.dependenceType() == DataDependenceEdge::DEP_RAW) {
                // allowed to write a new value at the same cycle
                // another reads it (the load gets the old value)
                // TODO: this is a bug. this should be WAR, not RAW
                e.setWeight(0);
                return 0; 
            } else {
                e.setWeight(1);
                return 1;
            }
        }
        case DataDependenceEdge::EDGE_RA: 
        case DataDependenceEdge::EDGE_REGISTER: {
            switch (e.dependenceType()) {
                // TODO: some connectivity heuristics
            case DataDependenceEdge::DEP_RAW: {
                if (e.guardUse()) {
                    int glat = n.guardLatency();
                    // jump guard?
 
                    // for predicated control flow ops the edge weight is
                    // guard latency + delay slots, as the predicated cflow
                    // ins has to be scehduled delay slots cycles before end.
                    if (n.isMove() && n.move().isControlFlowMove()) {
                        int ew = std::max(1, glat + delaySlots_);
                        e.setWeight(ew);
                        return ew;
                    }
                    // some other predicated operation
                    int ew = std::max(1, glat);
                    e.setWeight(ew);
                    return ew;
                } else {
                    // jump address of indirect branch
                    // indirect control flow ops the delay slots is added
                    // to the edgeweight, as the indirect control flow ins
                    // has to be scehduled delay slots cycles before end.
                    if (n.isMove() && n.move().isControlFlowMove()) {
                        int ew = delaySlots_ +1;
                        e.setWeight(ew);
                        return ew;
                    }
                }
                e.setWeight(1);
                return 1;
 
            }
            case DataDependenceEdge::DEP_WAR: {
                e.setWeight(0);
                return 0; // can be scheduled to same cycle
            }
            default: {
                e.setWeight(1);
                return 1;
            }
            }
        }
        default:
            e.setWeight(1);
            return 1; // can be scheduled to the next cycle (default)
        }
 
    } else {
        abortWithError("Unknown edge weight heuristics.");
    }
    e.setWeight(1);
    return 1;
}

Here is the call graph for this function:

◆ exclusingGuards()

bool DataDependenceGraph::exclusingGuards	(	const MoveNode &	mn1,
		const MoveNode &	mn2
	)		const

Definition at line 4480 of file DataDependenceGraph.cc.

                                                    {
    if (!mn1.isMove() || !mn2.isMove()) {
        return false;
    }
    const TTAProgram::Move& move1 = mn1.move();
    const TTAProgram::Move& move2 = mn2.move();
    if (move1.isUnconditional() || move2.isUnconditional()) {
        return false;
    }
    TTAProgram::MoveGuard& mg1 = move1.guard();
    TTAProgram::MoveGuard& mg2 = move2.guard();
    if (mg1.isInverted() == mg2.isInverted()) {
        return false;
    }
    NodeSet incomingGuards1 =
        guardRawPredecessors(mn1);
 
    NodeSet incomingGuards2 = 
        guardRawPredecessors(mn2);
 
    return !incomingGuards1.empty() && 
        incomingGuards1 == incomingGuards2;
}

References TTAProgram::Move::guard(), guardRawPredecessors(), TTAProgram::MoveGuard::isInverted(), MoveNode::isMove(), TTAProgram::Move::isUnconditional(), and MoveNode::move().

Referenced by DataDependenceGraphBuilder::checkAndCreateMemDep(), copyDepsOver(), copyDepsOver(), RegisterCopyAdder::createAntidepsForReg(), BFRegCopy::createAntidepsForReg(), createRegisterAntiDependenciesBetweenNodes(), DataDependenceGraphBuilder::createRegisterAntideps(), DataDependenceGraphBuilder::createSideEffectEdges(), ExecutionPipelineResource::exclusiveMoves(), mergeAndKeepAllowed(), mergeAndKeepUser(), DataDependenceGraphBuilder::processRegUse(), DataDependenceGraphBuilder::processRegWrite(), BasicBlockScheduler::tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), and unMergeUser().

Here is the call graph for this function:

◆ findBypassSource()

MoveNode * DataDependenceGraph::findBypassSource ( const MoveNode & mn )

Definition at line 5734 of file DataDependenceGraph.cc.

                                                        {
 
    DataDependenceGraph::EdgeSet edges = inEdges(mn);
    DataDependenceGraph::EdgeSet::iterator edgeIter = edges.begin();
    DataDependenceEdge* bypassEdge = NULL;
 
    // find one incoming raw edge. if multiple, cannot bypass.
    while (edgeIter != edges.end()) {
 
        DataDependenceEdge& edge = *(*edgeIter);
        // if the edge is not a real reg/ra raw edge, skip to next edge
        if (edge.edgeReason() != DataDependenceEdge::EDGE_REGISTER ||
            edge.dependenceType() != DataDependenceEdge::DEP_RAW ||
            edge.guardUse() || edge.headPseudo()) {
            edgeIter++;
            continue;
        }
 
        if (bypassEdge == NULL) {
            bypassEdge = &edge;
        } else {
            // cannot bypass if multiple inputs
            return 0;
        }
        edgeIter++;
    }
 
    // if no bypassable edge found, cannot bypass
    if (bypassEdge == NULL || bypassEdge->isBackEdge()) {
        return 0;
    }
 
    MoveNode& source = tailNode(*bypassEdge);
    return &source;
}

References DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), DataDependenceEdge::isBackEdge(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Here is the call graph for this function:

◆ findLimitingAntidependenceDestination()

MoveNode * DataDependenceGraph::findLimitingAntidependenceDestination ( MoveNode & mn )

Definition at line 5293 of file DataDependenceGraph.cc.

                                                                       {
    NodeDescriptor nd = descriptor(mn);
    MoveNode* limitingAntidep = NULL;
    EdgeSet oEdges = outEdges(mn);
    for (EdgeSet::iterator oe = oEdges.begin(); oe != oEdges.end(); oe++) {
        DataDependenceEdge& e = **oe;
        // TODO: WAW?
 
 
        if (e.dependenceType() == DataDependenceEdge::DEP_WAR && 
            e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !e.headPseudo() && !e.tailPseudo() && !e.guardUse()) {
            MoveNode& head = headNode(e,nd);
            if (head.isPlaced() && (limitingAntidep == NULL || 
                                       head.cycle()<limitingAntidep->cycle())){
                limitingAntidep = &head;
            }
        }
    }
    return limitingAntidep;
}

References MoveNode::cycle(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), and DataDependenceEdge::tailPseudo().

Referenced by BUBasicBlockScheduler::scheduleMove().

Here is the call graph for this function:

◆ findLimitingAntidependenceSource()

MoveNode * DataDependenceGraph::findLimitingAntidependenceSource ( MoveNode & mn )

Definition at line 5272 of file DataDependenceGraph.cc.

                                                                  {
    NodeDescriptor nd = descriptor(mn);
    MoveNode* limitingAntidep = NULL;
    EdgeSet iEdges = inEdges(mn);
    for (EdgeSet::iterator ie = iEdges.begin(); ie != iEdges.end(); ie++) {
        DataDependenceEdge& e = **ie;
        // TODO: WAW?
        if (e.dependenceType() == DataDependenceEdge::DEP_WAR && 
            e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !e.headPseudo() && !e.tailPseudo() && !e.guardUse()) {
            MoveNode& tail = tailNode(e,nd);
            if (tail.isPlaced() && (limitingAntidep == NULL || 
                                       tail.cycle()>limitingAntidep->cycle())){
                limitingAntidep = &tail;
            }
        }
    }
    return limitingAntidep;
}

References MoveNode::cycle(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), and DataDependenceEdge::tailPseudo().

Referenced by BasicBlockScheduler::scheduleMove().

Here is the call graph for this function:

◆ findLiveRange()

LiveRange * DataDependenceGraph::findLiveRange	(	MoveNode &	moveNode,
		bool	dest,
		bool	guard
	)		const

Finds a liverange, consisting of one (or multiple if guarded writes) write and one or multiple reads to same registers. if none found, returns empty pair.

Returns: first set contains writes, second set uses

Definition at line 4827 of file DataDependenceGraph.cc.

                                                     {
 
    NodeSet queuedWrites;
    NodeSet queuedReads;
    NodeSet queuedGuards;
 
    typedef EdgeSet::iterator EdgeIterator;
 
    LiveRange* liveRange = new LiveRange;
 
    if (dest == true) {
        queuedWrites.insert(&moveNode);
    } else {
        if (guard) {
            assert(moveNode.move().isUnconditional());
            queuedGuards.insert(&moveNode);
        } else {
            queuedReads.insert(&moveNode);
        }
    }
 
    // loop as long as we have not checked successors of some
    // write or predecessors of some read.
 
    // this is done in double-while-loop. only stop when neither
    // loop wants to continue. 
    while (!queuedWrites.empty() || !queuedReads.empty() ||
           !queuedGuards.empty()) {
        // first check writes.
        while (!queuedWrites.empty()) {
            MoveNode& write = **queuedWrites.begin();
            
            NodeDescriptor nd = descriptor(write);
            EdgeSet out = rootGraphOutEdges(write);
            
            for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
                DataDependenceEdge& e = **i;
 
                // only register raws. pseudo deps not yet supported.
                if (e.dependenceType() == DataDependenceEdge::DEP_RAW &&
                    e.edgeReason() == DataDependenceEdge::EDGE_REGISTER) {
                    MoveNode& succ = 
                        (static_cast<const DataDependenceGraph*>
                         (rootGraph()))->headNode(e, nd);
            
                    if (e.isBackEdge() || e.headPseudo() ||
                        e.tailPseudo() ||
                        !hasNode(succ)) {
                        liveRange->clear();
                        return liveRange;
                    } else {
                        if (e.guardUse()) {
                            // not yet handled. queue it
                            if (liveRange->guards.find(&succ) ==
                                liveRange->guards.end()) {
                                queuedGuards.insert(&succ);
                            }
                        } else {
                            // not yet handled. queue it
                            if (liveRange->reads.find(&succ) ==
                                liveRange->reads.end()) {
                                queuedReads.insert(&succ);
                            }
                        }
                    }
                }
            }
            // this is fully checked. add to result, remove from queue
            liveRange->writes.insert(&write);
            queuedWrites.erase(&write);
        }
 
        if (!queueRawPredecessors(
                queuedReads, liveRange->reads, queuedWrites,
                liveRange->writes, false)) {
            liveRange->clear();
            return liveRange;
        }
       
        if (!queueRawPredecessors(
                queuedGuards, liveRange->guards, queuedWrites, 
                liveRange->writes, true)) {
            liveRange->clear();
            return liveRange;
        }
    }
    return liveRange;
}

References assert, LiveRange::clear(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), LiveRange::guards, DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::hasNode(), DataDependenceEdge::headPseudo(), DataDependenceEdge::isBackEdge(), TTAProgram::Move::isUnconditional(), MoveNode::move(), queueRawPredecessors(), LiveRange::reads, BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdges(), DataDependenceEdge::tailPseudo(), and LiveRange::writes.

Referenced by RegisterRenamer::renameDestinationRegister(), and RegisterRenamer::renameSourceRegister().

Here is the call graph for this function:

◆ findLoopIndexInit()

MoveNode * DataDependenceGraph::findLoopIndexInit ( MoveNode & updateMove )

Definition at line 4755 of file DataDependenceGraph.cc.

                                                                     {
 
    DataDependenceEdge* initEdge = NULL;
    EdgeSet iEdges = rootGraphInEdges(updateMove);
    for (EdgeSet::iterator i=iEdges.begin(); i != iEdges.end(); i++) {
    DataDependenceEdge* e = *i;
    if (e->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
        e->dependenceType() == DataDependenceEdge::DEP_RAW &&
        !e->isBackEdge()) {
        if (initEdge != NULL) {
        return NULL;
        } else {
        initEdge = e;
        }
    }
    }
    if (initEdge == NULL) {
    return NULL;
    }
    return &rootGraph()->tailNode(*initEdge);
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::isBackEdge(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInEdges(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Here is the call graph for this function:

◆ findLoopIndexUpdate()

std::pair< MoveNode *, int > DataDependenceGraph::findLoopIndexUpdate ( MoveNode * indexMove )

Definition at line 4704 of file DataDependenceGraph.cc.

                                                            {
    while (indexMove->isSourceVariable()) {
        indexMove = onlyRegisterRawSource(*indexMove);
        if (indexMove == NULL) {
        return std::pair<MoveNode*, int>(NULL,0);
        }
    }
    if (indexMove->isSourceOperation()) {
        ProgramOperation* po = &indexMove->sourceOperation();
        if (po->operation().name() == "ADD" ||
        po->operation().name() == "SUB") {
            MoveNodeSet& input1Set = po->inputNode(1);
            MoveNodeSet& input2Set = po->inputNode(2);
            if (input1Set.count() != 1 || input2Set.count() != 1) {
        return std::pair<MoveNode*, int>(NULL,0);
        //return NULL;
            }
        MoveNode& input1 = input1Set.at(0);
            MoveNode& input2 = input2Set.at(0);
        MoveNode* oldIndex = NULL;
        MoveNode* val = NULL;
            if (input1.move().source().isGPR() && 
        input2.move().source().isImmediate()) {
        oldIndex = &input1;
        val = &input2;
            } else if (input2.move().source().isGPR() &&
               input1.move().source().isImmediate()) {
        oldIndex = &input2;
        val = &input1;
            } else {
        return std::pair<MoveNode*, int>(NULL,0);
        }
        while (oldIndex->isSourceVariable()) {
        oldIndex = onlyRegisterRawSource(*oldIndex);
        if (oldIndex == NULL) {
            return std::pair<MoveNode*, int>(NULL,0);
        }
        }
        if (oldIndex->isSourceOperation()) {
        if (&oldIndex->sourceOperation() == po) {
            int value = (po->operation().name() == "SUB") ? 
            -val->move().source().value().intValue() :
            val->move().source().value().intValue();
            return std::pair<MoveNode*, int>(oldIndex, value);
        }
        }
    }
    }
    return std::pair<MoveNode*, int>(NULL,0);
}

References MoveNodeSet::at(), MoveNodeSet::count(), ProgramOperation::inputNode(), SimValue::intValue(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediate(), MoveNode::isSourceOperation(), MoveNode::isSourceVariable(), MoveNode::move(), Operation::name(), onlyRegisterRawSource(), ProgramOperation::operation(), TTAProgram::Move::source(), MoveNode::sourceOperation(), and TTAProgram::Terminal::value().

Here is the call graph for this function:

◆ findLoopLimitAndIndex()

std::pair< MoveNode *, MoveNode * > DataDependenceGraph::findLoopLimitAndIndex ( MoveNode & jumpMove )

Finds the move which writes the loop limit comparison value into the loop comparison operation.

If cannot find, returs null.

Assumes positively-gworing loop with ne (or eq + xor 1) as end condition. (llvm creates this kind of loops)

Parameters

jumpMove jump move of a loop.

Returns: loop limit move or NULL of not found.

Definition at line 4618 of file DataDependenceGraph.cc.

                                                             {
    
    MoveNode* guardDef = onlyGuardDefOfMove(jumpMove);
    if (guardDef == NULL) {
        return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
    }
    while (guardDef->isSourceVariable()) {
        guardDef = onlyRegisterRawSource(*guardDef);
        if (guardDef == NULL) {
        return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
        }
    }
    if (guardDef->isSourceOperation()) {
        ProgramOperation* gdpo = &guardDef->sourceOperation();
        bool inverted = jumpMove.move().guard().isInverted();
 
        // machine does not have ne operation so eq + xor used.
        if (gdpo->operation().name() == "XOR") {
            MoveNodeSet& input1Set = gdpo->inputNode(1);
            MoveNodeSet& input2Set = gdpo->inputNode(2);
            if (input1Set.count() != 1 || input2Set.count() != 1) {
        return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
            }
            MoveNode& input1 = input1Set.at(0);
            MoveNode& input2 = input2Set.at(0);
 
            MoveNode *regMove = NULL;
            if (input1.move().source().isGPR() && 
                input2.move().source().isImmediate()) {
                regMove = &input1;
            } 
 
            if (input2.move().source().isGPR() && 
                input1.move().source().isImmediate()) {
                regMove = &input2;
            }
 
            // bypassed directly from eq?
            if (input1.isSourceOperation() &&
                input2.move().source().isImmediate()) {
                gdpo = &input1.sourceOperation();
            } else {
                if (input2.isSourceOperation() &&
                    input1.move().source().isImmediate()) {
                    gdpo = &input2.sourceOperation();
                } else { // not bypassed.
                    if (regMove != NULL) {
                        MoveNode* xorSrc = onlyRegisterRawSource(*regMove);
                        if (xorSrc != NULL && xorSrc->isSourceOperation()) {
                            inverted = !inverted;
                            gdpo = &xorSrc->sourceOperation();
                        } else {
                return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
                        }
                    } else {
            return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
                    }
                }
            }
        }
 
        if ((gdpo->operation().name() == "NE" && !inverted) ||
            (gdpo->operation().name() == "EQ"  && inverted)) {
            MoveNodeSet& input1Set = gdpo->inputNode(1);
            MoveNodeSet& input2Set = gdpo->inputNode(2);
            if (input1Set.count() != 1 || input2Set.count() != 1) {
        return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
            }
            MoveNode& input1 = input1Set.at(0);
            MoveNode& input2 = input2Set.at(0);
            if ((input1.move().source().isGPR() ||
                 input1.isSourceOperation()) && 
                input2.move().source().isImmediate()) {
        return std::pair<MoveNode*, MoveNode*>(&input2, &input1);
            } 
            if ((input2.move().source().isGPR() ||
                 input2.isSourceOperation()) && 
                input1.move().source().isImmediate()) {
        return std::pair<MoveNode*, MoveNode*>(&input1, &input2);
            }
        }
    }
    return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
}

References MoveNodeSet::at(), MoveNodeSet::count(), TTAProgram::Move::guard(), ProgramOperation::inputNode(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediate(), TTAProgram::MoveGuard::isInverted(), MoveNode::isSourceOperation(), MoveNode::isSourceVariable(), MoveNode::move(), Operation::name(), onlyGuardDefOfMove(), onlyRegisterRawSource(), ProgramOperation::operation(), TTAProgram::Move::source(), and MoveNode::sourceOperation().

Referenced by BUBasicBlockScheduler::handleLoopDDG(), and BasicBlockScheduler::scheduleMove().

Here is the call graph for this function:

◆ firstRegisterCycle()

int DataDependenceGraph::firstRegisterCycle	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the lowest cycle where accesses the given register. If unscheudled moves accessing the register, returns -1. If none found, return INT_MAX

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: cycle, or -1 if some unscheduled found, or INT_MAX if none found.

Definition at line 981 of file DataDependenceGraph.cc.

                                                                   {
 
    int firstCycle = INT_MAX;
    for (int i = nodeCount()-1; i >= 0; --i) {
        MoveNode& n = node(i);
        TTAProgram::Move& move = n.move();
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
        
        // check source
        TTAProgram::Terminal& source = move.source();
        bool sourceImmReg = source.isImmediateRegister();
        bool sourceGPR = source.isGPR();
        
        if (sourceImmReg || sourceGPR) {
            
            if (sourceImmReg)
                currentRF = &source.immediateUnit();
            else
                currentRF = &source.registerFile();
            
            if (&rf == currentRF && source.index() == registerIndex) {
                if (!n.isPlaced()) {
                    return -1;
                }
                if (n.cycle() < firstCycle) {
                    firstCycle = n.cycle();
                }
            }
        }
        
        // check destination
        TTAProgram::Terminal& destination = move.destination();
        if (destination.isGPR()) {
            currentRF = &destination.registerFile();
            
            if (&rf == currentRF && destination.index() == registerIndex) {
                if (!n.isPlaced()) {
                    return -1;
                }
                if (n.cycle() < firstCycle) {
                    firstCycle = n.cycle();
                }
                // this is a write of (constant) into reg, and no antideps in?
                if (move.isUnconditional()) {
                    if (inDegree(n) == 0) {
                        assert(firstCycle == n.cycle());
                        return firstCycle;
                    }
                }
            }
        }
        
        // check guard.
        if (!move.isUnconditional()) {
            const TTAMachine::Guard& guard = move.guard().guard();
            const TTAMachine::RegisterGuard* rg =
                dynamic_cast<const TTAMachine::RegisterGuard*>(&guard);
            if (rg != NULL) {
                if (rg->registerFile() == &rf && 
                    rg->registerIndex() == registerIndex) {
                    if (!n.isPlaced()) {
                        return -1;
                    }
                    if (n.cycle() < firstCycle) {
                        firstCycle = n.cycle();
                    }
                }
            }
        }
        if (move.isFunctionCall()) {
            const TTAMachine::RegisterFile* rrf = 
                dynamic_cast<const TTAMachine::RegisterFile*>(&rf);
            assert(rrf != NULL);
            TCEString reg = 
                DisassemblyRegister::registerName(*rrf, registerIndex);
            if (allParamRegs_.find(reg) != allParamRegs_.end()) {
                if (!n.isPlaced()) {
                    return -1;
                }
                if (n.cycle() + delaySlots_ < firstCycle) {
                    firstCycle = n.cycle() + delaySlots_ ;
                }
            }                    
        }
    }
    return firstCycle;
}

References allParamRegs_, assert, MoveNode::cycle(), delaySlots_, TTAProgram::Move::destination(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), TTAProgram::Terminal::immediateUnit(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), TTAProgram::Terminal::index(), TTAProgram::Move::isFunctionCall(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isPlaced(), TTAProgram::Move::isUnconditional(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAMachine::RegisterGuard::registerFile(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::registerIndex(), DisassemblyRegister::registerName(), and TTAProgram::Move::source().

Referenced by RegisterRenamer::findPartiallyUsedRegistersAfterCycle(), and RegisterRenamer::findPartiallyUsedRegistersInRFAfterCycle().

Here is the call graph for this function:

◆ firstScheduledRegisterKill()

MoveNode * DataDependenceGraph::firstScheduledRegisterKill	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the MoveNode of unconditional move with highest cycle that writes the given register.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The MoveNode, NULL, if not found.

Definition at line 1320 of file DataDependenceGraph.cc.

                                                                   {
 
    int firstCycle = INT_MAX;
    MoveNode* firstFound = NULL;
    int nodeCounter = nodeCount();
    for (int i = 0; i < nodeCounter; ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& dest = n.move().destination();
        if (!n.isPlaced() || !dest.isGPR())
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
            currentRF = &dest.registerFile();
 
        if (&rf == currentRF && 
            dest.index() == registerIndex &&
            n.cycle() < firstCycle &&
            n.move().isUnconditional()) {
            firstCycle = n.cycle();
            firstFound = &n;
        }
    }
    return firstFound;
}

References MoveNode::cycle(), TTAProgram::Move::destination(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), MoveNode::isPlaced(), TTAProgram::Move::isUnconditional(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), and TTAProgram::Terminal::registerFile().

Referenced by RegisterCopyAdder::createAntidepsForReg(), firstScheduledRegisterReads(), and firstScheduledRegisterWrites().

Here is the call graph for this function:

◆ firstScheduledRegisterRead()

MoveNode * DataDependenceGraph::firstScheduledRegisterRead	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex,
		int	firstCycleToTest = `0`
	)		const

Returns the MoveNode with lowest cycle that reads the given register.

Parameters

rf	The register file.
registerIndex	Index of the register.
firstCycleToTest	optional argument from which cycle to start search.

Returns: The MoveNode, NULL, if not found.

Definition at line 808 of file DataDependenceGraph.cc.

                                                   {
 
    int firstCycle = INT_MAX;
    MoveNode* firstFound = NULL;
    for (int i = 0; i < nodeCount(); ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& source = n.move().source();
        if (!n.isPlaced() || 
            !(source.isImmediateRegister() || source.isGPR())) 
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
        if (source.isImmediateRegister())
            currentRF = &source.immediateUnit();
        else
            currentRF = &source.registerFile();
 
        if (&rf == currentRF && 
            source.index() == registerIndex &&
            n.cycle() < firstCycle &&
            n.cycle() >= firstCycleToTest) {
            firstCycle = n.cycle();
            firstFound = &n;
        }
    }
    return firstFound;
}

References MoveNode::cycle(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isPlaced(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Terminal::registerFile(), and TTAProgram::Move::source().

Referenced by BUBasicBlockScheduler::bypassNode(), and BUBasicBlockScheduler::scheduleInputOperandTempMoves().

Here is the call graph for this function:

◆ firstScheduledRegisterReads()

DataDependenceGraph::NodeSet DataDependenceGraph::firstScheduledRegisterReads	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the set of MoveNodes which reads given register before first unconditional scheduled write to the register.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The set of movenodes.

Definition at line 1121 of file DataDependenceGraph.cc.

                                                                   {
 
    MoveNode* firstKill = firstScheduledRegisterKill(rf, registerIndex);
    int killCycle = firstKill == NULL ? -1 : firstKill->cycle();
    NodeSet firstReads;
 
    // first search last kill.
    for (int i = 0; i < nodeCount(); ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& source = n.move().source();
        if (!n.isPlaced() || 
            !(source.isImmediateRegister() || source.isGPR())) 
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
        if (source.isImmediateRegister())
            currentRF = &source.immediateUnit();
        else
            currentRF = &source.registerFile();
 
        if (&rf == currentRF && 
            source.index() == registerIndex) {
            if (n.cycle() < killCycle) {
                firstReads.insert(&n);
            }
        }
    }
    return firstReads;
}

References MoveNode::cycle(), firstScheduledRegisterKill(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isPlaced(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Terminal::registerFile(), and TTAProgram::Move::source().

Here is the call graph for this function:

◆ firstScheduledRegisterWrite()

MoveNode * DataDependenceGraph::firstScheduledRegisterWrite	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the MoveNode with lowest cycle that writes the given register.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The MoveNode, NULL, if not found.

Definition at line 847 of file DataDependenceGraph.cc.

                                                                   {
 
    int firstCycle = INT_MAX;
    MoveNode* firstFound = NULL;
    for (int i = 0; i < nodeCount(); ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& destination = n.move().destination();
        if (!n.isPlaced() || !destination.isGPR()) 
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
        currentRF = &destination.registerFile();
 
        if (&rf == currentRF && 
            destination.index() == registerIndex &&
            n.cycle() < firstCycle) {
            firstCycle = n.cycle();
            firstFound = &n;
        }
    }
    return firstFound;
}

References MoveNode::cycle(), TTAProgram::Move::destination(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), MoveNode::isPlaced(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), and TTAProgram::Terminal::registerFile().

Referenced by BUBasicBlockScheduler::scheduleOperand(), BUBasicBlockScheduler::scheduleResultReads(), BUBasicBlockScheduler::scheduleResultReadTempMoves(), and BUBasicBlockScheduler::scheduleRRTempMoves().

Here is the call graph for this function:

◆ firstScheduledRegisterWrites()

DataDependenceGraph::NodeSet DataDependenceGraph::firstScheduledRegisterWrites	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the set of MoveNodes which writes given register after last unconditional scheduled write to the register, and the last unconditional write.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The set of movenodes.

Definition at line 1245 of file DataDependenceGraph.cc.

                                                                   {
 
    // TODO: should this be able to be calculated from LR bookkeeping?
 
    MoveNode* firstKill = firstScheduledRegisterKill(rf, registerIndex);
    int killCycle = firstKill == NULL ? INT_MAX : firstKill->cycle();
    NodeSet firstWrites;
 
    int nodeCounter = nodeCount();
    // first search last kill.
    for (int i = 0; i < nodeCounter; ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& dest = n.move().destination();
        if (!n.isPlaced() || !dest.isGPR())
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
            currentRF = &dest.registerFile();
 
        if (&rf == currentRF && 
            dest.index() == registerIndex) {
            if (n.cycle() <= killCycle) {
                firstWrites.insert(&n);
            }
        }
    }
    return firstWrites;
}

References MoveNode::cycle(), TTAProgram::Move::destination(), firstScheduledRegisterKill(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), MoveNode::isPlaced(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), and TTAProgram::Terminal::registerFile().

Referenced by RegisterCopyAdder::createAntidepsForReg(), BFRegCopy::createAntidepsForReg(), BFRenameLiveRange::renameLiveRange(), and RegisterRenamer::renameLiveRange().

Here is the call graph for this function:

◆ fixAntidepsAfterLoopUnmergeUser()

void DataDependenceGraph::fixAntidepsAfterLoopUnmergeUser	(	MoveNode &	sourceNode,
		MoveNode &	mergedNode,
		const TCEString &	reg
	)

Definition at line 2213 of file DataDependenceGraph.cc.

                                                                                                                     {
    for (int i = 0; i < outDegree(mergedNode); i++) {
        DataDependenceEdge& edge = outEdge(mergedNode,i);
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAR &&
            edge.data() == reg) {
            return;
        }
    } 
    DataDependenceEdge* newEdge = 
        new DataDependenceEdge(DataDependenceEdge::EDGE_REGISTER, 
                               DataDependenceEdge::DEP_WAR,
                               reg, false, false, false, false, false);
    connectNodes(mergedNode, sourceNode, *newEdge);
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::DEP_WAR, BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdge().

Referenced by unMergeUser().

Here is the call graph for this function:

◆ fixInterBBAntiEdges()

void DataDependenceGraph::fixInterBBAntiEdges	(	BasicBlockNode &	bbn1,
		BasicBlockNode &	bbn2,
		bool	loopEdges
	)

Addds inter-BB-Anti edges between the the basic blocks.

currently quite a heavy routine

Parameters

bbn1	first basic block, executed first, sources of antidependence edges
bbn2	second basic block, executed later, targets of antidependence edges

Definition at line 3689 of file DataDependenceGraph.cc.

                                                                {
    std::map<TCEString, TTAProgram::Move*> firstWrites2;
    std::map<TCEString, TTAProgram::Move*> lastReads1;
    std::map<TCEString, TTAProgram::Move*> lastWrites1;
    std::map<TCEString, TTAProgram::Move*> lastGuards1;
 
    TTAProgram::BasicBlock& bb1 = bbn1.basicBlock();
    TTAProgram::BasicBlock& bb2 = bbn2.basicBlock();
 
    // find the first writes in the next BB.
    for (int i2 = 0; i2 < bb2.instructionCount(); i2++) {
        TTAProgram::Instruction& ins = bb2.instructionAtIndex(i2);
        for (int j2 = 0; j2 < ins.moveCount(); j2++) {
            TTAProgram::Move& move = ins.move(j2);
            TTAProgram::Terminal& dest = move.destination();
            if (dest.isGPR()) {
                TCEString reg2 = DisassemblyRegister::registerName(dest);
 
                std::map<TCEString, TTAProgram::Move*>::iterator iter2 = 
                    firstWrites2.find(reg2);
                if (iter2 == firstWrites2.end()) {
                    firstWrites2[reg2] = &move;
                }
            }
        }
    }
 
    // find the last reads, writes and guard uses from first BB.
    for (int i1 = bb1.instructionCount()-1; i1 >= 0 ; i1--) {
        TTAProgram::Instruction& ins = bb1.instructionAtIndex(i1);
        for (int j1 = 0; j1 < ins.moveCount(); j1++) {
            TTAProgram::Move& move = ins.move(j1);
            TTAProgram::Terminal& dest = move.destination();
            TTAProgram::Terminal& src = move.source();
            // Writes for WaWs
            if (dest.isGPR()) {
                TCEString reg1 = DisassemblyRegister::registerName(dest);
 
                std::map<TCEString, TTAProgram::Move*>::iterator iter1 = 
                    lastWrites1.find(reg1);
                if (iter1 == lastWrites1.end()) {
                    lastWrites1[reg1] = &move;
                }
            }
            // reads for WaRs
            if (src.isGPR()) {
                TCEString reg1 = DisassemblyRegister::registerName(src);
 
                std::map<TCEString, TTAProgram::Move*>::iterator iter1 = 
                    lastReads1.find(reg1);
                if (iter1 == lastReads1.end()) {
                    lastReads1[reg1] = &move;
                }
            }
            // guard uses
            if (!move.isUnconditional()) {
                const TTAMachine::Guard& g = move.guard().guard();
                const TTAMachine::RegisterGuard* rg =
                    dynamic_cast<const TTAMachine::RegisterGuard*>(&g);
                if (rg != NULL) {
                    TCEString reg1 = DisassemblyRegister::registerName(
                        *rg->registerFile(), rg->registerIndex());
                    
                    std::map<TCEString, TTAProgram::Move*>::iterator iter2 = 
                        lastGuards1.find(reg1);
                    if (iter2 == lastGuards1.end()) {
                        lastGuards1[reg1] = &move;
                    }
                }
            }
        }
    }
 
    // then go thru them
    for (std::map<TCEString, TTAProgram::Move*>::iterator iter2 = 
             firstWrites2.begin();
         iter2 != firstWrites2.end(); iter2++) {
        const TCEString& reg2 = iter2->first;
        MoveNode& mn2 = nodeOfMove(*(iter2->second));
        
        // WaRs
        TTAProgram::Move* move1 = lastReads1[reg2];
        if (move1 != NULL) {
            DataDependenceEdge* edge = 
                new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAR, reg2, false, false, false,
                    false, loopEdges);
            connectOrDeleteEdge(nodeOfMove(*move1), mn2, edge);
        }
        
        // WaWs
        move1 = lastWrites1[reg2];
        if (move1 != NULL) {
            DataDependenceEdge* edge = 
                new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAW, reg2, false, false, false,
                    false, loopEdges);
            connectOrDeleteEdge(nodeOfMove(*move1), mn2, edge);
        }
        
        // guard WaRs
        move1 = lastGuards1[reg2];
        if (move1 != NULL) {
            DataDependenceEdge* edge = 
                new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAR, reg2, true, false, false, 
                    false, loopEdges);
            connectOrDeleteEdge(nodeOfMove(*move1), mn2, edge);
        }
    }
}

References BasicBlockNode::basicBlock(), connectOrDeleteEdge(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isUnconditional(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), nodeOfMove(), TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), DisassemblyRegister::registerName(), and TTAProgram::Move::source().

Referenced by ControlFlowGraph::mergeNodes().

Here is the call graph for this function:

◆ getBasicBlockNode() [1/2]

const BasicBlockNode & DataDependenceGraph::getBasicBlockNode ( const MoveNode & mn ) const

Gives the basic block node where the node belongs to.

Parameters

mn	MoveNode whose basic block we are asking

Returns: BasicBlockNode of the move

Definition at line 186 of file DataDependenceGraph.cc.

                                                               {
    std::map<const MoveNode*, BasicBlockNode*>::const_iterator iter = 
        moveNodeBlocks_.find(&mn);
    if (iter == moveNodeBlocks_.end()) {
        TCEString msg = "MoveNode not in DDG!: ";
        msg += mn.toString();
        throw InvalidData(__FILE__,__LINE__,__func__,msg);
    }
    return *iter->second;
}

References __func__, moveNodeBlocks_, and MoveNode::toString().

Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), RegisterCopyAdder::addConnectionRegisterCopiesImmediate(), addNode(), CopyingDelaySlotFiller::checkIncomingDeps(), copyDependencies(), copyExternalInEdges(), copyExternalOutEdges(), ProgramDependenceGraph::copyRegionEECComponent(), LoopAnalyzer::findEndCond(), BF2Scheduler::handleLoopDDG(), PreOptimizer::inverseGuardsOfHeads(), BFRegCopy::operator()(), ProgramDependenceGraph::ProgramDependenceGraph(), BF2Scheduler::revertBBLiveRangeBookkeepingForDestination(), BF2Scheduler::revertBBLiveRangeBookkeepingForSource(), PreOptimizer::tryToOptimizeAddressReg(), and updateRegWrite().

Here is the call graph for this function:

◆ getBasicBlockNode() [2/2]

BasicBlockNode & DataDependenceGraph::getBasicBlockNode ( MoveNode & mn )

Gives the basic block node where the node belongs to.

Parameters

mn	MoveNode whose basic block we are asking

Returns: BasicBlockNode of the move

Definition at line 204 of file DataDependenceGraph.cc.

                                                    {
    std::map<const MoveNode*, BasicBlockNode*>::iterator iter = 
        moveNodeBlocks_.find(&mn);
    if (iter == moveNodeBlocks_.end()) {
        TCEString msg = "MoveNode not in DDG!: ";
        msg += mn.toString();
        throw InvalidData(__FILE__,__LINE__,__func__,msg);
    }
    return *iter->second;
}

References __func__, moveNodeBlocks_, and MoveNode::toString().

Here is the call graph for this function:

◆ getOperationLatency()

int DataDependenceGraph::getOperationLatency ( const TCEString & name ) const

private

Gets the lowest instruction latency for given operation.

If latency is not known (no machine is given) does some simple heuristics.

This function should propably be on somewhere else.

Parameters

op	operation whose minimum latency is being searched

Returns: minimum latency of given operation.

Definition at line 3304 of file DataDependenceGraph.cc.

                                                                    {
    std::map<TCEString, int>::const_iterator iter =
        operationLatencies_.find(name);
    if (iter != operationLatencies_.end()) {
        return iter->second;
    } else {
        return 1;
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::name(), and operationLatencies_.

Referenced by earliestCycle(), edgeLatency(), edgeWeight(), and latestCycle().

Here is the call graph for this function:

◆ guardConverted()

void DataDependenceGraph::guardConverted	(	MoveNode &	guardSrc,
		MoveNode &	dst
	)

Definition at line 5795 of file DataDependenceGraph.cc.

                                                                          {
    // similar than mergeAndKeepDestination
    ProgramOperationPtr srcPO = guardSrc.sourceOperationPtr();
    srcPO->addGuardOutputNode(dst);
    dst.setGuardOperationPtr(srcPO);
 
    TCEString regName = removeRAWEdges(guardSrc, dst);
 
    for (int i = 0; i < rootGraphInDegree(guardSrc); i++) {
        DataDependenceEdge& edge = rootGraphInEdge(guardSrc ,i);
        // skip antidependencies due bypassed register.. these are no more
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.data() == regName) {
            if (edge.dependenceType() == DataDependenceEdge::DEP_WAW ||
                edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
                continue;
            }
        }
        assert(!edge.guardUse());
        if (edge.edgeReason() != DataDependenceEdge::EDGE_OPERATION) {
            std::cerr << "Warning: non-operation edge: " << edge.toString()
                      << " on guard bypass" << std::endl;
            continue;
        }
 
        // copy other edges. (operation inputs)
        MoveNode& source = rootGraph()->tailNode(edge);
        DataDependenceEdge* newEdge =
            new DataDependenceEdge(
                DataDependenceEdge::EDGE_OPERATION,
                DataDependenceEdge::DEP_UNKNOWN, edge.data(), true);
 
        rootGraph()->connectNodes(source, dst, *newEdge);
    }
 
 
    // remove WAR antideps out from this
    for (int i = 0; i < rootGraphOutDegree(dst); i++) {
        DataDependenceEdge& edge = rootGraphOutEdge(dst, i);
 
        // create new WaW in place of old WaR
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAR &&
            edge.data() == regName && edge.guardUse()) {
 
            // and remove the old WaR
            (static_cast<DataDependenceGraph*>(rootGraph()))->
                removeEdge(edge, &dst, NULL);
            i--; // don't skip one edge here!
        }
    }
}

References assert, BoostGraph< GraphNode, GraphEdge >::connectNodes(), DataDependenceEdge::DEP_UNKNOWN, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), removeRAWEdges(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInDegree(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInEdge(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutDegree(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdge(), MoveNode::setGuardOperationPtr(), MoveNode::sourceOperationPtr(), BoostGraph< GraphNode, GraphEdge >::tailNode(), and GraphEdge::toString().

Referenced by BFLateBypassGuard::operator()(), and BFEarlyGuardBypass::operator()().

Here is the call graph for this function:

◆ guardDefMoves()

DataDependenceGraph::NodeSet DataDependenceGraph::guardDefMoves ( const MoveNode & moveNode )

Returns all movenodes that define (write the value of) the guard the given move node is predicated with.

Parameters

moveNode The move node of which guard defining move to find.

Returns: The MoveNodes that produces the guard value. Can be multiple if the writes are predicated or in different BB. If not found, returns NULL

Definition at line 743 of file DataDependenceGraph.cc.

                                                           {
 
    NodeSet guardDefMoves;
    EdgeSet inputEdges = inEdges(moveNode);
    for (EdgeSet::iterator i = inputEdges.begin();
         i != inputEdges.end(); i++) {
        DataDependenceEdge &edge = **i;
        if (edge.guardUse() && 
            edge.dependenceType() == DataDependenceEdge::DEP_RAW) {
            guardDefMoves.insert(&tailNode(edge));
        }
    }
    return guardDefMoves;
}

References DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::edge(), guardDefMoves(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by guardDefMoves(), guardsAllowBypass(), lastGuardDefMove(), onlyGuardDefOfMove(), and BasicBlockScheduler::tryToOptimizeWaw().

Here is the call graph for this function:

◆ guardRawPredecessors()

DataDependenceGraph::NodeSet DataDependenceGraph::guardRawPredecessors ( const MoveNode & node ) const

Definition at line 4048 of file DataDependenceGraph.cc.

                                                                    {
    NodeSet preds;
    DataDependenceGraph::EdgeSet iEdges = inEdges(node);
    for (DataDependenceGraph::EdgeSet::iterator i = iEdges.begin();
         i != iEdges.end(); i++) {
        DataDependenceEdge* iEdge = *i;
        if (iEdge->guardUse() && iEdge->dependenceType() == 
            DataDependenceEdge::DEP_RAW) {
            preds.insert(&tailNode(*iEdge));
        }
    }
    return preds;
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by exclusingGuards(), and sameGuards().

Here is the call graph for this function:

◆ guardRenamed()

DataDependenceGraph::UndoData DataDependenceGraph::guardRenamed ( MoveNode & mn )

Definition at line 5006 of file DataDependenceGraph.cc.

                                             {
 
    UndoData undoData;
 
    assert(!mn.move().isUnconditional());
    const TTAMachine::RegisterGuard* rg =
        dynamic_cast<const TTAMachine::RegisterGuard*>(
            &mn.move().guard().guard());
    assert(rg != NULL);
    const TCEString newReg = rg->registerFile()->name() + 
        '.' + Conversion::toString(rg->registerIndex());
 
    for (int i = 0; i < outDegree(mn); i++) {
        DataDependenceEdge& oEdge = outEdge(mn,i);
    
        if (oEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            oEdge.dependenceType() == DataDependenceEdge::DEP_WAR &&
            !oEdge.tailPseudo() && oEdge.guardUse()) {
            
            MoveNode& head = headNode(oEdge);            
            TTAProgram::Terminal& writeTerm = head.move().destination();
 
            // if this edge disappers because of the renaming?
            if (oEdge.headPseudo() ||
                (writeTerm.isGPR() && (
                     writeTerm.index() != rg->registerIndex() ||
                     &writeTerm.registerFile() != rg->registerFile()))) {
                undoData.removedEdges.insert(RemovedEdgeDatum(mn, head, oEdge));
                removeEdge(oEdge, NULL, &mn);
                i--; // don't skip one edge here!
            } else {
                // update the edge. also other end changed
                undoData.changedDataEdges[&oEdge] = oEdge.data();
                oEdge.setData(newReg);
            }
        }
    }
    return undoData;
}

References assert, DataDependenceGraph::UndoData::changedDataEdges, DataDependenceEdge::data(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isUnconditional(), MoveNode::move(), TTAMachine::Component::name(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), BoostGraph< MoveNode, DataDependenceEdge >::outEdge(), TTAMachine::RegisterGuard::registerFile(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::registerIndex(), DataDependenceGraph::UndoData::removedEdges, BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), DataDependenceEdge::setData(), DataDependenceEdge::tailPseudo(), and Conversion::toString().

Referenced by BFRenameLiveRange::renameLiveRange(), and RegisterRenamer::renameLiveRange().

Here is the call graph for this function:

◆ guardRestored()

void DataDependenceGraph::guardRestored	(	MoveNode &	guardSrc,
		MoveNode &	dst
	)

Definition at line 5849 of file DataDependenceGraph.cc.

                                                                         {
    // similar than mergeAndKeepDestination
    ProgramOperation& srcPO = guardSrc.sourceOperation();
    srcPO.removeGuardOutputNode(dst);
    dst.unsetGuardOperation();
 
    // remove the incoming guard operation edges.
    for (int i = 0; i < inDegree(dst); i++) {
        DataDependenceEdge& edge = inEdge(dst,i);
        if (edge.guardUse() &&
            edge.edgeReason() == DataDependenceEdge::EDGE_OPERATION) {
            removeEdge(edge, &dst, NULL);
            i--;
        }
    }
 
    // name of the bypass reg.
    TTAProgram::Terminal& dest = guardSrc.move().destination();
    assert(dest.isGPR());
    TCEString regName = DisassemblyRegister::registerName(dest);
 
    // create register edge between nodes.
    // this was removed by the merge.
    DataDependenceEdge* dde = new DataDependenceEdge(
        DataDependenceEdge::EDGE_REGISTER,
        DataDependenceEdge::DEP_RAW, regName,
        true, false, false, false);
    connectNodes(guardSrc, dst, *dde);
 
    // TODO: restore the guard antidep edges.
 
    // All all outgoing WAR's to merged node. The war's go to
    // all same places where WAW's fo from source node.
    for (int i = 0; i < outDegree(guardSrc); i++) {
        DataDependenceEdge& edge = outEdge(guardSrc,i);
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAW &&
            edge.data() == regName) {
            MoveNode& head = headNode(edge);
            // skip nodes with exclusive guard.
            DataDependenceEdge* newEdge = new DataDependenceEdge(
                DataDependenceEdge::EDGE_REGISTER,
                DataDependenceEdge::DEP_WAR, regName, true, false,
                false, edge.headPseudo(), edge.loopDepth());
            connectNodes(dst, head, *newEdge);
        }
    }
}

Referenced by BFLateBypassGuard::operator()(), BFLateBypassGuard::undoOnlyMe(), and BFEarlyGuardBypass::undoOnlyMe().

Here is the call graph for this function:

◆ guardsAllowBypass()

bool DataDependenceGraph::guardsAllowBypass	(	const MoveNode &	defNode,
		const MoveNode &	useNode,
		bool	loopBypass = `false`
	)

Checks whether guards allow bypassing.

Parameters

defNode	node defining a value, bypass source.
useNode	node using the value, node being bypassed.

Returns: true if guards do not prevent bypassing.

Definition at line 4543 of file DataDependenceGraph.cc.

                                                                       {
    
    // can always bypass from unconditional
    if (defNode.move().isUnconditional()) {
        return true;
    }
 
    // cannot bypass from conditional to unconditional
    if (useNode.move().isUnconditional()) {
        return false;
    }
 
    NodeSet defGuardDefMoves = guardDefMoves(defNode);
    NodeSet useGuardDefMoves = guardDefMoves(useNode);
    
    // guard value changed between iterations, cannot trust same src!
    // could check the backedge property from the guard edges,
    // this is suboptimal and safe
    if (loopBypass && !defGuardDefMoves.empty()) {
        return false;
    }
 
    // if guards defined in different place, 
    // we do now know if they are equal.
    if (defGuardDefMoves != useGuardDefMoves) {
        return false;
    }
 
    // if guards are equal, bypass allowed.
    return defNode.move().guard().guard().isEqual(
        useNode.move().guard().guard());
}

References TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), guardDefMoves(), TTAMachine::Guard::isEqual(), TTAProgram::Move::isUnconditional(), and MoveNode::move().

Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), BUBasicBlockScheduler::bypassNode(), CycleLookBackSoftwareBypasser::bypassNode(), and BFLateBypasses::operator()().

Here is the call graph for this function:

◆ hasAllRegisterAntidependencies()

bool DataDependenceGraph::hasAllRegisterAntidependencies ( )

inline

Definition at line 379 of file DataDependenceGraph.hh.

                                                 {
        return registerAntidependenceLevel_ >= ALL_ANTIDEPS;
    }

References ALL_ANTIDEPS, and registerAntidependenceLevel_.

Referenced by ControlFlowGraph::mergeNodes(), DataDependenceGraphBuilder::setSucceedingPredepsForBB(), DataDependenceGraphBuilder::updateRegistersAliveAfter(), and updateRegWrite().

◆ hasEqualEdge()

bool DataDependenceGraph::hasEqualEdge	(	const MoveNode &	tailNode,
		const MoveNode &	headNode,
		const DataDependenceEdge &	edge
	)		const

private

Checks if the graph already has an edge with same properties from same node to same node.

Parameters

tailNode	tail node of edge
headNode	head node of edge
edge	edge which for to test equality

Returns: true if equal edge exists, false if not exist

Definition at line 3324 of file DataDependenceGraph.cc.

          {
 
    typedef GraphTraits::out_edge_iterator outEdgeIter;
    std::pair<outEdgeIter, outEdgeIter> edges = boost::out_edges(
        descriptor(tailNode), graph_);
    NodeDescriptor hnd = descriptor(headNode);
 
    for (outEdgeIter ei = edges.first; ei != edges.second; ei++) {
        if (boost::target(*ei, graph_) == hnd) {
            DataDependenceEdge* dde = graph_[(*ei)];
            if (*dde == edge) {
                return true;
            }
        }
    }
    return false;
}

References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, BoostGraph< MoveNode, DataDependenceEdge >::headNode(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by connectOrDeleteEdge().

Here is the call graph for this function:

◆ hasIntraBBRegisterAntidependencies()

bool DataDependenceGraph::hasIntraBBRegisterAntidependencies ( )

inline

Definition at line 387 of file DataDependenceGraph.hh.

                                                     {
        return registerAntidependenceLevel_ >= INTRA_BB_ANTIDEPS;
    }

References INTRA_BB_ANTIDEPS, and registerAntidependenceLevel_.

Referenced by ControlFlowGraph::mergeNodes(), and DataDependenceGraphBuilder::processRegWrite().

◆ hasOtherRegWawSources()

bool DataDependenceGraph::hasOtherRegWawSources ( const MoveNode & mn ) const

Definition at line 5701 of file DataDependenceGraph.cc.

                                                                        {
    EdgeSet iEdges = inEdges(mn);
    for (auto e: iEdges) {
        if (e->edgeReason() != DataDependenceEdge::EDGE_REGISTER ||
            e->dependenceType() != DataDependenceEdge::DEP_WAW) {
            continue;
        }
        MoveNode& tail = tailNode(*e);
        if (&tail != &mn) {
            return true;
        }
    }
    return false;
}

References DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Here is the call graph for this function:

◆ hasRegWaw()

bool DataDependenceGraph::hasRegWaw	(	const MoveNodeUse &	mnu,
		std::set< MoveNodeUse >	targets
	)		const

Definition at line 5518 of file DataDependenceGraph.cc.

                                                               {
    NodeDescriptor nd = descriptor(*mnu.mn());
 
    std::pair<OutEdgeIter, OutEdgeIter> edges =
        boost::out_edges(nd, graph_);
 
    // loop thru all edges
    for (OutEdgeIter ei = edges.first; ei != edges.second; ei++ ) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge& edge = *graph_[ed];
        if (edge.dependenceType() == DataDependenceEdge::DEP_WAW  &&
            edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !edge.isBackEdge()) {
 
            MoveNode* target = graph_[boost::target(ed, graph_)];
            if (AssocTools::containsKey(targets, MoveNodeUse(*target))) {
                return true;
            }
        }
    }
    return false;
}

References AssocTools::containsKey(), DataDependenceEdge::DEP_WAW, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::graph_, GraphEdge::isBackEdge(), and MoveNodeUse::mn().

Referenced by DataDependenceGraphBuilder::processRegUse().

Here is the call graph for this function:

◆ hasSingleBBLoopRegisterAntidependencies()

bool DataDependenceGraph::hasSingleBBLoopRegisterAntidependencies ( )

inline

Definition at line 383 of file DataDependenceGraph.hh.

                                                          {
        return registerAntidependenceLevel_ >= SINGLE_BB_LOOP_ANTIDEPS;
    }

References registerAntidependenceLevel_, and SINGLE_BB_LOOP_ANTIDEPS.

Referenced by DataDependenceGraphBuilder::processRegWrite(), DataDependenceGraphBuilder::setSucceedingPredepsForBB(), and DataDependenceGraphBuilder::updateBB().

◆ hasUnscheduledPredecessors()

bool DataDependenceGraph::hasUnscheduledPredecessors ( const MoveNode & mn ) const

Definition at line 5594 of file DataDependenceGraph.cc.

                                                                        {
    
    DataDependenceGraph::NodeSet pred = predecessors(mn);
    for (DataDependenceGraph::NodeSet::iterator i = pred.begin(); 
         i != pred.end(); ++i) {
        if (!(**i).isPlaced()) {
            return true;
        }
    }
    return false;
}

References BoostGraph< MoveNode, DataDependenceEdge >::predecessors().

Here is the call graph for this function:

◆ hasUnscheduledSuccessors()

bool DataDependenceGraph::hasUnscheduledSuccessors ( const MoveNode & mn ) const

Definition at line 5607 of file DataDependenceGraph.cc.

                                                                      {
    
    DataDependenceGraph::NodeSet succ = successors(mn);
    for (DataDependenceGraph::NodeSet::iterator i = succ.begin(); 
         i != succ.end(); ++i) {
        if (!(**i).isPlaced()) {
            return true;
        }
    }
    return false;
}

References BoostGraph< MoveNode, DataDependenceEdge >::successors().

Here is the call graph for this function:

◆ isLoopBypass()

bool DataDependenceGraph::isLoopBypass	(	MoveNode &	sourceNode,
		MoveNode &	userNode
	)

Definition at line 1916 of file DataDependenceGraph.cc.

                                                                               {
    EdgeSet edges = connectingEdges(
        sourceNode, userNode);
 
    for (EdgeSet::iterator i = edges.begin();
         i != edges.end(); i++ ) {
        DataDependenceEdge* edge = *i;
        if (edge->dependenceType() == DataDependenceEdge::DEP_RAW &&
            edge->isBackEdge()) {
            return true;
        }
    }
    return false;
}

References BoostGraph< MoveNode, DataDependenceEdge >::connectingEdges(), DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::edge(), and GraphEdge::isBackEdge().

Referenced by mergeAndKeepSource(), mergeAndKeepUser(), and BFMergeAndKeepUser::operator()().

Here is the call graph for this function:

◆ isLoopInvariant()

bool DataDependenceGraph::isLoopInvariant ( const MoveNode & mn ) const

Definition at line 5688 of file DataDependenceGraph.cc.

                                                                  {
    EdgeSet iEdges = inEdges(mn);
    for (EdgeSet::iterator i = iEdges.begin(); i != iEdges.end(); i++) {
        DataDependenceEdge& e = **i;
        if (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            e.dependenceType() == DataDependenceEdge::DEP_RAW &&
            !e.guardUse()) {
            return false;
        }
    }
    return true;
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), and BoostGraph< MoveNode, DataDependenceEdge >::inEdges().

Here is the call graph for this function:

◆ isNotAvoidable()

bool DataDependenceGraph::isNotAvoidable ( const DataDependenceEdge & edge ) const

Returns true in case the given dependency cannot be (currently) avoided by techniques such as register renaming or speculation.

If the edge is "avoidable", it doesn't meen it always is. E.g., sometimes the register renamer can find a better register to remove the dependency, sometimes it cannot. That is, this method returns true only if it's certain we cannot do anything about the dependency with the current compiler backend or by, e.g., adding more registers to the machine.

Definition at line 5553 of file DataDependenceGraph.cc.

                                                                        {
 
    if (!edge.isFalseDep()) return true;
    MoveNode& tail = tailNode(edge);
    MoveNode& head = headNode(edge);
 
    /* The control dependency caused antidep case. In case the antidep
       overwrites the register with a different predicate than the other,
       it is not possible to simply rename the other register, but, e.g.,
       speculative execution has to be added with a final write to the
       original register.
 
       Example:
 
       a) p1: foo -> r1
       b) p1: r1 -> X
       c) p2: foo -> r1
       d) p2 r1 -> Y jne
       e) r1 -> foo
 
       In case p2 = !p1 then we can parallelize freely. In case
       p2 = p1 then we can parallelize after a reg rename of r1.
       Otherwise, speculative or similar transformation has to be
       done, which currently is not supported by tcecc.
    */
    if ((edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER) &&        
        (!tail.move().isUnconditional() && !head.move().isUnconditional()) &&
        !(tail.move().guard().guard().isEqual(head.move().guard().guard()) ||
          tail.move().guard().guard().isOpposite(head.move().guard().guard())))
        return true;
 
    if ((edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER) &&        
        ((tail.move().isUnconditional() && !head.move().isUnconditional()) ||
         (!tail.move().isUnconditional() && head.move().isUnconditional())))
        return true;
    
        
    return false;
}

References BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), TTAMachine::Guard::isEqual(), TTAMachine::Guard::isOpposite(), TTAProgram::Move::isUnconditional(), MoveNode::move(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by trueDependenceGraph().

Here is the call graph for this function:

◆ isRootGraphProcedureDDG()

bool DataDependenceGraph::isRootGraphProcedureDDG ( )

private

Tells whether the root graph is a procedure-wide ddg or created from a smaller piece of code.

This is needed for dead result elimination.

Returns: if root graph of the subgraph tree contains whole procedure.

Definition at line 3669 of file DataDependenceGraph.cc.

                                             {
    if (parentGraph_ == NULL) {
        return procedureDDG_;
    } else {
        return static_cast<DataDependenceGraph*>(parentGraph_)
            ->isRootGraphProcedureDDG();
    }
}

References isRootGraphProcedureDDG(), BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, and procedureDDG_.

Referenced by isRootGraphProcedureDDG(), and resultUsed().

Here is the call graph for this function:

◆ largestCycle()

int DataDependenceGraph::largestCycle ( ) const

Returns the largest cycle of a move in the DDG.

Current implementation is quite slow, so don't call in critical places.

Returns: The largest cycle of a move.

Definition at line 1838 of file DataDependenceGraph.cc.

                                        {
 
    int maxCycle = 0;
    for (int i = 0; i < nodeCount(); ++i) {
        Node& n = node(i);
        if (n.isPlaced()) {
            maxCycle = std::max(maxCycle, n.cycle());
        }
    }
 
    return maxCycle;
}

References MoveNode::cycle(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().

Referenced by ResourceConstraintAnalyzer::analyzeRegisterAntideps(), LoopPrologAndEpilogBuilder::build(), dotString(), BBSchedulerController::executeDDGPass(), BasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), and BasicBlockScheduler::scheduleMove().

Here is the call graph for this function:

◆ lastGuardDefMove()

MoveNode * DataDependenceGraph::lastGuardDefMove ( MoveNode & moveNode )

Returns the MoveNode that defines (writes the value of) the guard the given move node is predicated with. If there are multiple, returns the last.

Parameters

moveNode The move node of which guard defining move to find.

Returns: The MoveNode that produces the guard value. If not found, returns NULL

Definition at line 721 of file DataDependenceGraph.cc.

                                                        {
    NodeSet guardDefs = guardDefMoves(moveNode);
    MoveNode* last = NULL;
    for (NodeSet::iterator i = guardDefs.begin(); 
         i != guardDefs.end(); i++) {
        if (last == NULL || last->cycle() < (*i)->cycle()) {
            last = *i;
        }
    }
    return last;
}

References MoveNode::cycle(), and guardDefMoves().

Here is the call graph for this function:

◆ lastRegisterCycle()

int DataDependenceGraph::lastRegisterCycle	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the highest cycle where accesses the given register. If unscheudled moves accessing the register, returns INT_MAX; If none found, returns -1.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: cycle, or INT_MAX if some unscheduled found.

Definition at line 882 of file DataDependenceGraph.cc.

                                                                   {
 
    int lastCycle = -1;
    for (int i = 0; i < nodeCount(); ++i) {
        MoveNode& n = node(i);
        TTAProgram::Move& move = n.move();
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
        
        // check source
        TTAProgram::Terminal& source = move.source();
        bool sourceImmReg = source.isImmediateRegister();
        bool sourceGPR = source.isGPR();
        
        if (sourceImmReg || sourceGPR) {
            
            if (sourceImmReg)
                currentRF = &source.immediateUnit();
            else
                currentRF = &source.registerFile();
            
            if (&rf == currentRF && source.index() == registerIndex) {
                if (!n.isPlaced()) {
                    return INT_MAX;
                }
                if (n.cycle() > lastCycle) {
                    lastCycle = n.cycle();
                }
            }
        }
        
        // check destination
        TTAProgram::Terminal& destination = move.destination();
        if (destination.isGPR()) {
            currentRF = &destination.registerFile();
            
            if (&rf == currentRF && destination.index() == registerIndex) {
                if (!n.isPlaced()) {
                    return INT_MAX;
                }
                if (n.cycle() > lastCycle) {
                    lastCycle = n.cycle();
                }
 
                if (move.isUnconditional()) {
                    if (outDegree(n) == 0) {
                        assert(lastCycle == n.cycle());
                        return lastCycle;
                    }
                }
            }
        }
        
        // check guard.
        if (!move.isUnconditional()) {
            const TTAMachine::Guard& guard = move.guard().guard();
            const TTAMachine::RegisterGuard* rg =
                dynamic_cast<const TTAMachine::RegisterGuard*>(&guard);
            if (rg != NULL) {
                if (rg->registerFile() == &rf && 
                    rg->registerIndex() == registerIndex) {
                    if (!n.isPlaced()) {
                        return INT_MAX;
                    }
                    if (n.cycle() > lastCycle) {
                        lastCycle = n.cycle();
                    }
                }
            }
        }
        if (move.isFunctionCall()) {
            const TTAMachine::RegisterFile* rrf = 
                dynamic_cast<const TTAMachine::RegisterFile*>(&rf);
            assert(rrf != NULL);
            TCEString reg = 
                DisassemblyRegister::registerName(*rrf, registerIndex);
            if (allParamRegs_.find(reg) != allParamRegs_.end()) {
                if (!n.isPlaced()) {
                    return INT_MAX;
                }
                if (n.cycle() + delaySlots_> lastCycle) {
                    lastCycle = n.cycle() + delaySlots_ ;
                }
            }                    
        }
    }
    return lastCycle;
}

References allParamRegs_, assert, MoveNode::cycle(), delaySlots_, TTAProgram::Move::destination(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::Move::isFunctionCall(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isPlaced(), TTAProgram::Move::isUnconditional(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), TTAMachine::RegisterGuard::registerFile(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::registerIndex(), DisassemblyRegister::registerName(), and TTAProgram::Move::source().

Referenced by RegisterRenamer::findPartiallyUsedRegistersBeforeCycle(), and RegisterRenamer::findPartiallyUsedRegistersInRFBeforeCycle().

Here is the call graph for this function:

◆ lastScheduledRegisterGuardReads()

DataDependenceGraph::NodeSet DataDependenceGraph::lastScheduledRegisterGuardReads	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the set of MoveNodes which reads given register as guard after last unconditional scheduled write to the register.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The set of movenodes.

Definition at line 1163 of file DataDependenceGraph.cc.

                                                                   {
 
    MoveNode* lastKill = lastScheduledRegisterKill(rf, registerIndex);
    int killCycle = lastKill == NULL ? -1 : lastKill->cycle();
    NodeSet lastGuards;
 
    int nodeCounter = nodeCount();
    // first search last kill.
    for (int i = 0; i < nodeCounter; ++i) {
        MoveNode& n = node(i);
        TTAProgram::Move& move = n.move();
        if (move.isUnconditional() || !n.isPlaced()) {
            continue;
        }
 
        const TTAMachine::Guard* guard = &move.guard().guard();
        const TTAMachine::RegisterGuard* rg =
            dynamic_cast<const TTAMachine::RegisterGuard*>(guard);
        if (rg == NULL) {
            continue;
        }
        const TTAMachine::BaseRegisterFile* currentRF = rg->registerFile();
        if (&rf == currentRF && 
            rg->registerIndex() == registerIndex) {
            if (n.cycle() > killCycle) {
                lastGuards.insert(&n);
            }
        }
    }
    return lastGuards;
}

References MoveNode::cycle(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), MoveNode::isPlaced(), TTAProgram::Move::isUnconditional(), lastScheduledRegisterKill(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAMachine::RegisterGuard::registerFile(), and TTAMachine::RegisterGuard::registerIndex().

Referenced by RegisterRenamer::renameLiveRange().

Here is the call graph for this function:

◆ lastScheduledRegisterKill()

MoveNode * DataDependenceGraph::lastScheduledRegisterKill	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the MoveNode of unconditional move with highest cycle that writes the given register.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The MoveNode, NULL, if not found.

Definition at line 1285 of file DataDependenceGraph.cc.

                                                                   {
 
    int lastCycle = -1;
    MoveNode* lastFound = NULL;
    int nodeCounter = nodeCount();
    for (int i = 0; i < nodeCounter; ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& dest = n.move().destination();
        if (!n.isPlaced() || !dest.isGPR())
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
            currentRF = &dest.registerFile();
 
        if (&rf == currentRF && 
            dest.index() == registerIndex &&
            n.cycle() > lastCycle &&
            n.move().isUnconditional()) {
            lastCycle = n.cycle();
            lastFound = &n;
        }
    }
    return lastFound;
}

References MoveNode::cycle(), TTAProgram::Move::destination(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), MoveNode::isPlaced(), TTAProgram::Move::isUnconditional(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), and TTAProgram::Terminal::registerFile().

Referenced by RegisterCopyAdder::createAntidepsForReg(), BFRegCopy::createAntidepsForReg(), lastScheduledRegisterGuardReads(), lastScheduledRegisterReads(), and lastScheduledRegisterWrites().

Here is the call graph for this function:

◆ lastScheduledRegisterRead()

MoveNode * DataDependenceGraph::lastScheduledRegisterRead	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex,
		int	lastCycleToTest = `INT_MAX`
	)		const

Returns the MoveNode with highest cycle that reads the given register.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The MoveNode, NULL, if not found.

Definition at line 766 of file DataDependenceGraph.cc.

                               {
 
    int lastCycle = -1;
    MoveNode* lastFound = NULL;
    for (int i = 0; i < nodeCount(); ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& source = n.move().source();
        if (!n.isPlaced() || 
            !(source.isImmediateRegister() || source.isGPR())) 
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
        if (source.isImmediateRegister())
            currentRF = &source.immediateUnit();
        else
            currentRF = &source.registerFile();
 
        if (&rf == currentRF && 
            source.index() == registerIndex &&
            n.cycle() > lastCycle &&
            n.cycle() <= lastCycleToTest) {
            lastCycle = n.cycle();
            lastFound = &n;
        }
    }
    return lastFound;
}

References MoveNode::cycle(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isPlaced(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Terminal::registerFile(), and TTAProgram::Move::source().

Referenced by BUBasicBlockScheduler::bypassNode(), BasicBlockScheduler::scheduleInputOperandTempMoves(), BasicBlockScheduler::scheduleResultReads(), BasicBlockScheduler::scheduleResultReadTempMoves(), and BasicBlockScheduler::scheduleRRTempMoves().

Here is the call graph for this function:

◆ lastScheduledRegisterReads()

DataDependenceGraph::NodeSet DataDependenceGraph::lastScheduledRegisterReads	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the set of MoveNodes which reads given register after last unconditional scheduled write to the register.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The set of movenodes.

Definition at line 1080 of file DataDependenceGraph.cc.

                                                                   {
 
    MoveNode* lastKill = lastScheduledRegisterKill(rf, registerIndex);
    int killCycle = lastKill == NULL ? -1 : lastKill->cycle();
    NodeSet lastReads;
 
    int nodeCounter = nodeCount();
    // first search last kill.
    for (int i = 0; i < nodeCounter; ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& source = n.move().source();
        if (!n.isPlaced() || 
            !(source.isImmediateRegister() || source.isGPR())) 
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
        if (source.isImmediateRegister())
            currentRF = &source.immediateUnit();
        else
            currentRF = &source.registerFile();
 
        if (&rf == currentRF && 
            source.index() == registerIndex) {
            if (n.cycle() > killCycle) {
                lastReads.insert(&n);
            }
        }
    }
    return lastReads;
}

References MoveNode::cycle(), TTAProgram::Terminal::immediateUnit(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isPlaced(), lastScheduledRegisterKill(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Terminal::registerFile(), and TTAProgram::Move::source().

Referenced by RegisterCopyAdder::createAntidepsForReg(), BFRegCopy::createAntidepsForReg(), and RegisterRenamer::renameLiveRange().

Here is the call graph for this function:

◆ lastScheduledRegisterWrites()

DataDependenceGraph::NodeSet DataDependenceGraph::lastScheduledRegisterWrites	(	const TTAMachine::BaseRegisterFile &	rf,
		int	registerIndex
	)		const

Returns the set of MoveNodes which writes given register after last unconditional scheduled write to the register, and the last unconditional write.

Parameters

rf	The register file.
registerIndex	Index of the register.

Returns: The set of movenodes.

Definition at line 1206 of file DataDependenceGraph.cc.

                                                                   {
 
    MoveNode* lastKill = lastScheduledRegisterKill(rf, registerIndex);
    int killCycle = lastKill == NULL ? -1 : lastKill->cycle();
    NodeSet lastReads;
 
    int nodeCounter = nodeCount();
    // first search last kill.
    for (int i = 0; i < nodeCounter; ++i) {
        MoveNode& n = node(i);
 
        TTAProgram::Terminal& dest = n.move().destination();
        if (!n.isPlaced() || !dest.isGPR())
            continue;
 
        const TTAMachine::BaseRegisterFile* currentRF = NULL;
            currentRF = &dest.registerFile();
 
        if (&rf == currentRF && 
            dest.index() == registerIndex) {
            if (n.cycle() >= killCycle) {
                lastReads.insert(&n);
            }
        }
    }
    return lastReads;
}

References MoveNode::cycle(), TTAProgram::Move::destination(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), MoveNode::isPlaced(), lastScheduledRegisterKill(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), and TTAProgram::Terminal::registerFile().

Referenced by RegisterCopyAdder::createAntidepsForReg(), BFRegCopy::createAntidepsForReg(), and RegisterRenamer::renameLiveRange().

Here is the call graph for this function:

◆ latestCycle()

int DataDependenceGraph::latestCycle	(	const MoveNode &	moveNode,
		unsigned int	ii = `UINT_MAX`,
		bool	ignoreRegAntideps = `false`,
		bool	ignoreUnscheduledSuccessors = `true`,
		bool	ignoreGuards = `false`,
		bool	ignoreFuDeps = `false`,
		bool	ignoreSameOperationEdges = `false`
	)		const

Returns the latest cycle this move can be scheduled at given the cycles of the dependencies.

This is assumed to be used with bottom-up scheduling. Checks all successor nodes and checks their min cycle if they are scheduled. If none found, INT_MAX is returned, if at least one of successors is unscheduled, returns 0.

Parameters

moveNode The move node for which to find the latest cycle.

Returns: The latest cycle the move can be scheduled to according to data dependencies, 0 if unknown.

Todo:: Consider the latency for result read move!

Definition at line 543 of file DataDependenceGraph.cc.

                                         {
 
    if (machine_ == NULL) {
        throw InvalidData(__FILE__,__LINE__,__func__,
                          " setMachine() must be called before this");
    }
    
    const EdgeSet edges = outEdges(moveNode);
    int maxCycle = INT_MAX;
    for (EdgeSet::const_iterator i = edges.begin(); 
         i != edges.end(); ++i) {
        DataDependenceEdge& edge = **i;
 
        if (ignoreGuards && edge.guardUse()) {
            continue;
        }
        if (ignoreFuDeps &&
            (edge.edgeReason() == DataDependenceEdge::EDGE_FUSTATE ||
             edge.edgeReason() == DataDependenceEdge::EDGE_MEMORY)) {
            continue;
        }
 
        if (ignoreSameOperationEdges &&
            edge.edgeReason() == DataDependenceEdge::EDGE_OPERATION) {
            continue;
        }
 
        MoveNode& head = headNode(edge);
        if (&head == &moveNode) {
            continue;
        }
        
        /// @todo Consider the latency for result read move!
        if (head.isPlaced()) {
            int latency = 1;
            int effHeadCycle = head.cycle();
            
            // If call, make sure all incoming deps fit into delay slots,
            // can still be later than the call itself
            // dependence type does not matter.
            if (edge.headPseudo()) {
                effHeadCycle += delaySlots_;
            } else {
                if (edge.dependenceType() == DataDependenceEdge::DEP_WAW) {
                    
                    // ignore deg antidep? then skip over this edge.
                    if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER
                        && !edge.tailPseudo() && ignoreRegAntideps) {
                        continue;
                    }
 
                    // latency does not matter with WAW. always +1.
                    effHeadCycle -= 1;
                } else {
                    if (edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
 
                        // ignore deg antidep? then skip over this edge.
                        if (edge.edgeReason() == 
                            DataDependenceEdge::EDGE_REGISTER && 
                            !edge.tailPseudo() && ignoreRegAntideps) {
                            continue;
                        }
 
                        // WAR allows writing at same cycle than reading.
                        // in WAR also the latency goes backwards, 
                        // new value can
                        // be written before old is read is latency is big.
                        if (edge.guardUse()) {
                            latency = moveNode.guardLatency();
                        } 
                        // TODO: generate some hasAutomaticBundling()
                        // property to ADF
                        if (machine_->triggerInvalidatesResults()) {
                            latency = 0;
                        }
                        effHeadCycle = effHeadCycle + latency - 1;
                    } else {
                        // RAW
                        if (edge.guardUse()) {
                            latency = head.guardLatency();
                        } else {
                            if (edge.edgeReason() ==
                                DataDependenceEdge::EDGE_OPERATION &&
                                moveNode.isDestinationOperation() &&
                                head.inSameOperation(moveNode)) {
                                latency = getOperationLatency(edge.data());
                            }
                        }
                        // in case of RAW, value must be written latency
                        // cycles before it is used
                        effHeadCycle -= latency;
                    }
                }
            }
 
            assert ((ii != 0 || edge.loopDepth() ==0) && 
                    "ii should not be 0 if we have an loop edge");
            effHeadCycle += (ii * edge.loopDepth());
 
            maxCycle = std::min(effHeadCycle, maxCycle);
        } else {
            if (!edge.isBackEdge()) {
                if (!ignoreUnscheduledSuccessors) {
                    return -1;
                }
            }
        }
 
        // TODO: now does this for all input moves, not just trigger
        if (machine_->triggerInvalidatesResults() &&
            head.isSourceOperation()) {
            ProgramOperation& headPO = head.sourceOperation();
            for (int i = 0; i < headPO.inputMoveCount(); i++) {
                MoveNode& inputMove = headPO.inputMove(i);
                if (!inputMove.isPlaced()) {
                    continue;
                }
 
                if (edge.dependenceType() == DataDependenceEdge::DEP_WAR &&
                    (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     edge.edgeReason() == DataDependenceEdge::EDGE_RA)) {
 
                    // same operation. 0 cycle war.
                    // TODO: also this if bundle ordering correct.
                    if (moveNode.isDestinationOperation() &&
                        &moveNode.destinationOperation() ==
                        &headPO && !edge.isBackEdge()) {
                        maxCycle = std::min(maxCycle, inputMove.cycle());
                    } else {
                        // different operation.1 cycle war,to be sure,for now
                        maxCycle = std::min(maxCycle, inputMove.cycle()-1);
                    }
                }
 
                if (edge.dependenceType() == DataDependenceEdge::DEP_WAW &&
                    (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
                     edge.edgeReason() == DataDependenceEdge::EDGE_RA)) {
                    maxCycle = std::min(maxCycle, inputMove.cycle()-1);
                }
            }
        }
    }
 
    return maxCycle;
}

Referenced by CycleLookBackSoftwareBypasser::bypass(), BFPushAntidepDown::operator()(), BFPushAntidepsDown::operator()(), BFPushMoveUp::operator()(), BFPushMoveUp2::operator()(), BFScheduleExact::operator()(), BFSchedulePreLoopShared::operator()(), BFShareOperands::operator()(), BFRemoveGuardsFromSuccs::operator()(), BUBasicBlockScheduler::scheduleMove(), BasicBlockScheduler::scheduleMove(), BUBasicBlockScheduler::scheduleOperandWrites(), BasicBlockScheduler::tryToDelayOperands(), BUBasicBlockScheduler::tryToOptimizeWaw(), and BUBasicBlockScheduler::tryToSwitchInputs().

Here is the call graph for this function:

◆ machine()

const TTAMachine::Machine & DataDependenceGraph::machine ( ) const

inline

Definition at line 260 of file DataDependenceGraph.hh.

260{ return *machine_; }

References machine_.

Referenced by ResourceConstraintAnalyzer::analyzeMoveNode(), ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage(), and setMachine().

◆ memoryDependenceGraph()

DataDependenceGraph * DataDependenceGraph::memoryDependenceGraph ( )

Returns a version of the graph with only nodes and edges that present memory dependencies.

Definition at line 3482 of file DataDependenceGraph.cc.

                                           {
    DataDependenceGraph* subGraph = 
        new DataDependenceGraph(
            allParamRegs_, "memory DDG",
            registerAntidependenceLevel_, NULL, false, false);
 
    if (machine_ != NULL)
        subGraph->setMachine(*machine_);
    
    NodeSet nodes;
    for (int i = 0; i < nodeCount(); ++i) {
 
        MoveNode& mn = node(i);
        EdgeSet outEdg = outEdges(mn);
        bool found = false;
        for (EdgeSet::iterator ei = outEdg.begin(); ei != outEdg.end(); ei++) {
            Edge& edge = **ei;
            if (edge.edgeReason() == DataDependenceEdge::EDGE_MEMORY) {
                nodes.insert(&node(i));
                found = true;
                break;
            }
        }
 
        if (found) continue;
        EdgeSet inEdg = inEdges(mn);
        for (EdgeSet::iterator ei = inEdg.begin(); ei != inEdg.end(); ei++) {
            Edge& edge = **ei;
            if (edge.edgeReason() == DataDependenceEdge::EDGE_MEMORY) {
                nodes.insert(&node(i));
                break;
            }
        }
 
    }
    constructSubGraph(*subGraph, nodes);
 
    return subGraph;
}

References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_MEMORY, BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), machine_, BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), registerAntidependenceLevel_, and setMachine().

Referenced by ResourceConstraintAnalyzer::analyze().

Here is the call graph for this function:

◆ mergeAndKeepAllowed()

bool DataDependenceGraph::mergeAndKeepAllowed	(	MoveNode &	sourceNode,
		MoveNode &	userNode
	)

Checks if software bypassing is allowed without causing a deadlock through some circlar ddg dependence.

Parameters

sourceNode	node writing the value which is bypassed
userNode	node using the value, source of this node will be updated.

Definition at line 1880 of file DataDependenceGraph.cc.

                                                                                 {
 
    // check against to WAR's to each others caused by
    // A->B ; B-A trying to be bypassed to same cycle. don't allow this.
    // TODO: this does not handle/detect: A -> B ; C -> A; D -> C  where
    // B -> D is being bypassed from A. creates a loop.
 
    for (int i = 0; i < outDegree(sourceNode); i++) {
        DataDependenceEdge& edge = outEdge(sourceNode,i);
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAR &&
            !edge.tailPseudo()) {
            MoveNode& target = headNode(edge);
            if (!exclusingGuards(userNode, target)) {
                if (&target != &userNode && hasPath(target, userNode)) {
                    return false;
                }
            }
        }
    }
 
    if (!hasEdge(sourceNode, userNode)) {
        writeToDotFile("no_edge_on_merge.dot");
        throw Exception(
            __FILE__,__LINE__,__func__,"No edge between nodes being merged "
            + sourceNode.toString() + " " + userNode.toString());
    }
 
    if (!sourceNode.isMove() || !userNode.isMove()) {
        throw Exception(
            __FILE__,__LINE__,__func__,"Cannot merge entry/exit node!");
    }
 
    return true;
}

References __func__, DataDependenceEdge::DEP_WAR, BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, exclusingGuards(), BoostGraph< MoveNode, DataDependenceEdge >::hasEdge(), BoostGraph< MoveNode, DataDependenceEdge >::hasPath(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), MoveNode::isMove(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), BoostGraph< MoveNode, DataDependenceEdge >::outEdge(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by mergeAndKeepSource(), and mergeAndKeepUser().

Here is the call graph for this function:

◆ mergeAndKeepSource()

bool DataDependenceGraph::mergeAndKeepSource	(	MoveNode &	resultNode,
		MoveNode &	userNode,
		bool	force = `false`
	)

Definition at line 1962 of file DataDependenceGraph.cc.

                                                          {
 
    if (!force && !mergeAndKeepAllowed(sourceNode, userNode)) {
        return false;
    }
 
    // update the move
    sourceNode.move().setDestination(userNode.move().destination().copy());
 
    bool userIsRegToItselfCopy = false;
    // If source is an operation, set programOperation
    if (userNode.isDestinationOperation()) {
        // TODO: operand sharing, multiple users?
        ProgramOperationPtr dstOp = userNode.destinationOperationPtr();
        dstOp->addInputNode(sourceNode);
        sourceNode.addDestinationOperationPtr(dstOp);
        // TODO: remove the source node operand fromt he operatioN!
 
        // set fu annotations
        for (int j = 0; j < userNode.move().annotationCount(); j++) {
            TTAProgram::ProgramAnnotation anno = userNode.move().annotation(j);
            if (anno.id() == TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST) {
                sourceNode.move().addAnnotation(
                    TTAProgram::ProgramAnnotation(
                        TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST, anno.payload()));
            }
            if (anno.id() == TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST) {
                sourceNode.move().addAnnotation(
                    TTAProgram::ProgramAnnotation(
                        TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST, anno.payload()));
            }
        }
    } else {
        // bypassing from stupid reg-to-itself needs extra handling.
        if (userNode.move().source().equals(
                userNode.move().destination())) {
            userIsRegToItselfCopy = true;
        }
    }
 
    bool loopBypass = isLoopBypass(sourceNode, userNode);
 
    // remove RAW deps between source and user.
    TCEString regName = removeRAWEdges(sourceNode, userNode);
 
    
    for (int i = 0; i < rootGraphOutDegree(userNode); i++) {
        DataDependenceEdge& edge = rootGraphOutEdge(userNode,i);
 
        // skip antidependencies due bypassed register.. these are no more
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.data() == regName) {
            if (edge.dependenceType() == DataDependenceEdge::DEP_WAW ||
                edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
                continue;
            }
        }
 
        // copy other edges.
        MoveNode& dst = rootGraph()->headNode(edge);
        DataDependenceEdge* newEdge = new DataDependenceEdge(edge, loopBypass);
        
        // it the edge is a loop edge, put it only in root/parent graph.
        if (parentGraph_ != NULL) {
            static_cast<DataDependenceGraph*>(rootGraph())->
                connectNodes(sourceNode, dst, *newEdge, 
                             (edge.isBackEdge()?this:NULL));
        } else {
            connectNodes(sourceNode, dst, *newEdge);
        }
    }
 
    // copy antideps over these two nodes
    copyDepsOver(sourceNode, userNode, true, false);
 
    // fix WAR antidependencies to WaW
    for (int i = 0; i < inDegree(sourceNode); i++) {
        DataDependenceEdge& edge = inEdge(sourceNode,i);
    
        // create new WaW in place of old WaR
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAR &&
            edge.data() == regName) {
 
            // if stupid reg to itself copy, keep to in edges..
            if (!userIsRegToItselfCopy) {
            // and remove the old WaR
                removeEdge(edge, NULL, &sourceNode);
                i--; // don't skip one edge here!
            }
        }
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAW &&
            edge.data() == regName) {
            removeEdge(edge, NULL, &sourceNode);
            i--; // don't skip one edge here!
        }
    }
    
    for (int i = 0; i < rootGraphInDegree(userNode); i++) {
        DataDependenceEdge& e = rootGraphInEdge(userNode,i);
 
        // do not copy guard use edges - the user already ahs them.
        // copying them leads to exponential increase in guard ege counts.
        if (e.guardUse() && e.dependenceType() == DataDependenceEdge::DEP_RAW) {
            continue;
        }
        if (&rootGraph()->tailNode(e) != &sourceNode) {
            rootGraph()->copyInEdge(sourceNode, e);
        }
    }
 
    return true;
}

Here is the call graph for this function:

◆ mergeAndKeepUser()

bool DataDependenceGraph::mergeAndKeepUser	(	MoveNode &	resultNode,
		MoveNode &	userNode,
		bool	force = `false`
	)

Definition at line 2079 of file DataDependenceGraph.cc.

                                                          {
 
    if (!force && !mergeAndKeepAllowed(sourceNode, userNode)) {
        return false;
    }
 
//    writeToDotFile("before_merge.dot");
 
    bool loopBypass = isLoopBypass(sourceNode, userNode);
 
    // Cannot bypass over multiple loop iterations. even with force flag.
    if (loopBypass) {
    for (int i = 0; i < inDegree(sourceNode); i++) {
        DataDependenceEdge& edge = inEdge(sourceNode,i);
        if (!edge.isFalseDep() && edge.isBackEdge()) {
        return false;
        }
    }
    }
 
    // update the move
    userNode.move().setSource(sourceNode.move().source().copy());
 
    bool sourceIsRegToItselfCopy = false;
    // If source is an operation, set programOperation
    if (sourceNode.isSourceOperation()) {
        ProgramOperationPtr srcOp = sourceNode.sourceOperationPtr();
        srcOp->addOutputNode(userNode);
        userNode.setSourceOperationPtr(srcOp);
 
        // set fu annotations
        for (int j = 0; j < sourceNode.move().annotationCount(); j++) {
            TTAProgram::ProgramAnnotation anno = sourceNode.move().annotation(j);
            if (anno.id() == TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_SRC) {
                userNode.move().addAnnotation(
                    TTAProgram::ProgramAnnotation(
                        TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_SRC, anno.payload()));
            }
            if (anno.id() == TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC) {
                userNode.move().addAnnotation(
                    TTAProgram::ProgramAnnotation(
                        TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC, anno.payload()));
            }
            if (anno.id() == TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC) {
                userNode.move().addAnnotation(
                    TTAProgram::ProgramAnnotation(
                        TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC, anno.payload()));
            }
        }
    } else {
        // bypassing from stupid reg-to-itself needs extra handling.
        if (sourceNode.move().source().equals(
                sourceNode.move().destination())) {
            sourceIsRegToItselfCopy = true;
        }
    }
 
    // remove RAW deps between source and user.
    TCEString regName = removeRAWEdges(sourceNode, userNode);
 
 
    // if we are bypassign from a register-to-register copy, we'll have to
    // copy incoming raw edges also in rootgraph level to preserve inter-bb
    // -dependencies. 
    for (int i = 0; i < rootGraphInDegree(sourceNode); i++) {
        DataDependenceEdge& edge = rootGraphInEdge(sourceNode,i);
 
        // skip antidependencies due bypassed register.. these are no more
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.data() == regName) {
            if (edge.dependenceType() == DataDependenceEdge::DEP_WAW ||
                edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
                continue;
            }
        }
 
        // do not copy guard use edges - the user already ahs them.
        // copying them leads to exponential increase in guard ege counts.
        if (edge.guardUse()) {
            continue;
        }
 
        // copy other edges.
        MoveNode& source = rootGraph()->tailNode(edge);
        DataDependenceEdge* newEdge = new DataDependenceEdge(edge, loopBypass);
        rootGraph()->connectNodes(source, userNode, *newEdge);
    }
 
    if (sourceNode.isSourceVariable() || sourceNode.isSourceRA()) {
        // if bypassing reg-to-reg this copy anti edges resulting from the
        // read of the other register.
        for (int i = 0; i < rootGraphOutDegree(sourceNode); i++) {
            DataDependenceEdge& edge = rootGraphOutEdge(sourceNode,i);
            if ((edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER||
                 edge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
                edge.dependenceType() == DataDependenceEdge::DEP_WAR &&
                !edge.tailPseudo()) {
 
                MoveNode& target = rootGraph()->headNode(edge);
 
                if (!(static_cast<DataDependenceGraph*>(rootGraph()))
                     ->exclusingGuards(userNode, target) && 
                     &userNode != &target) {
                    DataDependenceEdge* newEdge = new DataDependenceEdge(edge, loopBypass);
                    // TODO: loop here!
                    rootGraph()->connectNodes(userNode, target, *newEdge);
                }
            }
        }
    }
 
    // fix WAR antidependencies to WaW
    for (int i = 0; i < rootGraphOutDegree(userNode); i++) {
        DataDependenceEdge& edge = rootGraphOutEdge(userNode,i);
    
        // create new WaW in place of old WaR
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAR && 
            edge.data() == regName) {
 
            // if stupid reg to itself copy, keep to in edges..
            if (!sourceIsRegToItselfCopy) {
            // and remove the old WaR
                (static_cast<DataDependenceGraph*>(rootGraph()))->
                    removeEdge(edge, &userNode, NULL);
                i--; // don't skip one edge here!
            }
        }
    }
    return true;
}

References TTAProgram::AnnotatedInstructionElement::addAnnotation(), TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_SRC, TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC, TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC, TTAProgram::AnnotatedInstructionElement::annotation(), BoostGraph< GraphNode, GraphEdge >::connectNodes(), TTAProgram::Terminal::copy(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, TTAProgram::Terminal::equals(), exclusingGuards(), BoostGraph< GraphNode, GraphEdge >::headNode(), TTAProgram::ProgramAnnotation::id(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), BoostGraph< MoveNode, DataDependenceEdge >::inEdge(), GraphEdge::isBackEdge(), isLoopBypass(), MoveNode::isSourceOperation(), MoveNode::isSourceRA(), MoveNode::isSourceVariable(), mergeAndKeepAllowed(), MoveNode::move(), TTAProgram::ProgramAnnotation::payload(), BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), removeRAWEdges(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInDegree(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInEdge(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutDegree(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdge(), TTAProgram::Move::setSource(), MoveNode::setSourceOperationPtr(), TTAProgram::Move::source(), MoveNode::sourceOperationPtr(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), BUBasicBlockScheduler::bypassNode(), and CycleLookBackSoftwareBypasser::bypassNode().

Here is the call graph for this function:

◆ moveFUDependenciesToTrigger()

void DataDependenceGraph::moveFUDependenciesToTrigger ( MoveNode & trigger )

Trigger of an operation may change when scheduling. This method updates fu state dependence edges to point to trigger instead of some other node of an operation. (they should point to trigger).

Definition at line 4785 of file DataDependenceGraph.cc.

                                                                  {
    if (!trigger.isDestinationOperation()) {
        return;
    }
    ProgramOperation& po = trigger.destinationOperation();
 
    // move input edges.
    for (int i = 0; i < po.inputMoveCount(); i++) {
        MoveNode& node = po.inputMove(i);
        if (&node != &trigger) {
            EdgeSet iEdges = rootGraphInEdges(node);
            for (EdgeSet::iterator i=iEdges.begin(); i != iEdges.end(); i++) {
                DataDependenceEdge& e = **i;
                if (e.edgeReason() == DataDependenceEdge::EDGE_FUSTATE) {
                    moveInEdge(node, trigger, e);
                }
            }
        }
    }
 
    // move output edges.
    for (int i = 0; i < po.inputMoveCount(); i++) {
        MoveNode& node = po.inputMove(i);
        if (&node != &trigger) {
            EdgeSet oEdges = rootGraphOutEdges(node);
            for (EdgeSet::iterator i=oEdges.begin(); i != oEdges.end(); i++) {
                DataDependenceEdge& e = **i;
                if (e.edgeReason() == DataDependenceEdge::EDGE_FUSTATE) {
                    moveOutEdge(node, trigger, e);
                }
            }
        }
    }
}

References MoveNode::destinationOperation(), DataDependenceEdge::EDGE_FUSTATE, DataDependenceEdge::edgeReason(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isDestinationOperation(), BoostGraph< MoveNode, DataDependenceEdge >::moveInEdge(), BoostGraph< MoveNode, DataDependenceEdge >::moveOutEdge(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdges().

Referenced by BUBasicBlockScheduler::scheduleOperandWrites().

Here is the call graph for this function:

◆ movesAtCycle()

DataDependenceGraph::NodeSet DataDependenceGraph::movesAtCycle ( int cycle ) const

Returns the moves that are scheduled at the given cycle.

Parameters

cycle The cycle.

Returns: Move that are scheduled at the given cycle.

Definition at line 699 of file DataDependenceGraph.cc.

                                                 {
 
    NodeSet moves;
    for (int i = 0; i < nodeCount(); ++i) {
        Node& n = node(i);
        if (n.isPlaced() && n.cycle() == cycle)
            moves.insert(&n);
    }
 
    return moves;
}

References MoveNode::cycle(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().

Referenced by dotString(), and BasicBlockScheduler::handleRemovedResultMoves().

Here is the call graph for this function:

◆ nodeOfMove()

MoveNode & DataDependenceGraph::nodeOfMove ( const TTAProgram::Move & move )

Gets a node of a move.

Warning: this operations is currently O(n). Smarter data structure needed for faster operation, propably should be implemented.

Parameters

move move.

Returns: MoveNode of the given move

Definition at line 3600 of file DataDependenceGraph.cc.

                                                          {
 
    auto i = nodesOfMoves_.find(&move);
    if (i != nodesOfMoves_.end()) {
        return *(i->second);
    } 
 
    TCEString msg = "move not in ddg: " + 
        Conversion::toString(reinterpret_cast<long>(&move)) + " " + 
        POMDisassembler::disassemble(move);
    throw InstanceNotFound(__FILE__,__LINE__,__func__, msg);
}

References __func__, POMDisassembler::disassemble(), nodesOfMoves_, and Conversion::toString().

Referenced by LoopAnalyzer::analyze(), CopyingDelaySlotFiller::collectMoves(), DataDependenceGraphBuilder::constructIndividualBB(), MoveNodeDuplicator::duplicateMove(), fixInterBBAntiEdges(), CopyingDelaySlotFiller::getMove(), ControlFlowGraph::mergeNodes(), BFShareOperandsLate::operator()(), ControlFlowGraph::removeJumpToTarget(), ControlFlowGraph::removeUnreachableNodes(), CopyingDelaySlotFiller::updateFTBBAndCfg(), and CopyingDelaySlotFiller::updateJumpsAndCfg().

Here is the call graph for this function:

◆ onlyGuardDefOfMove()

MoveNode * DataDependenceGraph::onlyGuardDefOfMove ( MoveNode & moveNode )

Finds (only) node which writes the guard value of a move. If none or multiple, return NULL

Definition at line 4581 of file DataDependenceGraph.cc.

                                                                    {
    NodeSet guardDefs = guardDefMoves(moveNode);
    if (guardDefs.size() != 1) {
        return NULL;
    }
    return *guardDefs.begin();
}

References guardDefMoves().

Referenced by LoopAnalyzer::analyze(), findLoopLimitAndIndex(), BF2Scheduler::handleLoopDDG(), and writesJumpGuard().

Here is the call graph for this function:

◆ onlyIncomingGuard()

DataDependenceEdge * DataDependenceGraph::onlyIncomingGuard ( const MoveNode & mn ) const

Returns the only incoming guard edge to given node

if there are multiple incoming guard edges, return NULL.

Parameters

mn	MoveNode whose incoming edges we are searching.

Returns: only guard edge to mn or NULL if no or multiple.

Definition at line 4024 of file DataDependenceGraph.cc.

                              {
    DataDependenceEdge* guard = NULL;
    DataDependenceGraph::EdgeSet iEdges = inEdges(mn);
 
    for (DataDependenceGraph::EdgeSet::iterator i = iEdges.begin();
         i != iEdges.end(); i++) {
        DataDependenceEdge* iEdge = *i;
        if (iEdge->guardUse() && iEdge->dependenceType() == 
            DataDependenceEdge::DEP_RAW) {
            if (guard == NULL) {
                guard = iEdge;
            } else {
                if (!(*guard == *iEdge) || 
                    &tailNode(*iEdge) != &tailNode(*guard)) {
                    return NULL; // too complicated guard
                }
            }
        }
    }
    return guard;
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Here is the call graph for this function:

◆ onlyRegisterEdgeIn()

DataDependenceEdge * DataDependenceGraph::onlyRegisterEdgeIn ( MoveNode & mn ) const

Returns the only incoming register edge to a node. If none or multiple, returns NULL.

Definition at line 255 of file DataDependenceGraph.cc.

                                                          {
    
    DataDependenceEdge* result = NULL;
    for (int i = 0; i < inDegree(mn); i++) {
        DataDependenceEdge &edge = inEdge(mn, i);
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER) {
            if (result == NULL) {
                result = &edge;
            } else {
                return NULL;
            }
        }
    }
    return result;
}

References BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), and BoostGraph< MoveNode, DataDependenceEdge >::inEdge().

Here is the call graph for this function:

◆ onlyRegisterEdgeOut()

DataDependenceEdge * DataDependenceGraph::onlyRegisterEdgeOut ( MoveNode & mn ) const

Returns the only outgoing register edge from a node. If none or multiple, returns NULL.

Definition at line 276 of file DataDependenceGraph.cc.

                                                           {
 
    DataDependenceEdge* result = NULL;
    for (int i = 0; i < outDegree(mn); i++) {
        DataDependenceEdge &edge = outEdge(mn, i);
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER) {
            if (result == NULL) {
                result = &edge;
            } else {
                return NULL;
            }
        }
    }
    return result;
}

References BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdge().

Here is the call graph for this function:

◆ onlyRegisterRawAncestor()

const MoveNode * DataDependenceGraph::onlyRegisterRawAncestor	(	const MoveNode &	mn,
		const std::string &	sp
	)		const

Tracks the origin of the data a movenode reads. Goes back thru DDG and tracks register-to register reads.

If data comes from operation, returns the operation result read. If data comes from stack pointer, returns the stack pointer read. If the data may come from multiple places (conditional writes to reg, or writes to same reg in multiple BB's), return the move which read the value from the reg.

Definition at line 4203 of file DataDependenceGraph.cc.

                                                   {
    const MoveNode* node = &mn;
 
    while(true) {
        if (node->isSourceReg(sp)) {
            return node;
        }
        MoveNode* src = onlyRegisterRawSource(*node);
        if (src == NULL) {
            return node;
        } else {
            // this should not be needed if incoming code were sensible
            // but it often is not. extra check to prevetn forever loop.
            if (node == src) {
                return node;
            }
            node = src;
        }
    } 
}

References BoostGraph< MoveNode, DataDependenceEdge >::node(), and onlyRegisterRawSource().

Referenced by OffsetAliasAnalyzer::analyze(), and OffsetAliasAnalyzer::isAddressTraceable().

Here is the call graph for this function:

◆ onlyRegisterRawDestinations()

DataDependenceGraph::NodeSet DataDependenceGraph::onlyRegisterRawDestinations	(	const MoveNode &	mn,
		bool	allowGuardEdges = `false`,
		bool	allowBackEdges = `false`
	)		const

Returns the destinations of ordinary register RAW edge to given node, ie the moves which reads the value this move writes.

Parameters

mn	MoveNode whose succssor moves we are searching.

Returns: only move reading reg this writes or NULL if no or multiple.

Definition at line 4163 of file DataDependenceGraph.cc.

                                                                         {
    NodeSet destination;
    NodeDescriptor nd = descriptor(mn);
    
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    std::pair<OutEdgeIter, OutEdgeIter> edges =
        boost::out_edges(nd, graph_);
 
    for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge* edge = graph_[ed];
        if (edge->dependenceType() == DataDependenceEdge::DEP_RAW &&
            edge->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            (allowGuardEdges || !edge->guardUse())
            && !edge->tailPseudo()) {
            if (!edge->headPseudo() && (allowBackEdges || !edge->isBackEdge())) {
                destination.insert(graph_[boost::target(ed, graph_)]);
            } else {
                destination.clear();
                break;
            }
        }
    }
    return destination;
}

References DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::graph_, and GraphEdge::isBackEdge().

Referenced by BF2ScheduleFront::allNodesOfSameOperation(), BUBasicBlockScheduler::bypassNode(), BUBasicBlockScheduler::findBypassDestinations(), and BUMoveNodeSelector::mightBeReady().

Here is the call graph for this function:

◆ onlyRegisterRawDestinationsWithEdges()

std::map< DataDependenceEdge , MoveNode , DataDependenceEdge::Comparator > DataDependenceGraph::onlyRegisterRawDestinationsWithEdges	(	const MoveNode &	mn,
		bool	allowBackEdges
	)		const

Returns the destinations of ordinary register RAW edge to given node, ie the moves which reads the value this move writes.

Parameters

mn	MoveNode whose succssor moves we are searching.

Returns: only move reading reg this writes or NULL if no or multiple.

Definition at line 4124 of file DataDependenceGraph.cc.

                                                   {
    std::map<DataDependenceEdge*, MoveNode*, DataDependenceEdge::Comparator>
        destination;
    NodeDescriptor nd = descriptor(mn);
 
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    std::pair<OutEdgeIter, OutEdgeIter> edges =
        boost::out_edges(nd, graph_);
 
    for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge* edge = graph_[ed];
        if (edge->dependenceType() == DataDependenceEdge::DEP_RAW &&
            edge->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !edge->tailPseudo()) {
            if (!edge->headPseudo() && (allowBackEdges || !edge->isBackEdge())) {
                destination.insert(std::make_pair(edge, graph_[boost::target(ed, graph_)]));
            } else {
                destination.clear();
                break;
            }
        }
    }
    return destination;
}

References DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::graph_, and GraphEdge::isBackEdge().

Referenced by BFLateBypasses::operator()().

Here is the call graph for this function:

◆ onlyRegisterRawSource()

MoveNode * DataDependenceGraph::onlyRegisterRawSource	(	const MoveNode &	mn,
		int	guardEdges = `2`,
		int	backEdges = `0`
	)		const

Returns the source of only ordinary register RAW edge to given node, ie the only move which writes the value this move reads.

backEdges: 0: do not care 1: only backedges 2: no backedges

guardEdges: 0: do not care 1: only guard edges 2: no guard edges

if there are multiple nodes where the value may come, return NULL, or if none found.

Parameters

mn	MoveNode whose predecessor noves we are searching.

Returns: only move writing reg this reads or NULL if no or multiple.

Definition at line 4083 of file DataDependenceGraph.cc.

          {
    MoveNode* source = NULL;
    NodeDescriptor nd = descriptor(mn);
    
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    std::pair<InEdgeIter, InEdgeIter> edges =
        boost::in_edges(nd, graph_);
 
    for (InEdgeIter ei = edges.first; ei != edges.second; ei++) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge* edge = graph_[ed];
        if (backEdges == 1 && !edge->isBackEdge()) continue;
        if (backEdges == 2 && edge->isBackEdge()) continue;
        if (guardEdges == 1 && !edge->guardUse()) continue;
        if (guardEdges == 2 && edge->guardUse()) continue;
        if (edge->dependenceType() == DataDependenceEdge::DEP_RAW &&
            edge->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !edge->headPseudo() && !edge->tailPseudo()) {
            if (source == NULL) {
                source = graph_[boost::source(ed, graph_)];
            } else {
                return NULL;
            }
        }
    }
    return source;
}

References DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::graph_, and GraphEdge::isBackEdge().

Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), BF2ScheduleFront::allNodesOfSameOperation(), LoopAnalyzer::analyze(), OffsetAliasAnalyzer::analyzeLoopPtrIncrease(), BUBasicBlockScheduler::findBypassDestinations(), LoopAnalyzer::findEndCond(), LoopAnalyzer::findInitAndUpdate(), findLoopIndexUpdate(), findLoopLimitAndIndex(), ConstantAliasAnalyzer::getConstantAddress(), StackAliasAnalyzer::getStackOffset(), BUMoveNodeSelector::mightBeReady(), onlyRegisterRawAncestor(), BFEarlyGuardBypass::operator()(), OffsetAliasAnalyzer::sameLoopAndPrevSources(), MemoryAliasAnalyzer::searchLoopIndexBasedIncrement(), PreOptimizer::tryToPrecalcConstantAdd(), PreOptimizer::tryToRemoveEq(), and LoopAnalyzer::tryTrackCommonAncestor().

Here is the call graph for this function:

◆ operationInEdges()

DataDependenceGraph::EdgeSet DataDependenceGraph::operationInEdges ( const MoveNode & node ) const

Definition at line 5913 of file DataDependenceGraph.cc.

                                                                {
    std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
        descriptor(node), graph_);
 
    EdgeSet result;
 
    for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
        DataDependenceEdge* edge = graph_[(*ei)];
        if (edge->edgeReason() == DataDependenceEdge::EDGE_OPERATION) {
            edgeDescriptors_[edge] = *ei;
            result.insert(edge);
        }
    }
    return result;
}

References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, BoostGraph< MoveNode, DataDependenceEdge >::edgeDescriptors_, BoostGraph< MoveNode, DataDependenceEdge >::graph_, and BoostGraph< MoveNode, DataDependenceEdge >::node().

Referenced by ExecutionPipelineBroker::isLoopBypass(), and BFPushMoveUp2::isLoopBypass().

Here is the call graph for this function:

◆ otherSuccessorsScheduled()

bool DataDependenceGraph::otherSuccessorsScheduled	(	MoveNode &	node,
		const NodeSet &	ignoredNodes
	)		const

Definition at line 3266 of file DataDependenceGraph.cc.

                                                                                               {
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    NodeDescriptor nd = descriptor(node);
    std::pair<OutEdgeIter, OutEdgeIter> edges =
    boost::out_edges(nd, graph_);
    
    for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge& edge = *graph_[ed];
        if (edge.isBackEdge()) {
            continue;
        }
        MoveNode* m = graph_[boost::target(ed, graph_)];
        if (!m->isPlaced()) {
            if (!AssocTools::containsKey(ignoredNodes, m)) {
                return false;
            }
        }
    }
    return true;
}

References AssocTools::containsKey(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, GraphEdge::isBackEdge(), MoveNode::isPlaced(), and BoostGraph< MoveNode, DataDependenceEdge >::node().

Referenced by BUMoveNodeSelector::isReadyToBeScheduled().

Here is the call graph for this function:

◆ predecessorsReady()

bool DataDependenceGraph::predecessorsReady ( MoveNode & node ) const

Checks whether the given node has all its predcessors scheduled.

Ignores intra operation edges, thus if the predecessors belongs to the same operation, it need not be scheduled for the node to be considered ready.

Returns: True in case all predecessors are scheduled.

Definition at line 3176 of file DataDependenceGraph.cc.

                                                           {
 
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    NodeDescriptor nd = descriptor(node);
    std::pair<InEdgeIter, InEdgeIter> edges =
        boost::in_edges(nd, graph_);
 
    bool srcOp = node.isSourceOperation();
    bool dstOp = node.isDestinationOperation();
 
    for (InEdgeIter ei = edges.first; ei != edges.second; ei++) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge& edge = *graph_[ed];
        if (edge.isBackEdge()) {
            continue;
        }
        const MoveNode& m = *graph_[boost::source(ed, graph_)];
 
        if (srcOp) {
            // operand move of same operation
            if ((m.isDestinationOperation() && 
                 &node.sourceOperation() == &m.destinationOperation()) ||
                (m.isSourceOperation() &&
                 &node.sourceOperation() == &m.sourceOperation())) {
                continue;
            }
        }
 
        if (dstOp && m.isDestinationOperation() &&
            &node.destinationOperation() == &m.destinationOperation()) {
            continue;
        } 
        if (!m.isPlaced()) {
            return false;
        }
    }
    return true;
 
}

References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), MoveNode::destinationOperation(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, GraphEdge::isBackEdge(), MoveNode::isDestinationOperation(), MoveNode::isPlaced(), MoveNode::isSourceOperation(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and MoveNode::sourceOperation().

Referenced by CriticalPathBBMoveNodeSelector::isReadyToBeScheduled().

Here is the call graph for this function:

◆ programOperation() [1/2]

ProgramOperation & DataDependenceGraph::programOperation ( int index )

Returs programoperation which is in this graph.

Parameters

index index of the programoperation.

Definition at line 227 of file DataDependenceGraph.cc.

                                               {
    return *programOperations_.at(index);
}

References programOperations_.

Referenced by BF2Scheduler::countLoopInvariantValueUsages(), PreOptimizer::handleCFGDDG(), and BF2Scheduler::reservePreallocatedFUs().

◆ programOperation() [2/2]

const ProgramOperation & DataDependenceGraph::programOperation ( int index ) const

Definition at line 232 of file DataDependenceGraph.cc.

                                                     {
    return *programOperations_.at(index);
}

References programOperations_.

◆ programOperationCount()

int DataDependenceGraph::programOperationCount ( ) const

Returns the number of programoperations in this ddg.

Definition at line 246 of file DataDependenceGraph.cc.

                                                 {
    return programOperations_.size();
}

References programOperations_.

Referenced by addProgramOperation(), BF2Scheduler::countLoopInvariantValueUsages(), PreOptimizer::handleCFGDDG(), and BF2Scheduler::reservePreallocatedFUs().

◆ programOperationPtr()

ProgramOperationPtr DataDependenceGraph::programOperationPtr ( int index )

Definition at line 237 of file DataDependenceGraph.cc.

                                                  {
    return programOperations_.at(index);
}

References programOperations_.

◆ queueRawPredecessors()

bool DataDependenceGraph::queueRawPredecessors	(	NodeSet &	queue,
		NodeSet &	finalDest,
		NodeSet &	predQueue,
		NodeSet &	predFinalDest,
		bool	guard
	)		const

private

Definition at line 4918 of file DataDependenceGraph.cc.

                                              {
 
    typedef EdgeSet::iterator EdgeIterator;
 
    // check one read.
    while (!queue.empty()) {
        MoveNode& read = **queue.begin();
 
        NodeDescriptor nd = descriptor(read);
        EdgeSet in = rootGraphInEdges(read);
 
        for (EdgeIterator j = in.begin(); j != in.end(); j++) {
            DataDependenceEdge& e = **j;
            
            if (e.dependenceType() == DataDependenceEdge::DEP_RAW &&
                e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
                e.guardUse() == guard) {
                MoveNode& pred = 
                    (static_cast<const DataDependenceGraph*>
                     (rootGraph()))->tailNode(e, nd);
                if (e.isBackEdge() || e.headPseudo() || 
                    e.tailPseudo() || !hasNode(pred)) {
                    return false;
                } else {
                    if (predFinalDest.find(&pred) == 
                        predFinalDest.end()) {
                        predQueue.insert(&pred);
                    }
                }
            }
        }
        // this is fully checked. add to result, remove from queue
        finalDest.insert(&read);
        queue.erase(&read);
    }
    return true;
}

Referenced by findLiveRange().

Here is the call graph for this function:

◆ rAntiEdgesIn()

int DataDependenceGraph::rAntiEdgesIn ( MoveNode & mn )

private

Counts all incoming antidependence edges to a movenode.

Parameters

mn	MoveNode whose edges we are counting

Returns: number of incoming antidependence edges.

Definition at line 4001 of file DataDependenceGraph.cc.

                                                  {
    EdgeSet iEdges = inEdges(mn);
    int count = 0;
    for (EdgeSet::iterator iter = 
             iEdges.begin(); iter != iEdges.end(); iter++) {
        if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            (((*iter)->dependenceType() == DataDependenceEdge::DEP_WAR) ||
            ((*iter)->dependenceType() == DataDependenceEdge::DEP_WAW))) {
            count++;
        }
    }
    return count;
}

References DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_REGISTER, and BoostGraph< MoveNode, DataDependenceEdge >::inEdges().

Here is the call graph for this function:

◆ regDepSiblings()

DataDependenceGraph::NodeSet DataDependenceGraph::regDepSiblings ( const MoveNode & mn ) const

Definition at line 5620 of file DataDependenceGraph.cc.

                                                            {
 
    NodeSet potentialSiblings;
    NodeSet siblings;
    NodeSet regDepSources;
 
    EdgeSet ins = inEdges(mn);
    int edgeCounter = 0;
    for (auto e: ins) {
        if ((e->edgeReason() != DataDependenceEdge::EDGE_REGISTER &&
             e->edgeReason() != DataDependenceEdge::EDGE_RA) ||
            e->headPseudo() || e->tailPseudo() || e->guardUse()) {
            continue;
        }
        edgeCounter++;
 
        MoveNode& tail = tailNode(*e);
        regDepSources.insert(&tail);
        const EdgeSet& outs = outEdges(tail);
        for (auto f: outs) {
            if ((f->edgeReason() != DataDependenceEdge::EDGE_REGISTER &&
                 f->edgeReason() != DataDependenceEdge::EDGE_RA) ||
                f->headPseudo() || f->tailPseudo() || f->guardUse()) {
                continue;
            }
            if (e != f && *e == *f) {
                MoveNode& head = headNode(*f);
                if (&head != &mn) {
                    potentialSiblings.insert(&head);
                }
            }
        }
    }
 
    for (auto n : potentialSiblings) {
        bool ok = true;
        EdgeSet ins2 = inEdges(*n);
        int edgeCounter2 = 0;
        for (auto e: ins2) {
            if ((e->edgeReason() != DataDependenceEdge::EDGE_REGISTER &&
                 e->edgeReason() != DataDependenceEdge::EDGE_RA) ||
                e->headPseudo() || e->tailPseudo() || e->guardUse()) {
                continue;
            }
 
            bool foundSame = false;
            const MoveNode& tail = tailNode(*e);
            for (auto f : ins) {
                if (*e == *f && &tailNode(*f) == &tail) {
                    foundSame = true;
                    break;
                }
            }
 
            // did not find similar edge from the inputs of the original node
            if (!foundSame) {
                ok = false;
                break;
            }
            edgeCounter2++;
        }
        if (ok && edgeCounter2 == edgeCounter) {
            siblings.insert(n);
        }
    }
    return siblings;
}

References DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::headNode(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by BFShareOperands::operator()().

Here is the call graph for this function:

◆ registerAndRAInEdges()

DataDependenceGraph::EdgeSet DataDependenceGraph::registerAndRAInEdges ( const MoveNode & node ) const

Definition at line 5930 of file DataDependenceGraph.cc.

                                                                    {
    std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
        descriptor(node), graph_);
 
    EdgeSet result;
 
    for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
        DataDependenceEdge* edge = graph_[(*ei)];
        if (edge->isRegisterOrRA()) {
            edgeDescriptors_[edge] = *ei;
            result.insert(edge);
        }
    }
    return result;
}

References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::edgeDescriptors_, BoostGraph< MoveNode, DataDependenceEdge >::graph_, and BoostGraph< MoveNode, DataDependenceEdge >::node().

Here is the call graph for this function:

◆ regRawPredecessors()

DataDependenceGraph::NodeSet DataDependenceGraph::regRawPredecessors	(	const MoveNode &	node,
		int	backedges = `0`
	)		const

Returns the register raw predecessors of the given node.

If node has no register raw predecessors, an empty set is returned. Note: the node can also be a predecessor of itself. Register raw predecessor means predecessor which is connected by register or ra raw edge

backEdges: 0: do not care 1: only backedges 2: no backedges

Parameters

node	The node of which successors to find.

Returns: Set of root nodes, can be empty.

Definition at line 4310 of file DataDependenceGraph.cc.

                                                                                 {
    
    NodeSet pred;
 
    NodeDescriptor nd = descriptor(node);
    EdgeSet in = inEdges(node);
    typedef EdgeSet::iterator EdgeIterator;
 
    for (EdgeIterator i = in.begin(); i != in.end(); ++i) {
        DataDependenceEdge& e = **i;
        if (backedges == 1 && !e.isBackEdge()) {
            continue;
        } else if (backedges == 2 && e.isBackEdge()) {
            continue;
        }
        if (e.dependenceType() == DataDependenceEdge::DEP_RAW &&
            (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
             e.edgeReason() == DataDependenceEdge::EDGE_RA)) {
            pred.insert(&tailNode(**i, nd));
        }
    }
    return pred;
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), DataDependenceEdge::isBackEdge(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().

Referenced by LoopAnalyzer::findInitAndUpdate().

Here is the call graph for this function:

◆ regRawSuccessorCount()

int DataDependenceGraph::regRawSuccessorCount	(	const MoveNode &	mn,
		bool	onlyScheduled
	)

Calculates number of register RAW dependecies originating from given node

Parameters

mn	Movenodes whose dependencies to calculate
onlySchedules	only care about dependencies to Scheduled nodes.

Returns: number of register RAW dependencies originating from given node

Definition at line 3952 of file DataDependenceGraph.cc.

                                            {
    int count = 0;
    EdgeSet oEdges = outEdges(mn);
    for (EdgeSet::iterator iter = 
             oEdges.begin(); iter != oEdges.end(); iter++) {
        if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            (*iter)->dependenceType() == DataDependenceEdge::DEP_RAW) {
            MoveNode& mn = headNode(**iter);
            if (!onlyScheduled || mn.isPlaced()) {
                count++;
            }
        }
    }
    return count;
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::headNode(), MoveNode::isPlaced(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().

Referenced by OffsetAliasAnalyzer::analyze(), CycleLookBackSoftwareBypasser::bypassNode(), and OffsetAliasAnalyzer::isAddressTraceable().

Here is the call graph for this function:

◆ regRawSuccessors()

DataDependenceGraph::NodeSet DataDependenceGraph::regRawSuccessors ( const MoveNode & node ) const

Returns the register raw successors of the given node.

If node has no register raw successors, an empty set is returned. Note: the node can also be a successor of itself. Register raw successor means successor which is connected by register or ra raw edge

Parameters

node	The node of which successors to find.

Returns: Set of root nodes, can be empty.

Definition at line 4272 of file DataDependenceGraph.cc.

                                                                {
    
    NodeSet succ;
 
    NodeDescriptor nd = descriptor(node);
    EdgeSet out = outEdges(node);
    typedef EdgeSet::iterator EdgeIterator;
 
    for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
        DataDependenceEdge& e = **i;
        if (e.dependenceType() == DataDependenceEdge::DEP_RAW &&
            (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
             e.edgeReason() == DataDependenceEdge::EDGE_RA)) {
            succ.insert(&headNode(**i, nd));
        }
    }
    
    return succ;
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().

Referenced by BasicBlockScheduler::tryToOptimizeWaw(), and BUBasicBlockScheduler::tryToOptimizeWaw().

Here is the call graph for this function:

◆ regWarSuccessors()

DataDependenceGraph::NodeSet DataDependenceGraph::regWarSuccessors ( const MoveNode & node ) const

Returns the register war successors of the given node.

If node has no register war successors, an empty set is returned. Note: the node can also be a successor of itself. Register war successor means successor which is connected by register or ra war edge

Parameters

node	The node of which successors to find.

Returns: Set of root nodes, can be empty.

Definition at line 4239 of file DataDependenceGraph.cc.

                                                                {
    
    NodeSet succ;
 
    NodeDescriptor nd = descriptor(node);
    EdgeSet out = outEdges(node);
    typedef EdgeSet::iterator EdgeIterator;
 
    for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
        DataDependenceEdge& e = **i;
        if (e.dependenceType() == DataDependenceEdge::DEP_WAR &&
            (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER ||
             e.edgeReason() == DataDependenceEdge::EDGE_RA)) {
            succ.insert(&headNode(**i, nd));
        }
    }
    
    return succ;
}

References DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().

Referenced by CycleLookBackSoftwareBypasser::bypassNode().

Here is the call graph for this function:

◆ regWawSuccessors()

DataDependenceGraph::NodeSet DataDependenceGraph::regWawSuccessors ( const MoveNode & node ) const

Returns the register waw successors of the given node.

If node has no reg waw successors, an empty set is returned. Note: the node can also be a successor of itself. register waw successor means successor which is connected by register waw edge.

Parameters

node	The node of which successors to find.

Returns: Set of root nodes, can be empty.

Definition at line 4347 of file DataDependenceGraph.cc.

                                                                {
    
    NodeSet succ;
 
    NodeDescriptor nd = descriptor(node);
    EdgeSet out = outEdges(node);
    typedef EdgeSet::iterator EdgeIterator;
 
    for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
        DataDependenceEdge& e = **i;
 
        // if we would bypass also over ra, then allow also ra in following
        if (e.dependenceType() == DataDependenceEdge::DEP_WAW &&
            e.edgeReason() == DataDependenceEdge::EDGE_REGISTER) {
            succ.insert(&headNode(**i, nd));
        }
    }
    
    return succ;
}

References DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().

Referenced by CycleLookBackSoftwareBypasser::removeDeadResults().

Here is the call graph for this function:

◆ removeIncomingGuardEdges()

void DataDependenceGraph::removeIncomingGuardEdges ( MoveNode & node )

Removes guard raw edges coming to some node.

This is called if the guard is removed from the node.

Parameters

node The node.

Definition at line 5466 of file DataDependenceGraph.cc.

                                                            {
    NodeDescriptor nd = descriptor(node);
    std::pair<InEdgeIter, InEdgeIter> edges =
        boost::in_edges(nd, graph_);
 
    // loop thru all edges
    for (InEdgeIter ei = edges.first; ei != edges.second; ) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge& edge = *graph_[ed];
        if (edge.guardUse() && edge.dependenceType() == 
            DataDependenceEdge::DEP_RAW) {
            boost::remove_edge(*ei, graph_);
 
            // removing messes up the iterator. start again from first.
            edges = boost::in_edges(nd, graph_);
            ei = edges.first;
        } else {
            ei++;
        }
    }
}

References DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and BoostGraph< MoveNode, DataDependenceEdge >::node().

Referenced by BUBasicBlockScheduler::scheduleMove(), BasicBlockScheduler::scheduleMove(), BasicBlockScheduler::tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), and BFOptimization::unsetJumpGuard().

Here is the call graph for this function:

◆ removeNode()

void DataDependenceGraph::removeNode ( MoveNode & node )

virtual

Removes MoveNode from graph and ProgramOperations.

Does not delete the movenode.

This does NOT update overgoing antideps - consider calling copyAntidepsOver(node); before calling this.

Parameters

node	MoveNode being removed.

Reimplemented from BoostGraph< MoveNode, DataDependenceEdge >.

Definition at line 2843 of file DataDependenceGraph.cc.

                                              {
    // remove move -> movenode mapping.
    if (node.isMove()) {
        TTAProgram::Move* move = &node.move();
        auto i = nodesOfMoves_.find(move);
        if (i != nodesOfMoves_.end()) {
            nodesOfMoves_.erase(i);
        } 
    }
 
    // remove node from program operations
    if (node.isMove()) {
        if (node.isSourceOperation()) {
            ProgramOperation& srcOp = node.sourceOperation();
            srcOp.removeOutputNode(node);
            node.unsetSourceOperation();
        }
 
        if (node.isDestinationOperation()) {
            for (int i = node.destinationOperationCount() - 1; i >= 0; i--) {
                ProgramOperation& dstOp = node.destinationOperation(i);
                dstOp.removeInputNode(node);
            }
            node.clearDestinationOperation();
        }
    }
    
//    copyAntidepsOver(node);
    
    // remove node from graph
    BoostGraph<MoveNode,DataDependenceEdge>::removeNode(node);
}

References BoostGraph< MoveNode, DataDependenceEdge >::node(), nodesOfMoves_, ProgramOperation::removeInputNode(), BoostGraph< GraphNode, GraphEdge >::removeNode(), and ProgramOperation::removeOutputNode().

Referenced by deleteNode(), MoveNodeDuplicator::disposeMoveNode(), CopyingDelaySlotFiller::loseCopies(), ControlFlowGraph::removeJumpToTarget(), ControlFlowGraph::removeUnreachableNodes(), CopyingDelaySlotFiller::unassignTempAssigns(), BFRegCopy::undoDDG(), CopyingDelaySlotFiller::updateFTBBAndCfg(), and CopyingDelaySlotFiller::updateJumpsAndCfg().

Here is the call graph for this function:

◆ removeOutgoingGuardWarEdges()

void DataDependenceGraph::removeOutgoingGuardWarEdges ( MoveNode & node )

Removes guard raw edges coming to some node.

This is called if the guard is removed from the node.

Parameters

node The node.

Definition at line 5496 of file DataDependenceGraph.cc.

                                                               {
    NodeDescriptor nd = descriptor(node);
    std::pair<OutEdgeIter, OutEdgeIter> edges =
        boost::out_edges(nd, graph_);
 
    // loop thru all edges
    for (OutEdgeIter ei = edges.first; ei != edges.second; ) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge& edge = *graph_[ed];
        if (edge.guardUse() && edge.dependenceType() == 
            DataDependenceEdge::DEP_WAR) {
            boost::remove_edge(*ei, graph_);
 
            // removing messes up the iterator. start again from first.
            edges = boost::out_edges(nd, graph_);
            ei = edges.first;
        } else {
            ei++;
        }
    }
}

References DataDependenceEdge::DEP_WAR, BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and BoostGraph< MoveNode, DataDependenceEdge >::node().

Referenced by BasicBlockScheduler::tryToOptimizeWaw(), and BUBasicBlockScheduler::tryToOptimizeWaw().

Here is the call graph for this function:

◆ removeRAWEdges()

TCEString DataDependenceGraph::removeRAWEdges	(	MoveNode &	sourceNode,
		MoveNode &	userNode
	)

Removes raw edged between nodes.

Returns the register associated with the raw dependency

Definition at line 1937 of file DataDependenceGraph.cc.

                                                                                      {
    
    TCEString regName;
    EdgeSet edges = connectingEdges(sourceNode, userNode);
 
    for (auto edge: edges) {
        if (edge->dependenceType() == DataDependenceEdge::DEP_RAW) {
            regName = edge->data();
            removeEdge(*edge, &sourceNode, &userNode);
        }
    }
 
    // there must have been a register raw edge between source and user node
    if (regName == "") {
        std::cerr << "Missing RAW edge between: " << sourceNode.toString()
                  << " and " << userNode.toString() << " on removeRawEdges."
                  << " Wrote missing_raw.dot" << std::endl;
        writeToDotFile("missing_raw.dot");
        assert(false);
    }
 
    return regName;
}

References assert, BoostGraph< MoveNode, DataDependenceEdge >::connectingEdges(), DataDependenceEdge::DEP_RAW, BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by guardConverted(), mergeAndKeepSource(), and mergeAndKeepUser().

Here is the call graph for this function:

◆ renamedSimpleLiveRange()

void DataDependenceGraph::renamedSimpleLiveRange	(	MoveNode &	src,
		MoveNode &	dest,
		MoveNode &	antidepPoint,
		DataDependenceEdge &	lrEdge,
		const TCEString &	oldReg,
		const TCEString &	newReg
	)

Definition at line 5182 of file DataDependenceGraph.cc.

                                                      {
    
    // if nothing changed, retuen
    if (oldReg == newReg) {
        return;
    }
 
    // copy antideps over these two nodes
    copyDepsOver(src, dest, true, false);
 
    NodeDescriptor ndADP = descriptor(antidepPoint);
    EdgeSet resultInEdges = inEdges(antidepPoint);
    EdgeSet firstInEdges = inEdges(src);
    EdgeSet firstOutEdges = outEdges(src);
    EdgeSet lastOutEdges = outEdges(dest);
 
    // move antideps coming to adeppoint into src
    for (EdgeSet::iterator i = resultInEdges.begin(); 
         i != resultInEdges.end(); i++) {
        DataDependenceEdge& e = **i;
        if (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !e.headPseudo() &&
            (e.dependenceType() == DataDependenceEdge::DEP_WAW ||
             e.dependenceType() == DataDependenceEdge::DEP_WAR)) {
            assert(e.data() == newReg);
            MoveNode& tail = tailNode(e, ndADP);
            // do not create loop.
            if (e.loopDepth() == 0 && &tail == &src) {
                removeEdge(e);
            } else {
                moveInEdge(antidepPoint, src, e);
            }
        }
    }
 
    DataDependenceEdge* warEdge = new DataDependenceEdge(
        DataDependenceEdge::EDGE_REGISTER,
        DataDependenceEdge::DEP_WAR,
        newReg, false, false, false, false, 0);
 
    DataDependenceEdge* wawEdge = new DataDependenceEdge(
        DataDependenceEdge::EDGE_REGISTER,
        DataDependenceEdge::DEP_WAW,
        newReg, false, false, false, false, 0);
 
    connectNodes(src, antidepPoint, *wawEdge);
    connectNodes(dest, antidepPoint, *warEdge);
 
    assert(connectingEdge.data() == oldReg);
    connectingEdge.setData(newReg);
 
    // remove antidep edges that were removed because of this renameing
    for (EdgeSet::iterator i = firstInEdges.begin(); 
         i != firstInEdges.end(); i++) {
        DataDependenceEdge& e = **i;
        if (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            (e.dependenceType() == DataDependenceEdge::DEP_WAW ||
             e.dependenceType() == DataDependenceEdge::DEP_WAR)) {
            removeEdge(e, NULL, &src);
        }
    }
 
    for (EdgeSet::iterator i = firstOutEdges.begin(); 
         i != firstOutEdges.end(); i++) {
        DataDependenceEdge& e = **i;
        if (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !e.tailPseudo() && e.data() == oldReg &&
            (e.dependenceType() == DataDependenceEdge::DEP_WAW ||
             e.dependenceType() == DataDependenceEdge::DEP_WAR)) {
            removeEdge(e, &src, NULL);
        }
    }
    for (EdgeSet::iterator i = lastOutEdges.begin(); 
         i != lastOutEdges.end(); i++) {
        DataDependenceEdge& e = **i;
        if (e.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !e.tailPseudo() && e.data() == oldReg &&
            (e.dependenceType() == DataDependenceEdge::DEP_WAW ||
             e.dependenceType() == DataDependenceEdge::DEP_WAR)) {
            removeEdge(e, &src, NULL);
        }
    }
}

Referenced by PreOptimizer::tryToOptimizeAddressReg().

Here is the call graph for this function:

◆ resultUsed() [1/2]

bool DataDependenceGraph::resultUsed ( MoveNode & resultNode )

Checks whether a result is used later or if the result move can be dropped.

Parameters

resultNode node being checked for nonused results.

Definition at line 2348 of file DataDependenceGraph.cc.

                                                    {
    return resultUsed(resultNode, NULL);
}

References resultUsed().

Referenced by BUBasicBlockScheduler::bypassNode(), CycleLookBackSoftwareBypasser::bypassNode(), BUBasicBlockScheduler::finalizeSchedule(), BUBasicBlockScheduler::handleDDG(), BUBasicBlockScheduler::handleLoopDDG(), resultUsed(), BUBasicBlockScheduler::scheduleResultReads(), BUBasicBlockScheduler::scheduleResultReadTempMoves(), and BUBasicBlockScheduler::scheduleRRTempMoves().

Here is the call graph for this function:

◆ resultUsed() [2/2]

bool DataDependenceGraph::resultUsed	(	MoveNode &	resultNode,
		MoveNode *	regCopy
	)

Checks whether a result is used later or if the result move can be dropped.

Parameters

resultNode	node being checked for nonused results.
regCopy	Register copy to be removed that might use the result

Definition at line 2360 of file DataDependenceGraph.cc.

                                                                       {
    //naming of this variabl si reverse logic, ok if not used
    bool killingWrite = true;
    if (!isRootGraphProcedureDDG()) {
        killingWrite = false;
    }
    bool hasRAW = false;
    bool hasOtherEdge = false;
    
    EdgeSet edges = rootGraphOutEdges(resultNode);
    EdgeSet::iterator edgeIter = edges.begin();
    while (edgeIter != edges.end()) {
 
        DataDependenceEdge& edge = *(*edgeIter);
        MoveNode& head = 
            (static_cast<const DataDependenceGraph*>
            (rootGraph()))->headNode(edge);
        if (regCopy != NULL && &head == regCopy) {
            edgeIter++;
            continue;
        }
 
        // don't case about operation edges.
        if (edge.edgeReason() == DataDependenceEdge::EDGE_OPERATION) {
            edgeIter++;
            continue;
        }
 
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER) {
            if (edge.dependenceType() == DataDependenceEdge::DEP_RAW) {
                // result is still going to be used
                hasRAW = true;
                break;
            }
 
            if (killingWrite == false) {
                // TODO: does this break if the waw dest unconditional?
                if (edge.dependenceType() == DataDependenceEdge::DEP_WAW &&
                    !edge.headPseudo()) {
                    if (head.isMove() && head.move().isUnconditional()) {
                        killingWrite = true;
                    }
                }
            }
 
        } else {
            // there are some other outgoing edges
            hasOtherEdge = true;
        }
        edgeIter++;
    }
    return (!killingWrite || hasRAW || hasOtherEdge );
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAW, BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_REGISTER, MoveNode::isMove(), isRootGraphProcedureDDG(), TTAProgram::Move::isUnconditional(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), and BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdges().

Here is the call graph for this function:

◆ rWarEdgesOut()

int DataDependenceGraph::rWarEdgesOut ( MoveNode & mn )

Calculates number of register WAR antidependecies originating from given node

Parameters

mn	Movenodes whose dependencies to calculate

Returns: number of register WAR antidependencies originating from given node

Definition at line 3930 of file DataDependenceGraph.cc.

                                                  {
    int count = 0;
    EdgeSet oEdges = outEdges(mn);
    for (EdgeSet::iterator iter = 
             oEdges.begin(); iter != oEdges.end(); iter++) {
        if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            (*iter)->dependenceType() == DataDependenceEdge::DEP_WAR) {
            count++;
        }
    }
    return count;
}

References DataDependenceEdge::DEP_WAR, DataDependenceEdge::EDGE_REGISTER, and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().

Referenced by RegisterCopyAdder::addConnectionRegisterCopies().

Here is the call graph for this function:

◆ rWawRawEdgesOutUncond()

bool DataDependenceGraph::rWawRawEdgesOutUncond ( MoveNode & mn )

private

Calculates number of register antidependecies originating from given node

Parameters

mn	Movenodes whose dependencies to calculate

Returns: number of register antidependencies originating from given node

Definition at line 3978 of file DataDependenceGraph.cc.

                                                            {
    EdgeSet oEdges = outEdges(mn);
    for (EdgeSet::iterator iter = 
             oEdges.begin(); iter != oEdges.end(); iter++) {
        if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            (((*iter)->dependenceType() == DataDependenceEdge::DEP_RAW) ||
            ((*iter)->dependenceType() == DataDependenceEdge::DEP_WAW))) {
            MoveNode& head = headNode(**iter);
            if (head.move().isUnconditional()) {
                return true;
            }
        }
    }
    return false;
 
}

References DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::headNode(), TTAProgram::Move::isUnconditional(), MoveNode::move(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().

Here is the call graph for this function:

◆ sameGuards()

bool DataDependenceGraph::sameGuards	(	const MoveNode &	mn1,
		const MoveNode &	mn2
	)		const

Definition at line 4506 of file DataDependenceGraph.cc.

                                                    {
    if (!mn1.isMove() || !mn2.isMove()) {
        return false;
    }
    const TTAProgram::Move& move1 = mn1.move();
    const TTAProgram::Move& move2 = mn2.move();
 
    if (move1.isUnconditional() && move2.isUnconditional()) {
        return true;
    }
 
    if (move1.isUnconditional() || move2.isUnconditional()) {
        return false;
    }
    TTAProgram::MoveGuard& mg1 = move1.guard();
    TTAProgram::MoveGuard& mg2 = move2.guard();
    if (mg1.isInverted() != mg2.isInverted()) {
        return false;
    }
    NodeSet incomingGuards1 =
        guardRawPredecessors(mn1);
 
    NodeSet incomingGuards2 = 
        guardRawPredecessors(mn2);
 
    return !incomingGuards1.empty() && 
        incomingGuards1 == incomingGuards2;
}

References TTAProgram::Move::guard(), guardRawPredecessors(), TTAProgram::MoveGuard::isInverted(), MoveNode::isMove(), TTAProgram::Move::isUnconditional(), and MoveNode::move().

Referenced by DataDependenceGraphBuilder::checkAndCreateMemAntideps(), DataDependenceGraphBuilder::createRegisterAntideps(), DataDependenceGraphBuilder::earlierWritesWithSameGuard(), DataDependenceGraphBuilder::hasEarlierMemWriteToSameAddressWithSameGuard(), and DataDependenceGraphBuilder::hasEarlierWriteWithSameGuard().

Here is the call graph for this function:

◆ sanityCheck()

void DataDependenceGraph::sanityCheck ( ) const

Checks that the DDG is sane.

Goes through all edges in the DDG and ensures they make sense, for example, in case of R_RAW, the head should really read the register written by the tail.

Exceptions

In	case the graph contains failures. Exception message contains the reason.

Definition at line 1399 of file DataDependenceGraph.cc.

                                       {
    for (int i = 0; i < edgeCount(); ++i) {
        DataDependenceEdge& e = edge(i);
        MoveNode& tail = tailNode(e);
        const TTAProgram::Terminal& tailSource = tail.move().source();
        const TTAProgram::Terminal& tailDestination = tail.move().destination();
 
        MoveNode& head = headNode(e);
        const TTAProgram::Terminal& headSource = head.move().source();
        const TTAProgram::Terminal& headDestination = head.move().destination();
 
        switch (e.dependenceType()) {
        case DataDependenceEdge::DEP_UNKNOWN:
            if (tailDestination.isFUPort() && headSource.isFUPort())
                break; // operation dependency is marked with DEP_UNKNOWN
            throw Exception(
                __FILE__, __LINE__, __func__,
                ((boost::format(
                      "DEP_UNKNOWN in edge between %s and %s."))
                 % tail.toString() % head.toString()).str());
            break;
        case DataDependenceEdge::DEP_RAW:
            // the normal case
            if (tailDestination.equals(headSource))
                break;
 
            // memory RAW
            if (e.edgeReason() == DataDependenceEdge::EDGE_MEMORY &&
                tailDestination.isFUPort() && 
                tailDestination.hintOperation().writesMemory() &&
                headDestination.isFUPort() &&
                headDestination.hintOperation().readsMemory())
                break;
 
            // W:gcu.ra R:ra
            if (tailDestination.isFUPort() &&
                &tailDestination.functionUnit() == 
                tailDestination.functionUnit().machine()->controlUnit() && 
                headSource.isFUPort())
                break;
 
            // tail writes a reg the head is guarded with 
            if (!head.move().isUnconditional() && tailDestination.isGPR() && 
                dynamic_cast<const TTAMachine::RegisterGuard*>(
                    &head.move().guard().guard()) != NULL) {
                const TTAMachine::RegisterGuard& g =
                    dynamic_cast<const TTAMachine::RegisterGuard&>(
                        head.move().guard().guard());
                if (g.registerFile() == &tailDestination.registerFile())
                    break; // TODO: check also the register index
            }
 
            // return value register on procedure return
            if (tailDestination.isGPR() &&
                headDestination.isFUPort() && 
                head.move().isControlFlowMove())
                break;
 
            writeToDotFile("faulty_raw_ddg.dot");
            throw Exception(
                __FILE__, __LINE__, __func__,
                ((boost::format(
                      "DEP_RAW in edge between %s and %s."))
                 % tail.toString() % head.toString()).str());
            break;
        case DataDependenceEdge::DEP_WAR:
            if (headDestination.equals(tailSource))
                break;
 
            // memory WAR
            if (e.edgeReason() == DataDependenceEdge::EDGE_MEMORY &&
                tailDestination.isFUPort() && 
                tailDestination.hintOperation().readsMemory() &&
                headDestination.isFUPort() &&
                headDestination.hintOperation().writesMemory())
                break;
            
            // memory WAR between memory op and call
            if (e.edgeReason() == DataDependenceEdge::EDGE_MEMORY &&
                tailDestination.isFUPort() && 
                tailDestination.hintOperation().readsMemory() &&
                headDestination.isFUPort() &&
                head.move().isFunctionCall())
                break;
            
            // call parameter register
            if (tailDestination.isFUPort() &&
                tailSource.isGPR() &&
                head.move().isFunctionCall())
                break;
 
            // return value register has WaR to 'call'
            // no better heuristics yet as we don't know the register RV is
            // mapped to
            if (tailSource.isGPR() && head.move().isFunctionCall())
                break; 
 
            // a use (probably a store) of RA has a WaR to 'call'
            if (tailSource.isFUPort() && head.move().isFunctionCall())
                break;
 
            writeToDotFile("faulty_war_ddg.dot");
            throw Exception(
                __FILE__, __LINE__, __func__,
                ((boost::format(
                      "DEP_WAR in edge between %s and %s."))
                 % tail.toString() % head.toString()).str());
            break;
        case DataDependenceEdge::DEP_WAW:
            if (headDestination.equals(tailDestination))
                break;
 
            // memory WAW - can also point to call?
            if (e.edgeReason() == DataDependenceEdge::EDGE_MEMORY &&
                tailDestination.isFUPort() && 
                (tailDestination.hintOperation().writesMemory() &&
                ((headDestination.isFUPort() &&
                  headDestination.hintOperation().writesMemory()) ||
                 (headDestination.isFUPort() &&
                  head.move().isFunctionCall()))))
                break;
 
            // memory WAW between memory op and call
            if (e.edgeReason() == DataDependenceEdge::EDGE_MEMORY &&
                tailDestination.isFUPort() && 
                tailDestination.hintOperation().writesMemory() &&
                headDestination.isFUPort() &&
                head.move().isFunctionCall())
                break;
 
            // function parameter registers
            if (tailDestination.isGPR() &&
                headDestination.isFUPort() && 
                head.move().isFunctionCall())
                break;
 
            writeToDotFile("faulty_waw_ddg.dot");
            throw Exception(
                __FILE__, __LINE__, __func__,
                ((boost::format(
                      "DEP_WAW in edge between %s and %s."))
                 % tail.toString() % head.toString()).str());
            break;
        default:
            throw Exception(
                __FILE__, __LINE__, __func__,
                ((boost::format(
                      "Unknown edge type: %d in edge between %s and %s."))
                 % e.dependenceType() % tail.toString() % head.toString()).
                str());
        }
    }
}

References __func__, TTAMachine::Machine::controlUnit(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_UNKNOWN, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_MEMORY, BoostGraph< MoveNode, DataDependenceEdge >::edgeCount(), DataDependenceEdge::edgeReason(), TTAProgram::Terminal::equals(), TTAProgram::Terminal::functionUnit(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), TTAProgram::Terminal::hintOperation(), TTAProgram::Move::isControlFlowMove(), TTAProgram::Move::isFunctionCall(), TTAProgram::Terminal::isFUPort(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isUnconditional(), TTAMachine::Component::machine(), MoveNode::move(), Operation::readsMemory(), TTAMachine::RegisterGuard::registerFile(), TTAProgram::Terminal::registerFile(), TTAProgram::Move::source(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), MoveNode::toString(), Operation::writesMemory(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by BasicBlockScheduler::scheduleOperation(), and BasicBlockScheduler::scheduleRRMove().

Here is the call graph for this function:

◆ scheduledMoves()

DataDependenceGraph::NodeSet DataDependenceGraph::scheduledMoves ( ) const

Returns all scheduled moves.

Parameters

cycle The cycle.

Returns: Scheduled moves.

Definition at line 1375 of file DataDependenceGraph.cc.

                                          {
 
    NodeSet moves;
    int nodeCounter = nodeCount();
    for (int i = 0; i < nodeCounter; ++i) {
        Node& n = node(i);
        if (n.isPlaced())
            moves.insert(&n);
    }
 
    return moves;
}

References MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().

Referenced by ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage(), BasicBlockScheduler::unscheduleAllNodes(), and BUBasicBlockScheduler::unscheduleAllNodes().

Here is the call graph for this function:

◆ scheduledNodeCount()

int DataDependenceGraph::scheduledNodeCount ( ) const

Returns the count of nodes in the graph that have been scheduled.

Current implementation is quite slow, so don't call in critical places.

Returns: The count of scheduled nodes.

Definition at line 1859 of file DataDependenceGraph.cc.

                                              {
 
    int scheduledCount = 0;
    for (int i = 0; i < nodeCount(); ++i) {
        Node& n = node(i);
        if (n.isPlaced()) 
            ++scheduledCount;
    }
 
    return scheduledCount;
}

References MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().

Referenced by BUMoveNodeSelector::candidates(), CriticalPathBBMoveNodeSelector::candidates(), BUBasicBlockScheduler::handleDDG(), BasicBlockScheduler::handleDDG(), BF2Scheduler::handleLoopDDG(), BasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), CriticalPathBBMoveNodeSelector::isReadyToBeScheduled(), BF2Scheduler::scheduleDDG(), BasicBlockScheduler::scheduleMove(), and BUBasicBlockScheduler::unscheduleAllNodes().

Here is the call graph for this function:

◆ setBasicBlockNode()

void DataDependenceGraph::setBasicBlockNode	(	const MoveNode &	mn,
		BasicBlockNode &	bbn
	)

Definition at line 216 of file DataDependenceGraph.cc.

                                             {
    moveNodeBlocks_[&mn] = &bbn;
}

References moveNodeBlocks_.

Referenced by ControlFlowGraph::mergeNodes().

◆ setCycleGrouping()

void DataDependenceGraph::setCycleGrouping ( bool flag )

virtual

Sets the "cycle grouping" mode of the Dot printout.

If set, moves are grouped according to their scheduled cycles (if any).

Definition at line 1738 of file DataDependenceGraph.cc.

                                               {
    cycleGrouping_ = flag;
}

References cycleGrouping_.

Referenced by BUMoveNodeSelector::BUMoveNodeSelector(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), CriticalPathBBMoveNodeSelector::notifyScheduled(), BasicBlockScheduler::scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), BasicBlockScheduler::scheduleRRMove(), and BUBasicBlockScheduler::scheduleRRMove().

◆ setEdgeWeightHeuristics()

void DataDependenceGraph::setEdgeWeightHeuristics ( EdgeWeightHeuristics ewh )

Definition at line 5716 of file DataDependenceGraph.cc.

                                                                          {
    if (edgeWeightHeuristics_ != ewh) {
        // force path recalculation
        height_ = -1; 
        sourceDistances_.clear();
        sinkDistances_.clear();
        // nullify edge weights to recalc them
        typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
        EdgeIterPair edges = boost::edges(graph_);
        for (EdgeIter i = edges.first; i != edges.second; i++) {
            GraphEdge* e = graph_[*i];
            e->setWeight(-1);
        }
    }
    edgeWeightHeuristics_ = ewh;
}

References edgeWeightHeuristics_, BoostGraph< MoveNode, DataDependenceEdge >::graph_, BoostGraph< MoveNode, DataDependenceEdge >::height_, GraphEdge::setWeight(), BoostGraph< MoveNode, DataDependenceEdge >::sinkDistances_, and BoostGraph< MoveNode, DataDependenceEdge >::sourceDistances_.

Referenced by ResourceConstraintAnalyzer::analyze(), ResourceConstraintAnalyzer::analyzeRegisterAntideps(), ResourceConstraintAnalyzer::dumpGraphWithStats(), ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage(), and ResourceConstraintAnalyzer::optimalScheduleResourceUsage().

Here is the call graph for this function:

◆ setMachine()

void DataDependenceGraph::setMachine ( const TTAMachine::Machine & machine )

Sets a machine into DDG.

This machine is used to some heuristics and helper functions that selector uses, for example path length calculation and earliestCycle.

If no machine is set, these functions will still work but will give non-optimal results.

Parameters

machine machine to be used for heristics

Definition at line 3116 of file DataDependenceGraph.cc.

                                                                {
 
    if (machine_ == &machine) {
        return;
    }
 
    // nullify edge weights to recalc them
    typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::edges(graph_);
    for (EdgeIter i = edges.first; i != edges.second; i++) {
        GraphEdge* e = graph_[*i];
        e->setWeight(-1);
    }
 
    machine_ = &machine;
    delaySlots_ = machine.controlUnit()->delaySlots();
    MachineAnalysis ma(machine);
 
    if (&machine == &UniversalMachine::instance()) {
        rrCost_ = 3;
    } else {
    // heuristic value about connectivity delays.
    rrCost_ = int(
        std::max(2.0,
                 3.0*((3-ma.bypassability()-(ma.connectivity()*2)))));
    }
    const TTAMachine::Machine::FunctionUnitNavigator& fuNav = 
        machine.functionUnitNavigator();
 
    operationLatencies_.clear();
    for (int i = 0; i < fuNav.count(); i++) {
        const TTAMachine::FunctionUnit* fu = fuNav.item(i);
        for (int j = 0; j < fu->operationCount(); j++) {
            TTAMachine::HWOperation* hwop = fu->operation(j);
            int latency = hwop->latency();
            TCEString name = StringTools::stringToUpper(hwop->name());
            // if does not exist or is existing is bigger update
            if (!AssocTools::containsKey(operationLatencies_, name)
                || latency < operationLatencies_[name]) {
                operationLatencies_[name] = latency;
            }
        }
    }
    height_ = -1; // force path recalculation
    sourceDistances_.clear();
    sinkDistances_.clear();
    loopingSinkDistances_.clear();
    loopingSourceDistances_.clear();
}

References MachineAnalysis::bypassability(), MachineAnalysis::connectivity(), AssocTools::containsKey(), TTAMachine::Machine::controlUnit(), TTAMachine::Machine::Navigator< ComponentType >::count(), TTAMachine::ControlUnit::delaySlots(), delaySlots_, TTAMachine::Machine::functionUnitNavigator(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, BoostGraph< MoveNode, DataDependenceEdge >::height_, UniversalMachine::instance(), TTAMachine::Machine::Navigator< ComponentType >::item(), TTAMachine::HWOperation::latency(), BoostGraph< MoveNode, DataDependenceEdge >::loopingSinkDistances_, BoostGraph< MoveNode, DataDependenceEdge >::loopingSourceDistances_, machine(), machine_, BoostGraph< MoveNode, DataDependenceEdge >::name(), TTAMachine::HWOperation::name(), TTAMachine::FunctionUnit::operation(), TTAMachine::FunctionUnit::operationCount(), operationLatencies_, rrCost_, GraphEdge::setWeight(), BoostGraph< MoveNode, DataDependenceEdge >::sinkDistances_, BoostGraph< MoveNode, DataDependenceEdge >::sourceDistances_, and StringTools::stringToUpper().

Referenced by DataDependenceGraphBuilder::build(), DataDependenceGraphBuilder::build(), BUMoveNodeSelector::BUMoveNodeSelector(), BUMoveNodeSelector::BUMoveNodeSelector(), BUMoveNodeSelector::BUMoveNodeSelector(), createSubgraph(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), criticalPathGraph(), BF2Scheduler::handleLoopDDG(), memoryDependenceGraph(), BF2Scheduler::scheduleDDG(), and trueDependenceGraph().

Here is the call graph for this function:

◆ setNodeBB()

void DataDependenceGraph::setNodeBB	(	MoveNode &	mn,
		BasicBlockNode &	bblock,
		DataDependenceGraph *	modifier
	)

Sets bookkeeping that the given movende belongs to the given basic block.

Parameters

mn	MoveNode given
bblock	Basic Block node where the move node belongs
modifier	modifier graph on the subgraph tree

Definition at line 119 of file DataDependenceGraph.cc.

                                                                         {
    moveNodeBlocks_[&mn] = &bblock;
    
    if (parentGraph_ != NULL && parentGraph_ != modifier) {
        static_cast<DataDependenceGraph*>(parentGraph_)->
            setNodeBB(mn, bblock, this);
    }
 
    for (unsigned int i = 0; i < childGraphs_.size(); i++) {
        if ( childGraphs_[i] != modifier ) {
            static_cast<DataDependenceGraph*>(childGraphs_[i])->
                setNodeBB(mn,bblock,this);
        }
    }
}

References BoostGraph< MoveNode, DataDependenceEdge >::childGraphs_, moveNodeBlocks_, BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, and setNodeBB().

Referenced by addNode(), addNode(), and setNodeBB().

Here is the call graph for this function:

◆ setProgramOperationNodes()

virtual void DataDependenceGraph::setProgramOperationNodes ( bool flag )

inlinevirtual

Definition at line 224 of file DataDependenceGraph.hh.

                                                     {
        dotProgramOperationNodes_ = flag;
    }

References dotProgramOperationNodes_.

Referenced by ResourceConstraintAnalyzer::analyze(), and ResourceConstraintAnalyzer::analyzePreSchedule().

◆ smallestCycle()

int DataDependenceGraph::smallestCycle ( ) const

Returns the smallest cycle of a move in the DDG.

Current implementation is quite slow, so don't call in critical places.

Returns: The smallest cycle of a move.

Definition at line 1818 of file DataDependenceGraph.cc.

                                         {
 
    int minCycle = INT_MAX;
    for (int i = 0; i < nodeCount(); ++i) {
        Node& n = node(i);
        if (n.isPlaced())
            minCycle = std::min(minCycle, n.cycle());
    }
 
    return minCycle;
}

References MoveNode::cycle(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().

Referenced by ResourceConstraintAnalyzer::analyzeRegisterAntideps(), dotString(), BBSchedulerController::executeDDGPass(), and BUBasicBlockScheduler::handleLoopDDG().

Here is the call graph for this function:

◆ sourceRenamed()

DataDependenceGraph::UndoData DataDependenceGraph::sourceRenamed ( MoveNode & mn )

Source of a move is renamed to a register which is not used in this ddg. Removes old edges not needed anymore.

If destination of edge also renamed to this reg, keep the edge, update the data of the edge.

Parameters

mn	MoveNode whose source or guard is renamed.
guard	true if renamed gaurd, not source.

Definition at line 4970 of file DataDependenceGraph.cc.

                                               {
 
    UndoData undoData;
 
    TTAProgram::Terminal& term = mn.move().source();
    const TCEString newReg = DisassemblyRegister::registerName(term);
 
    for (int i = 0; i < outDegree(mn); i++) {
        DataDependenceEdge& oEdge = outEdge(mn,i);
    
        if (oEdge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            oEdge.dependenceType() == DataDependenceEdge::DEP_WAR &&
            !oEdge.tailPseudo() && !oEdge.guardUse()) {
 
            MoveNode& head = headNode(oEdge);
            TTAProgram::Terminal& writeTerm = head.move().destination();
 
            // if this edge disappers because of the renaming?
            if (oEdge.headPseudo() ||
                (writeTerm.isGPR() && (
                     writeTerm.index() != term.index() ||
                     &writeTerm.registerFile() != &term.registerFile()))) {
                undoData.removedEdges.insert(RemovedEdgeDatum(mn, head, oEdge));
                removeEdge(oEdge, NULL, &mn);
                i--; // don't skip one edge here!
            } else {
                // update the edge. also other end changed
                undoData.changedDataEdges[&oEdge] = oEdge.data();
                oEdge.setData(newReg);
            }
        }
    }
    return undoData;
}

References DataDependenceGraph::UndoData::changedDataEdges, DataDependenceEdge::data(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), BoostGraph< MoveNode, DataDependenceEdge >::outEdge(), TTAProgram::Terminal::registerFile(), DisassemblyRegister::registerName(), DataDependenceGraph::UndoData::removedEdges, BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), DataDependenceEdge::setData(), TTAProgram::Move::source(), and DataDependenceEdge::tailPseudo().

Referenced by BFRenameLiveRange::renameLiveRange(), and RegisterRenamer::renameLiveRange().

Here is the call graph for this function:

◆ successorsReady()

bool DataDependenceGraph::successorsReady ( MoveNode & node ) const

Checks whether the given node has all its successors scheduled.

Ignores intra operation edges, thus if the successor belongs to the same operation, it need not be scheduled for the node to be considered ready.

Returns: True in case all successors are scheduled.

Definition at line 3228 of file DataDependenceGraph.cc.

                                                         {
    
    // use the internal data structures to make this fast.
    // edgeset has too much set overhead,
    // inedge(n,i) is O(n^2) , this is linear with no overhead
    NodeDescriptor nd = descriptor(node);
    std::pair<OutEdgeIter, OutEdgeIter> edges =
    boost::out_edges(nd, graph_);
    
    for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
        EdgeDescriptor ed = *ei;
        DataDependenceEdge& edge = *graph_[ed];
        if (edge.isBackEdge()) {
            continue;
        }
        const MoveNode& m = *graph_[boost::target(ed, graph_)];
        
        const bool operandMoveOfSameOperation =
        (node.isDestinationOperation() && m.isSourceOperation() && 
         &node.destinationOperation() == &m.sourceOperation());
        const bool resultMoveOfSameOperation = 
        (node.isSourceOperation() && m.isSourceOperation() &&
         &node.sourceOperation() == &m.sourceOperation());
        const bool operandsOfSameOperation =
        (node.isDestinationOperation() && m.isDestinationOperation() &&
         &node.destinationOperation() == &m.destinationOperation());
        if (operandMoveOfSameOperation || resultMoveOfSameOperation ||
            operandsOfSameOperation) {
            continue;
        } 
        if (!m.isPlaced()) {
            return false;
        }
    }
    return true;
}

References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), MoveNode::destinationOperation(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, GraphEdge::isBackEdge(), MoveNode::isDestinationOperation(), MoveNode::isPlaced(), MoveNode::isSourceOperation(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and MoveNode::sourceOperation().

Here is the call graph for this function:

◆ trueDependenceGraph()

DataDependenceGraph * DataDependenceGraph::trueDependenceGraph	(	bool	removeMemAntideps = `true`,
		bool	ignoreMemDeps = `false`
	)

Returns a version of the graph with only true dependence edges.

Definition at line 3417 of file DataDependenceGraph.cc.

                                                {
    DataDependenceGraph* subGraph = 
        new DataDependenceGraph(
            allParamRegs_, "true DDG", registerAntidependenceLevel_,
            NULL, false, false);
    NodeSet nodes;
    for (int i = 0; i < nodeCount(); ++i) {
        nodes.insert(&node(i));
    }
    if (machine_ != NULL)
        subGraph->setMachine(*machine_);
 
    constructSubGraph(*subGraph, nodes);
    
    for (int i = 0; i < nodeCount(); i++) {
        MoveNode& tail = node(i);
        for (int e = 0; e < subGraph->outDegree(tail);) {
            DataDependenceEdge& edge = subGraph->outEdge(tail,e);
            if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
                isNotAvoidable(edge)) {
                e++;
                continue;
            }
            // consider the memory dependencies
            if (edge.edgeReason() == DataDependenceEdge::EDGE_MEMORY &&
                (ignoreMemDeps || (edge.isFalseDep() && removeMemAntideps))) {
                subGraph->dropEdge(edge);
            } else {
                e++;
            }
        }
    }
    return subGraph;
}

References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), BoostGraph< GraphNode, GraphEdge >::dropEdge(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_MEMORY, DataDependenceEdge::EDGE_REGISTER, isNotAvoidable(), machine_, BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), BoostGraph< GraphNode, GraphEdge >::outDegree(), BoostGraph< GraphNode, GraphEdge >::outEdge(), registerAntidependenceLevel_, and setMachine().

Referenced by ResourceConstraintAnalyzer::analyzeRegisterAntideps().

Here is the call graph for this function:

◆ undo()

void DataDependenceGraph::undo ( UndoData & undoData )

Definition at line 5898 of file DataDependenceGraph.cc.

                                                 {
    for (auto i : undoData.changedDataEdges) {
        i.first->setData(i.second);
    }
 
    for (auto i: undoData.removedEdges) {
        connectNodes(i.nTail, i.nHead, i.edge);
    }
 
    for (auto i: undoData.newEdges) {
        removeEdge(*i);
    }
}

References DataDependenceGraph::UndoData::changedDataEdges, BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceGraph::UndoData::newEdges, DataDependenceGraph::UndoData::removedEdges, and BoostGraph< MoveNode, DataDependenceEdge >::removeEdge().

Referenced by BFRenameLiveRange::undoOnlyMe().

Here is the call graph for this function:

◆ unMergeUser()

void DataDependenceGraph::unMergeUser	(	MoveNode &	sourceNode,
		MoveNode &	mergedNode,
		bool	loopBypass = `false`
	)

Reverses work done by mergeAndKeep routine

changes node to read it's data from register and returns the original edges.

Parameters

sourceNode	node which writes to the register mergedNode should read.
mergedNode	node being changed

Definition at line 2240 of file DataDependenceGraph.cc.

                                                                                            {
 
 
    // name of the bypass reg.
    TTAProgram::Terminal& dest = sourceNode.move().destination();
    assert(dest.isGPR());
    TCEString regName = DisassemblyRegister::registerName(dest);
 
    // if this is not rootgraph, do it there. allows this to work even if
    // source node being deleted from this this sub-ddg.
    if (rootGraph() != this) {
        static_cast<DataDependenceGraph*>(rootGraph())->
            unMergeUser(sourceNode, mergedNode, loopBypass);
        if (loopBypass) {
            fixAntidepsAfterLoopUnmergeUser(sourceNode, mergedNode, regName);
        }
        return;
    } 
 
    // unset programoperation from bypassed
    if (mergedNode.isSourceOperation()) {
        ProgramOperation& srcOp = mergedNode.sourceOperation();
        srcOp.removeOutputNode(mergedNode);
        mergedNode.unsetSourceOperation();
 
        // unset fu annotations
        mergedNode.move().removeAnnotations(TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_SRC);
        mergedNode.move().removeAnnotations(TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC);
        mergedNode.move().removeAnnotations(TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC);
    }
 
    // All incoming RAW and operation dependencies were created by
    // the bypassing, originally there was just one RAW edge which was removed.
    // so remove the incoming edges merge routine copied to here.
    // these can be operation edges or ordinary register RaWs.
    // these should only go to source node.
    for (int i = 0; i < inDegree(mergedNode); i++) {
        DataDependenceEdge& edge = inEdge(mergedNode,i);
        // removes operation edges and 
        if (edge.edgeReason() == DataDependenceEdge::EDGE_OPERATION ||
            (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
             edge.dependenceType() == DataDependenceEdge::DEP_RAW &&
             !edge.headPseudo() && !edge.guardUse())) {
            removeEdge(edge, NULL, &mergedNode);
            i--; // do not skip next edge which now has same index
        } 
    }
 
    // do the actual unmerge by returning source to original register.
    mergedNode.move().setSource(sourceNode.move().destination().copy());
 
    bool nodeRegToItselfCopy = false;
    if (mergedNode.move().source().equals(mergedNode.move().destination())) {
        nodeRegToItselfCopy = true;
    }
 
    // create register edge between nodes.
    // this was removed by the merge.
    DataDependenceEdge* dde = new DataDependenceEdge(
        DataDependenceEdge::EDGE_REGISTER,
        DataDependenceEdge::DEP_RAW, regName,
        false, false, false, false, loopBypass);
    connectNodes(sourceNode, mergedNode, *dde);
 
    // remove war antidependence edges that should 
    // come from source. these should only come from the
    if (sourceNode.isSourceVariable()) {
        for( int i = 0; i < outDegree(mergedNode); i++) {
            DataDependenceEdge& edge = outEdge(mergedNode,i);
            if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
                edge.dependenceType() == DataDependenceEdge::DEP_WAR &&
                edge.data() != regName && !edge.tailPseudo() &&
                !edge.guardUse()) {
                removeEdge(edge, &mergedNode, NULL);
                i--; // do not skip next edge which now has same index
            }
        }
    }
 
    // All all outgoing WAR's to merged node. The war's go to 
    // all same places where WAW's fo from source node.
    for (int i = 0; i < outDegree(sourceNode); i++) {
        DataDependenceEdge& edge = outEdge(sourceNode,i);
        if (edge.edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            edge.dependenceType() == DataDependenceEdge::DEP_WAW &&
            edge.data() == regName) {
            MoveNode& dest = headNode(edge);
            // skip nodes with exclusive guard.
            if (!exclusingGuards(dest, mergedNode)) {
                DataDependenceEdge* newEdge = new DataDependenceEdge(
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAR, regName, false, false,
                    false, edge.headPseudo(), edge.loopDepth() - loopBypass + 
                    nodeRegToItselfCopy);
                connectNodes(mergedNode, dest, *newEdge);
            }
        }
    }
}

Referenced by CycleLookBackSoftwareBypasser::bypassNode(), CycleLookBackSoftwareBypasser::removeBypass(), BUBasicBlockScheduler::undoBypass(), unMergeUser(), and BUBasicBlockScheduler::unscheduleAllNodes().

Here is the call graph for this function:

◆ unscheduledMoves()

DataDependenceGraph::NodeSet DataDependenceGraph::unscheduledMoves ( ) const

Returns all unscheduled moves.

Parameters

cycle The cycle.

Returns: Unscheduled moves.

Definition at line 1355 of file DataDependenceGraph.cc.

                                            {
 
    NodeSet moves;
    int nodeCounter = nodeCount();
    for (int i = 0; i < nodeCounter; ++i) {
        Node& n = node(i);
        if (!n.isPlaced())
            moves.insert(&n);
    }
 
    return moves;
}

References MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().

Referenced by BUMoveNodeSelector::candidates(), CriticalPathBBMoveNodeSelector::candidates(), CriticalPathBBMoveNodeSelector::isReadyToBeScheduled(), and BasicBlockScheduler::scheduleMove().

Here is the call graph for this function:

◆ updateRegUse()

void DataDependenceGraph::updateRegUse	(	const MoveNodeUse &	mnd,
		const TCEString &	reg,
		TTAProgram::BasicBlock &	bb
	)

Creates dependencies from incoming definitions in other BB's to a reg use.

Parameters

mnd	data about the register usage.

Definition at line 5367 of file DataDependenceGraph.cc.

                                                                            {
 
    // create RAW's from definitions in previous BBs.
    std::set<MoveNodeUse>& defReaches = 
        bb.liveRangeData_->regDefReaches_[reg];
    for (std::set<MoveNodeUse>::iterator i = defReaches.begin();
         i != defReaches.end(); i++) {
 
        const MoveNodeUse& source = *i;
        if (hasNode(*source.mn())) {
            DataDependenceEdge* dde =
                // create dependency edge
                new DataDependenceEdge(
                    mnd.ra() ? DataDependenceEdge::EDGE_RA :
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_RAW, reg, mnd.guard(), false, 
                    source.pseudo(), mnd.pseudo(), source.loop());
 
            // and connect.
            connectOrDeleteEdge(*source.mn(), *mnd.mn(), dde);
        }
    }
}

References connectOrDeleteEdge(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, MoveNodeUse::guard(), BoostGraph< MoveNode, DataDependenceEdge >::hasNode(), TTAProgram::BasicBlock::liveRangeData_, MoveNodeUse::loop(), MoveNodeUse::mn(), MoveNodeUse::pseudo(), MoveNodeUse::ra(), and LiveRangeData::regDefReaches_.

Referenced by DataDependenceGraphBuilder::constructIndividualFromInlineAsmBB(), DataDependenceGraphBuilder::processRegUse(), and DataDependenceGraphBuilder::updateBB().

Here is the call graph for this function:

◆ updateRegWrite()

DataDependenceGraph::EdgeSet DataDependenceGraph::updateRegWrite	(	const MoveNodeUse &	mnd,
		const TCEString &	reg,
		TTAProgram::BasicBlock &	bb
	)

Creates dependencies to a register write from MN's in other BBs.

Parameters

mnd	movenode which writes to a register
reg	register wrere the movenode writes to
createAllAntideps	whether to create antideps from all BB's or just from same bb in case of single-bb loop.

Definition at line 5401 of file DataDependenceGraph.cc.

                                                                            {
    // WaWs
 
    DataDependenceGraph::EdgeSet addedEdges;
 
    std::set<MoveNodeUse>& defReaches = 
        bb.liveRangeData_->regDefReaches_[reg];
    for (std::set<MoveNodeUse>::iterator i = defReaches.begin();
         i != defReaches.end(); i++) {
 
        const MoveNodeUse& source = *i;
        if (hasNode(*source.mn()) && source.mn()->isMove() &&
            (hasAllRegisterAntidependencies() || 
             &getBasicBlockNode(*source.mn()) == 
             &getBasicBlockNode(*mnd.mn()))) {
            // create dependency edge
            DataDependenceEdge* dde =
                new DataDependenceEdge(
                    mnd.ra() ? DataDependenceEdge::EDGE_RA :
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAW, reg, false, false, 
                    source.pseudo(), mnd.pseudo(), source.loop());
            // and connect.
            if (connectOrDeleteEdge(*source.mn(), *mnd.mn(), dde)) {
                addedEdges.insert(dde);
            }
        }
    }
    
    // WaRs
    std::set<MoveNodeUse>& useReaches = 
        bb.liveRangeData_->regUseReaches_[reg];
    for (std::set<MoveNodeUse>::iterator i = useReaches.begin();
         i != useReaches.end(); i++) {
 
        const MoveNodeUse& source = *i;
        if (hasNode(*source.mn()) && source.mn()->isMove() &&
            (hasAllRegisterAntidependencies() || 
             &getBasicBlockNode(*source.mn()) == 
            &getBasicBlockNode(*mnd.mn()))) {
            // create dependency edge
            DataDependenceEdge* dde =
                new DataDependenceEdge(
                    mnd.ra() ? DataDependenceEdge::EDGE_RA :
                    DataDependenceEdge::EDGE_REGISTER,
                    DataDependenceEdge::DEP_WAR, reg, source.guard(), false, 
                    source.pseudo(), mnd.pseudo(), source.loop());
            // and connect.
            if (connectOrDeleteEdge(*source.mn(), *mnd.mn(), dde)) {
                addedEdges.insert(dde);
            }
        }
    }
    return addedEdges;
}

References connectOrDeleteEdge(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, getBasicBlockNode(), MoveNodeUse::guard(), hasAllRegisterAntidependencies(), BoostGraph< MoveNode, DataDependenceEdge >::hasNode(), MoveNode::isMove(), TTAProgram::BasicBlock::liveRangeData_, MoveNodeUse::loop(), MoveNodeUse::mn(), MoveNodeUse::pseudo(), MoveNodeUse::ra(), LiveRangeData::regDefReaches_, and LiveRangeData::regUseReaches_.

Referenced by DataDependenceGraphBuilder::processRegWrite(), and DataDependenceGraphBuilder::updateBB().

Here is the call graph for this function:

◆ writesJumpGuard()

bool DataDependenceGraph::writesJumpGuard ( const MoveNode & moveNode )

Returns true if the node writes a value to a predicate register which is used as a guard of a jump.

Definition at line 4593 of file DataDependenceGraph.cc.

                                                                  {
    NodeSet succs = successors(moveNode);
    for (auto n: succs) {
        if (n->move().isJump()) {
            if (onlyGuardDefOfMove(*n) == &moveNode) {
                return true;
            }
        }
    }
    return false;
}

References onlyGuardDefOfMove(), and BoostGraph< MoveNode, DataDependenceEdge >::successors().

Here is the call graph for this function:

◆ writeToXMLFile()

void DataDependenceGraph::writeToXMLFile ( std::string fileName ) const

Writes the graph into an XML file.

Definition at line 1747 of file DataDependenceGraph.cc.

                                                            {
 
    XMLSerializer serializer;
    ObjectState topOS = ObjectState("dependenceinfo");
    ObjectState* labelOS = new ObjectState("label", &topOS);
    ObjectState* nodesOS = new ObjectState("nodes", &topOS);
    ObjectState* edgesOS = new ObjectState("edges", &topOS);
 
    // Name of the unit
    labelOS->setValue(name());
 
    // Populate the nodes element
    for (int i = 0; i < nodeCount(); ++i) {
        ObjectState* nodeOS = new ObjectState("node", nodesOS);
        ObjectState* idOS = new ObjectState("id", nodeOS);
        ObjectState* labelOS = new ObjectState("label", nodeOS);
 
        Node& n = node(i);
 
        idOS->setValue(n.nodeID());
        labelOS->setValue(n.toString());
 
        if (n.isPlaced()) {
            ObjectState* cycleOS = new ObjectState("cycle", nodeOS);
            ObjectState* busOS = new ObjectState("slot", nodeOS);
 
            cycleOS->setValue(Conversion::toString(n.cycle()));
            busOS->setValue(n.move().bus().name());
        }
    }
 
    // Populate the edges element
    typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::edges(graph_);
    for (EdgeIter i = edges.first; i != edges.second; i++) {
        Edge& e = *graph_[*i];
        Node& tail = *graph_[boost::source(*i, graph_)];
        Node& head = *graph_[boost::target(*i, graph_)];
        edgesOS->addChild(e.saveState(tail, head));
    }
 
    // Implicit operand to trigger edges
    for (int i = 0; i < nodeCount(); ++i) {
        Node& n = node(i);
        if (n.isPlaced() && n.isMove() && n.move().isTriggering() &&
            n.isDestinationOperation()) {
            ProgramOperation &dst = n.destinationOperation();
            for (int j = 0; j < dst.inputMoveCount(); ++j) {
                if (dst.inputMove(j).nodeID() != n.nodeID()) {
                    
                    // Create a dummy edge and dump it
                    DataDependenceEdge e(DataDependenceEdge::EDGE_OPERATION,
                                         DataDependenceEdge::DEP_TRIGGER);
                    edgesOS->addChild(e.saveState(dst.inputMove(j), n));
                }
            }
        }
    }
 
    serializer.setDestinationFile(fileName);
    serializer.writeState(&topOS);
}

References ObjectState::addChild(), TTAProgram::Move::bus(), MoveNode::cycle(), DataDependenceEdge::DEP_TRIGGER, MoveNode::destinationOperation(), DataDependenceEdge::EDGE_OPERATION, BoostGraph< MoveNode, DataDependenceEdge >::graph_, ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isDestinationOperation(), MoveNode::isMove(), MoveNode::isPlaced(), TTAProgram::Move::isTriggering(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::name(), TTAMachine::Component::name(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), GraphNode::nodeID(), DataDependenceEdge::saveState(), XMLSerializer::setDestinationFile(), ObjectState::setValue(), MoveNode::toString(), Conversion::toString(), and XMLSerializer::writeState().

Referenced by BasicBlockScheduler::ddgSnapshot(), BasicBlockPass::ddgSnapshot(), BF2Scheduler::handleLoopDDG(), BBSchedulerController::handleProcedure(), and BF2Scheduler::scheduleDDG().

Here is the call graph for this function:

Member Data Documentation

◆ allParamRegs_

std::set<TCEString> DataDependenceGraph::allParamRegs_

private

Definition at line 430 of file DataDependenceGraph.hh.

Referenced by createSubgraph(), criticalPathGraph(), firstRegisterCycle(), lastRegisterCycle(), memoryDependenceGraph(), and trueDependenceGraph().

◆ cycleGrouping_

bool DataDependenceGraph::cycleGrouping_

private

Dot printing related variables. Group the printed MoveNodes according to their cycles.

Definition at line 442 of file DataDependenceGraph.hh.

Referenced by dotString(), and setCycleGrouping().

◆ delaySlots_

int DataDependenceGraph::delaySlots_

private

Definition at line 449 of file DataDependenceGraph.hh.

Referenced by earliestCycle(), edgeLatency(), edgeWeight(), firstRegisterCycle(), lastRegisterCycle(), latestCycle(), and setMachine().

◆ dotProgramOperationNodes_

bool DataDependenceGraph::dotProgramOperationNodes_

private

The moves belonging to the same program operation are merged to a single node. Reduces the complexity of the graph.

Definition at line 445 of file DataDependenceGraph.hh.

Referenced by dotString(), and setProgramOperationNodes().

◆ edgeWeightHeuristics_

EdgeWeightHeuristics DataDependenceGraph::edgeWeightHeuristics_

private

The heuristics to use to weight edges in the longest path computation.

Definition at line 458 of file DataDependenceGraph.hh.

Referenced by edgeWeight(), and setEdgeWeightHeuristics().

◆ machine_

const TTAMachine::Machine* DataDependenceGraph::machine_

private

Definition at line 448 of file DataDependenceGraph.hh.

Referenced by createSubgraph(), criticalPathGraph(), earliestCycle(), latestCycle(), machine(), memoryDependenceGraph(), setMachine(), and trueDependenceGraph().

◆ moveNodeBlocks_

std::map<const MoveNode*, BasicBlockNode*> DataDependenceGraph::moveNodeBlocks_

private

Definition at line 438 of file DataDependenceGraph.hh.

Referenced by createSubgraph(), getBasicBlockNode(), getBasicBlockNode(), setBasicBlockNode(), and setNodeBB().

◆ nodesOfMoves_

std::map<const TTAProgram::Move*, MoveNode*> DataDependenceGraph::nodesOfMoves_

private

Definition at line 434 of file DataDependenceGraph.hh.

Referenced by addNode(), nodeOfMove(), and removeNode().

◆ operationLatencies_

std::map<TCEString, int> DataDependenceGraph::operationLatencies_

private

Definition at line 450 of file DataDependenceGraph.hh.

Referenced by getOperationLatency(), and setMachine().

◆ ownedBBN_

BasicBlockNode* DataDependenceGraph::ownedBBN_

private

Definition at line 453 of file DataDependenceGraph.hh.

Referenced by ~DataDependenceGraph().

◆ procedureDDG_

bool DataDependenceGraph::procedureDDG_

private

Definition at line 454 of file DataDependenceGraph.hh.

Referenced by dotString(), and isRootGraphProcedureDDG().

◆ programOperations_

POList DataDependenceGraph::programOperations_

private

Definition at line 437 of file DataDependenceGraph.hh.

Referenced by addProgramOperation(), createSubgraph(), dropProgramOperation(), programOperation(), programOperation(), programOperationCount(), programOperationPtr(), and ~DataDependenceGraph().

◆ registerAntidependenceLevel_

AntidependenceLevel DataDependenceGraph::registerAntidependenceLevel_

private

Definition at line 455 of file DataDependenceGraph.hh.

Referenced by createSubgraph(), criticalPathGraph(), hasAllRegisterAntidependencies(), hasIntraBBRegisterAntidependencies(), hasSingleBBLoopRegisterAntidependencies(), memoryDependenceGraph(), and trueDependenceGraph().

◆ rrCost_

int DataDependenceGraph::rrCost_

private

Definition at line 451 of file DataDependenceGraph.hh.

Referenced by edgeWeight(), and setMachine().

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

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ AntidependenceLevel

◆ DumpFileFormat

◆ EdgeWeightHeuristics

Constructor & Destructor Documentation

◆ DataDependenceGraph()

◆ ~DataDependenceGraph()

Member Function Documentation

◆ addNode() [1/3]

◆ addNode() [2/3]

◆ addNode() [3/3]

◆ addProgramOperation()

◆ combineNodes()

◆ connectOrDeleteEdge()

◆ copyDependencies()

◆ copyDepsOver() [1/2]

◆ copyDepsOver() [2/2]

◆ copyExternalInEdges()

◆ copyExternalOutEdges()

◆ copyIncomingGuardEdges()

◆ copyIncomingRawEdges()

◆ copyOutgoingGuardWarEdges()

◆ createRegisterAntiDependenciesBetweenNodes()

◆ createSubgraph() [1/3]

◆ createSubgraph() [2/3]

◆ createSubgraph() [3/3]

◆ criticalPathGraph()

◆ deleteNode()

◆ destRenamed()

◆ dotString()

◆ dropBackEdges()

◆ dropProgramOperation()

◆ earliestCycle()

◆ edgeLatency()

◆ edgeWeight()

◆ exclusingGuards()

◆ findBypassSource()

◆ findLimitingAntidependenceDestination()

◆ findLimitingAntidependenceSource()

◆ findLiveRange()

◆ findLoopIndexInit()

◆ findLoopIndexUpdate()

◆ findLoopLimitAndIndex()

◆ firstRegisterCycle()

◆ firstScheduledRegisterKill()

◆ firstScheduledRegisterRead()

◆ firstScheduledRegisterReads()

◆ firstScheduledRegisterWrite()

◆ firstScheduledRegisterWrites()

◆ fixAntidepsAfterLoopUnmergeUser()

◆ fixInterBBAntiEdges()

◆ getBasicBlockNode() [1/2]

◆ getBasicBlockNode() [2/2]

◆ getOperationLatency()

◆ guardConverted()

◆ guardDefMoves()

◆ guardRawPredecessors()

◆ guardRenamed()

◆ guardRestored()

◆ guardsAllowBypass()

◆ hasAllRegisterAntidependencies()

◆ hasEqualEdge()

◆ hasIntraBBRegisterAntidependencies()

◆ hasOtherRegWawSources()

◆ hasRegWaw()

◆ hasSingleBBLoopRegisterAntidependencies()

◆ hasUnscheduledPredecessors()

◆ hasUnscheduledSuccessors()

◆ isLoopBypass()

◆ isLoopInvariant()

◆ isNotAvoidable()

◆ isRootGraphProcedureDDG()

◆ largestCycle()