OpenASIP
2.0
|
#include <DataDependenceGraph.hh>
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 MoveNode ::Comparator > | NodeSet |
typedef std::set< DataDependenceEdge *, typename DataDependenceEdge ::Comparator > | EdgeSet |
typedef MoveNode | Node |
The (base) node type managed by this graph. More... | |
typedef DataDependenceEdge | Edge |
The (base) edge type managed by this graph. More... | |
Public Types inherited from GraphBase< MoveNode, DataDependenceEdge > | |
typedef std::set< MoveNode *, typename MoveNode ::Comparator > | NodeSet |
typedef std::set< DataDependenceEdge *, typename DataDependenceEdge ::Comparator > | EdgeSet |
typedef MoveNode | Node |
Node type of this graph (possibly, a base class). More... | |
typedef DataDependenceEdge | Edge |
Edge type of this graph (possibly, a base class). More... | |
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. More... | |
bool | dotProgramOperationNodes_ |
The moves belonging to the same program operation are merged to a single node. Reduces the complexity of the graph. More... | |
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. More... | |
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. More... | |
typedef boost::graph_traits< Graph > | GraphTraits |
Traits characterising the internal graph type. More... | |
typedef GraphTraits::out_edge_iterator | OutEdgeIter |
Output edge iterator type. More... | |
typedef GraphTraits::in_edge_iterator | InEdgeIter |
Input edge iterator type. More... | |
typedef GraphTraits::edge_iterator | EdgeIter |
Iterator type for the list of all edges in the graph. More... | |
typedef GraphTraits::vertex_iterator | NodeIter |
Iterator type for the list of all nodes in the graph. More... | |
typedef GraphTraits::edge_descriptor | EdgeDescriptor |
Type with which edges of the graph are seen internally. More... | |
typedef GraphTraits::vertex_descriptor | NodeDescriptor |
Type with which nodes of the graph are seen internally. More... | |
typedef hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions > | EdgeDescMap |
typedef hash_map< const Node *, NodeDescriptor, GraphHashFunctions > | NodeDescMap |
typedef std::vector< std::vector< int > > | PathCache |
Protected Member Functions inherited from BoostGraph< 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 Attributes inherited from BoostGraph< MoveNode, DataDependenceEdge > | |
std::map< const MoveNode *, int, typename MoveNode ::Comparator > | sourceDistances_ |
std::map< const MoveNode *, int, typename MoveNode ::Comparator > | sinkDistances_ |
std::map< const MoveNode *, int, typename MoveNode ::Comparator > | loopingSourceDistances_ |
std::map< const MoveNode *, int, typename MoveNode ::Comparator > | loopingSinkDistances_ |
int | height_ |
Graph | graph_ |
The internal graph structure. More... | |
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_ |
Definition at line 67 of file DataDependenceGraph.hh.
Enumerator | |
---|---|
NO_ANTIDEPS | |
INTRA_BB_ANTIDEPS | |
SINGLE_BB_LOOP_ANTIDEPS | |
ALL_ANTIDEPS |
Definition at line 78 of file DataDependenceGraph.hh.
Enumerator | |
---|---|
DUMP_DOT | |
DUMP_XML |
Definition at line 85 of file DataDependenceGraph.hh.
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.
DataDependenceGraph::DataDependenceGraph | ( | std::set< TCEString > | allParamRegs, |
const TCEString & | name = "" , |
||
AntidependenceLevel | antidependenceLevel = ALL_ANTIDEPS , |
||
BasicBlockNode * | ownedBBN = NULL , |
||
bool | containsProcedure = false , |
||
bool | noLoopEdges = false |
||
) |
Constructor.
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.
Referenced by createSubgraph(), criticalPathGraph(), memoryDependenceGraph(), and trueDependenceGraph().
|
virtual |
Deletes all MoveNodes and ProgramOperations.
Definition at line 95 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), ownedBBN_, BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, and programOperations_.
|
virtual |
Adds a node into the graph.
This method should not be called by the user, used internally
moveNode | moveNode being added. |
Reimplemented from BoostGraph< MoveNode, DataDependenceEdge >.
Definition at line 144 of file DataDependenceGraph.cc.
References BoostGraph< GraphNode, GraphEdge >::addNode(), MoveNode::isMove(), MoveNode::move(), and nodesOfMoves_.
Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), RegisterCopyAdder::addConnectionRegisterCopiesImmediate(), addNode(), LoopPrologAndEpilogBuilder::build(), LLVMTCEDataDependenceGraphBuilder::buildLocalDDG(), DataDependenceGraphBuilder::constructIndividualBB(), DataDependenceGraphBuilder::constructIndividualFromInlineAsmBB(), DataDependenceGraphBuilder::createRegisterDeps(), MoveNodeDuplicator::duplicateMoveNode(), BFRegCopy::operator()(), and PreOptimizer::tryToRemoveGuardInversingOp().
void DataDependenceGraph::addNode | ( | MoveNode & | moveNode, |
BasicBlockNode & | bblock | ||
) |
Adds a node into the graph.
moveNode | moveNode being added. |
bblock | Basic block where the move logically belongs. |
Definition at line 158 of file DataDependenceGraph.cc.
References addNode(), and setNodeBB().
Adds a node into the graph.
moveNode | moveNode being added. |
relatedNode | another node already existing in the graph where this movenode relates to. , for example is created by splitting that |
Definition at line 172 of file DataDependenceGraph.cc.
References addNode(), getBasicBlockNode(), and setNodeBB().
void DataDependenceGraph::addProgramOperation | ( | ProgramOperationPtr | po | ) |
Adds a program operation to the graph, and its parent graphs.
po | ProgramOperation being added. |
Definition at line 298 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, programOperationCount(), and programOperations_.
Referenced by LLVMTCEDataDependenceGraphBuilder::buildLocalDDG(), DataDependenceGraphBuilder::processResultRead(), DataDependenceGraphBuilder::processTriggerPO(), and BFRemoveLoopChecksAndJump::undoOnlyMe().
void DataDependenceGraph::combineNodes | ( | MoveNode & | node1, |
MoveNode & | node2, | ||
MoveNode & | destination | ||
) |
Definition at line 2782 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), BoostGraph< MoveNode, DataDependenceEdge >::moveInEdge(), BoostGraph< MoveNode, DataDependenceEdge >::moveInEdges(), BoostGraph< MoveNode, DataDependenceEdge >::moveOutEdge(), BoostGraph< MoveNode, DataDependenceEdge >::moveOutEdges(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
Referenced by PreOptimizer::tryToRemoveGuardInversingOp().
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.
tailNode | tail node of edge |
headNode | head node of edge |
edge | edge which is added to graph or deleted. |
Definition at line 3355 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), hasEqualEdge(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
Referenced by DataDependenceGraphBuilder::checkAndCreateMemDep(), copyDepsOver(), DataDependenceGraphBuilder::createOperationEdges(), createRegisterAntiDependenciesBetweenNodes(), DataDependenceGraphBuilder::createRegisterAntideps(), DataDependenceGraphBuilder::createSideEffectEdges(), fixInterBBAntiEdges(), DataDependenceGraphBuilder::processRegUse(), RegisterRenamer::updateAntiEdgesFromLRTo(), updateRegUse(), and updateRegWrite().
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.
src | movenode to copy dependencies from |
dst | movenode to copy dependencies to |
Definition at line 3816 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), getBasicBlockNode(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and DataDependenceEdge::isBackEdge().
Referenced by MoveNodeDuplicator::duplicateMoveNode().
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.
node | node whose in- and outgoing antideps are being combined/copied. |
Definition at line 2422 of file DataDependenceGraph.cc.
References connectOrDeleteEdge(), DataDependenceEdge::data(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), exclusingGuards(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), DataDependenceEdge::loopDepth(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), and DataDependenceEdge::tailPseudo().
Referenced by CycleLookBackSoftwareBypasser::bypassNode(), BUBasicBlockScheduler::bypassNode(), destRenamed(), mergeAndKeepSource(), BFDREEarly::operator()(), BFDRELate::operator()(), BFPostpassDRE::operator()(), BFPostpassLoopDRE::operator()(), BFDRELoop::operator()(), renamedSimpleLiveRange(), BUBasicBlockScheduler::tryToOptimizeWaw(), BasicBlockScheduler::tryToOptimizeWaw(), and PreOptimizer::tryToRemoveGuardInversingOp().
Definition at line 2515 of file DataDependenceGraph.cc.
References connectOrDeleteEdge(), DataDependenceEdge::data(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), exclusingGuards(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), DataDependenceEdge::loopDepth(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), DataDependenceEdge::tailPseudo(), DataDependenceEdge::toString(), and MoveNode::toString().
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.
source | node containing original incoming edges. |
nodeCopy | node where to copy the inedges to. |
Definition at line 5323 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), getBasicBlockNode(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
Referenced by LoopPrologAndEpilogBuilder::build().
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.
source | node containing original outgoingcoming edges. |
nodeCopy | node where to copy the outedges to. |
Definition at line 5346 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), getBasicBlockNode(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().
Referenced by LoopPrologAndEpilogBuilder::build().
Copies all incoming guard dependencies going to a movenode to another
src | movenode to copy dependencies from |
dst | movenode to copy dependencies to |
Definition at line 3865 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and DataDependenceEdge::guardUse().
Referenced by BUBasicBlockScheduler::tryToOptimizeWaw(), and BasicBlockScheduler::tryToOptimizeWaw().
Definition at line 5770 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and DataDependenceEdge::guardUse().
Copies all outgoing guard war dependencies going to a movenode to another
src | movenode to copy dependencies from |
dst | movenode to copy dependencies to |
Definition at line 3897 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and DataDependenceEdge::guardUse().
Referenced by BUBasicBlockScheduler::tryToOptimizeWaw(), and BasicBlockScheduler::tryToOptimizeWaw().
void DataDependenceGraph::createRegisterAntiDependenciesBetweenNodes | ( | 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.
nodes | nodes whose antidependencies to add. |
Definition at line 4381 of file DataDependenceGraph.cc.
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().
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.
nodes | code being included in the subgraph |
includeLoops | whether to include loop-carried dependencies |
Definition at line 3377 of file DataDependenceGraph.cc.
References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), DataDependenceGraph(), 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(), and CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector().
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.
codeSnippets | code being included in the subgraph |
includeLoops | whether to include loop-carried dependencies |
Definition at line 3563 of file DataDependenceGraph.cc.
References createSubgraph(), TTAProgram::Instruction::isInProcedure(), MoveNode::isMove(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Move::parent(), and TTAProgram::Instruction::parent().
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.
cs | code being included in the subgraph |
includeLoops | whether to include loop-carried dependencies |
Definition at line 3532 of file DataDependenceGraph.cc.
References createSubgraph(), TTAProgram::Move::isInInstruction(), TTAProgram::Instruction::isInProcedure(), MoveNode::isMove(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), TTAProgram::Move::parent(), and TTAProgram::Instruction::parent().
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.
References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), DataDependenceGraph(), BoostGraph< MoveNode, DataDependenceEdge >::isInCriticalPath(), machine_, BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), registerAntidependenceLevel_, and setMachine().
Referenced by ResourceConstraintAnalyzer::analyze(), and BasicBlockScheduler::ddgSnapshot().
void DataDependenceGraph::deleteNode | ( | MoveNode & | node | ) |
Removes a MoveNode from a graph and deletes it.
node | MoveNode being deleted. |
Definition at line 2882 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::node(), and removeNode().
Referenced by PreOptimizer::tryToPrecalcConstantAdd(), and PreOptimizer::tryToRemoveGuardInversingOp().
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.
References DataDependenceGraph::UndoData::changedDataEdges, copyDepsOver(), DataDependenceEdge::data(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::guard(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), TTAProgram::Terminal::index(), BoostGraph< MoveNode, DataDependenceEdge >::inEdge(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isUnconditional(), MoveNode::move(), DataDependenceGraph::UndoData::newEdges, BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), BoostGraph< MoveNode, DataDependenceEdge >::outEdge(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), DisassemblyRegister::registerName(), DataDependenceGraph::UndoData::removedEdges, BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), DataDependenceEdge::setData(), TTAProgram::Move::source(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), and DataDependenceEdge::tailPseudo().
Referenced by BFRenameLiveRange::renameLiveRange(), and RegisterRenamer::renameLiveRange().
|
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.
Definition at line 1562 of file DataDependenceGraph.cc.
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().
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.
References BoostGraph< MoveNode, DataDependenceEdge >::childGraphs_, BoostGraph< MoveNode, DataDependenceEdge >::edgeDescriptors_, BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::isBackEdge(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().
void DataDependenceGraph::dropProgramOperation | ( | ProgramOperationPtr | po | ) |
Drops a program operation to the graph, but not its parent graphs.
po | ProgramOperation being added. |
Definition at line 361 of file DataDependenceGraph.cc.
References programOperations_.
Referenced by BFRemoveLoopChecksAndJump::operator()().
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.
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. |
Definition at line 388 of file DataDependenceGraph.cc.
References __func__, assert, MoveNode::cycle(), DataDependenceEdge::data(), delaySlots_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), MoveNode::destinationOperation(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_FUSTATE, DataDependenceEdge::EDGE_MEMORY, DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), getOperationLatency(), MoveNode::guardLatency(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::hasNode(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), MoveNode::inSameOperation(), DataDependenceEdge::isBackEdge(), MoveNode::isDestinationOperation(), MoveNode::isPlaced(), MoveNode::isSourceOperation(), DataDependenceEdge::loopDepth(), machine_, ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), MoveNode::sourceOperation(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), ProgramOperation::triggeringMove(), and TTAMachine::Machine::triggerInvalidatesResults().
Referenced by ResourceConstraintAnalyzer::analyzeMoveNode(), CycleLookBackSoftwareBypasser::bypass(), CycleLookBackSoftwareBypasser::bypassNode(), MoveNodeGroup::earliestCycle(), ResourceConstraintAnalyzer::findResourceConstrainedParent(), ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage(), BFPushMoveUp::operator()(), BFPushAntidepDown::operator()(), BFPushMoveUp2::operator()(), BFScheduleExact::operator()(), BFScheduleBU::operator()(), BasicBlockScheduler::scheduleMove(), BUBasicBlockScheduler::scheduleMove(), BasicBlockScheduler::scheduleOperandWrites(), BasicBlockScheduler::tryToOptimizeWaw(), and BasicBlockScheduler::tryToSwitchInputs().
int DataDependenceGraph::edgeLatency | ( | const DataDependenceEdge & | edge, |
int | ii, | ||
const MoveNode * | tail, | ||
const MoveNode * | head | ||
) | const |
Definition at line 311 of file DataDependenceGraph.cc.
References DataDependenceEdge::data(), delaySlots_, DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::edgeReason(), getOperationLatency(), MoveNode::guardLatency(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), MoveNode::inSameOperation(), MoveNode::isSourceOperation(), DataDependenceEdge::loopDepth(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), DataDependenceEdge::tailPseudo(), and DataDependenceEdge::toString().
Referenced by BFPushDepsUp::operator()().
|
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).
e | edge whose weight is being measured |
n | head node of the edge. |
Reimplemented from BoostGraph< MoveNode, DataDependenceEdge >.
Definition at line 2910 of file DataDependenceGraph.cc.
References abortWithError, DataDependenceEdge::data(), delaySlots_, DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::EDGE_MEMORY, DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), edgeWeightHeuristics_, EWH_HEURISTIC, EWH_REAL, getOperationLatency(), MoveNode::guardLatency(), DataDependenceEdge::guardUse(), DataDependenceEdge::headPseudo(), TTAProgram::Move::isControlFlowMove(), TTAProgram::Move::isJump(), MoveNode::isMove(), MoveNode::move(), rrCost_, GraphEdge::setWeight(), and GraphEdge::weight().
Definition at line 4480 of file DataDependenceGraph.cc.
References TTAProgram::Move::guard(), guardRawPredecessors(), TTAProgram::MoveGuard::isInverted(), MoveNode::isMove(), TTAProgram::Move::isUnconditional(), and MoveNode::move().
Referenced by DataDependenceGraphBuilder::checkAndCreateMemDep(), copyDepsOver(), RegisterCopyAdder::createAntidepsForReg(), createRegisterAntiDependenciesBetweenNodes(), DataDependenceGraphBuilder::createRegisterAntideps(), DataDependenceGraphBuilder::createSideEffectEdges(), ExecutionPipelineResource::exclusiveMoves(), mergeAndKeepAllowed(), mergeAndKeepUser(), DataDependenceGraphBuilder::processRegUse(), DataDependenceGraphBuilder::processRegWrite(), BUBasicBlockScheduler::tryToOptimizeWaw(), BasicBlockScheduler::tryToOptimizeWaw(), and unMergeUser().
Definition at line 5734 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), DataDependenceEdge::isBackEdge(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
Definition at line 5293 of file DataDependenceGraph.cc.
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().
Definition at line 5272 of file DataDependenceGraph.cc.
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().
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.
Definition at line 4827 of file DataDependenceGraph.cc.
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().
Definition at line 4755 of file DataDependenceGraph.cc.
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().
Definition at line 4704 of file DataDependenceGraph.cc.
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().
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)
jumpMove | jump move of a loop. |
Definition at line 4618 of file DataDependenceGraph.cc.
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().
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
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 981 of file DataDependenceGraph.cc.
References allParamRegs_, assert, MoveNode::cycle(), delaySlots_, TTAProgram::Move::destination(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::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(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), DisassemblyRegister::registerName(), and TTAProgram::Move::source().
Referenced by RegisterRenamer::findPartiallyUsedRegistersAfterCycle(), and RegisterRenamer::findPartiallyUsedRegistersInRFAfterCycle().
MoveNode * DataDependenceGraph::firstScheduledRegisterKill | ( | const TTAMachine::BaseRegisterFile & | rf, |
int | registerIndex | ||
) | const |
Returns the MoveNode of unconditional move with highest cycle that writes the given register.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 1320 of file DataDependenceGraph.cc.
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().
MoveNode * DataDependenceGraph::firstScheduledRegisterRead | ( | const TTAMachine::BaseRegisterFile & | rf, |
int | registerIndex, | ||
int | firstCycleToTest = 0 |
||
) | const |
Returns the MoveNode with lowest cycle that reads the given register.
rf | The register file. |
registerIndex | Index of the register. |
firstCycleToTest | optional argument from which cycle to start search. |
Definition at line 808 of file DataDependenceGraph.cc.
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().
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.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 1121 of file DataDependenceGraph.cc.
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().
MoveNode * DataDependenceGraph::firstScheduledRegisterWrite | ( | const TTAMachine::BaseRegisterFile & | rf, |
int | registerIndex | ||
) | const |
Returns the MoveNode with lowest cycle that writes the given register.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 847 of file DataDependenceGraph.cc.
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().
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.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 1245 of file DataDependenceGraph.cc.
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 BFRegCopy::createAntidepsForReg(), RegisterCopyAdder::createAntidepsForReg(), BFRenameLiveRange::renameLiveRange(), and RegisterRenamer::renameLiveRange().
void DataDependenceGraph::fixAntidepsAfterLoopUnmergeUser | ( | MoveNode & | sourceNode, |
MoveNode & | mergedNode, | ||
const TCEString & | reg | ||
) |
Definition at line 2213 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::data(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdge().
Referenced by unMergeUser().
void DataDependenceGraph::fixInterBBAntiEdges | ( | BasicBlockNode & | bbn1, |
BasicBlockNode & | bbn2, | ||
bool | loopEdges | ||
) |
Addds inter-BB-Anti edges between the the basic blocks.
currently quite a heavy routine
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.
References BasicBlockNode::basicBlock(), connectOrDeleteEdge(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, TTAProgram::MoveGuard::guard(), TTAProgram::Move::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().
const BasicBlockNode & DataDependenceGraph::getBasicBlockNode | ( | const MoveNode & | mn | ) | const |
Gives the basic block node where the node belongs to.
mn | MoveNode whose basic block we are asking |
Definition at line 186 of file DataDependenceGraph.cc.
References __func__, moveNodeBlocks_, and MoveNode::toString().
Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), RegisterCopyAdder::addConnectionRegisterCopiesImmediate(), addNode(), copyDependencies(), copyExternalInEdges(), copyExternalOutEdges(), ProgramDependenceGraph::copyRegionEECComponent(), LoopAnalyzer::findEndCond(), BF2Scheduler::handleLoopDDG(), PreOptimizer::inverseGuardsOfHeads(), BFRegCopy::operator()(), ProgramDependenceGraph::ProgramDependenceGraph(), BF2Scheduler::revertBBLiveRangeBookkeepingForDestination(), BF2Scheduler::revertBBLiveRangeBookkeepingForSource(), PreOptimizer::tryToOptimizeAddressReg(), and updateRegWrite().
BasicBlockNode & DataDependenceGraph::getBasicBlockNode | ( | MoveNode & | mn | ) |
Gives the basic block node where the node belongs to.
mn | MoveNode whose basic block we are asking |
Definition at line 204 of file DataDependenceGraph.cc.
References __func__, moveNodeBlocks_, and MoveNode::toString().
|
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.
op | operation whose minimum latency is being searched |
Definition at line 3304 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::name(), and operationLatencies_.
Referenced by earliestCycle(), edgeLatency(), edgeWeight(), and latestCycle().
Definition at line 5795 of file DataDependenceGraph.cc.
References assert, BoostGraph< GraphNode, GraphEdge >::connectNodes(), DataDependenceEdge::data(), DataDependenceEdge::DEP_UNKNOWN, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), 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 DataDependenceEdge::toString().
Referenced by BFLateBypassGuard::operator()(), and BFEarlyGuardBypass::operator()().
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.
moveNode | The move node of which guard defining move to find. |
Definition at line 743 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
Referenced by guardsAllowBypass(), lastGuardDefMove(), onlyGuardDefOfMove(), and BasicBlockScheduler::tryToOptimizeWaw().
DataDependenceGraph::NodeSet DataDependenceGraph::guardRawPredecessors | ( | const MoveNode & | node | ) | const |
Definition at line 4048 of file DataDependenceGraph.cc.
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().
DataDependenceGraph::UndoData DataDependenceGraph::guardRenamed | ( | MoveNode & | mn | ) |
Definition at line 5006 of file DataDependenceGraph.cc.
References assert, DataDependenceGraph::UndoData::changedDataEdges, DataDependenceEdge::data(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::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(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::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().
Definition at line 5849 of file DataDependenceGraph.cc.
References assert, BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceEdge::data(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), BoostGraph< MoveNode, DataDependenceEdge >::inEdge(), TTAProgram::Terminal::isGPR(), DataDependenceEdge::loopDepth(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), BoostGraph< MoveNode, DataDependenceEdge >::outEdge(), DisassemblyRegister::registerName(), BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), ProgramOperation::removeGuardOutputNode(), MoveNode::sourceOperation(), and MoveNode::unsetGuardOperation().
Referenced by BFLateBypassGuard::operator()(), BFEarlyGuardBypass::undoOnlyMe(), and BFLateBypassGuard::undoOnlyMe().
bool DataDependenceGraph::guardsAllowBypass | ( | const MoveNode & | defNode, |
const MoveNode & | useNode, | ||
bool | loopBypass = false |
||
) |
Checks whether guards allow bypassing.
defNode | node defining a value, bypass source. |
useNode | node using the value, node being bypassed. |
Definition at line 4543 of file DataDependenceGraph.cc.
References TTAProgram::MoveGuard::guard(), TTAProgram::Move::guard(), guardDefMoves(), TTAMachine::Guard::isEqual(), TTAProgram::Move::isUnconditional(), and MoveNode::move().
Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), CycleLookBackSoftwareBypasser::bypassNode(), and BUBasicBlockScheduler::bypassNode().
|
inline |
Definition at line 379 of file DataDependenceGraph.hh.
References ALL_ANTIDEPS, and registerAntidependenceLevel_.
Referenced by ControlFlowGraph::mergeNodes(), DataDependenceGraphBuilder::setSucceedingPredepsForBB(), DataDependenceGraphBuilder::updateRegistersAliveAfter(), and updateRegWrite().
|
private |
Checks if the graph already has an edge with same properties from same node to same node.
tailNode | tail node of edge |
headNode | head node of edge |
edge | edge which for to test equality |
Definition at line 3324 of file DataDependenceGraph.cc.
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().
|
inline |
Definition at line 387 of file DataDependenceGraph.hh.
References INTRA_BB_ANTIDEPS, and registerAntidependenceLevel_.
Referenced by ControlFlowGraph::mergeNodes(), and DataDependenceGraphBuilder::processRegWrite().
bool DataDependenceGraph::hasOtherRegWawSources | ( | const MoveNode & | mn | ) | const |
Definition at line 5701 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
bool DataDependenceGraph::hasRegWaw | ( | const MoveNodeUse & | mnu, |
std::set< MoveNodeUse > | targets | ||
) | const |
Definition at line 5518 of file DataDependenceGraph.cc.
References AssocTools::containsKey(), DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::isBackEdge(), and MoveNodeUse::mn().
Referenced by DataDependenceGraphBuilder::processRegUse().
|
inline |
Definition at line 383 of file DataDependenceGraph.hh.
References registerAntidependenceLevel_, and SINGLE_BB_LOOP_ANTIDEPS.
Referenced by DataDependenceGraphBuilder::processRegWrite(), DataDependenceGraphBuilder::setSucceedingPredepsForBB(), and DataDependenceGraphBuilder::updateBB().
bool DataDependenceGraph::hasUnscheduledPredecessors | ( | const MoveNode & | mn | ) | const |
Definition at line 5594 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::predecessors().
bool DataDependenceGraph::hasUnscheduledSuccessors | ( | const MoveNode & | mn | ) | const |
Definition at line 5607 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::successors().
Definition at line 1916 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::connectingEdges(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), and DataDependenceEdge::isBackEdge().
Referenced by mergeAndKeepSource(), mergeAndKeepUser(), and BFMergeAndKeepUser::operator()().
bool DataDependenceGraph::isLoopInvariant | ( | const MoveNode & | mn | ) | const |
Definition at line 5688 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), and BoostGraph< MoveNode, DataDependenceEdge >::inEdges().
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.
References BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::guard(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), TTAMachine::Guard::isEqual(), DataDependenceEdge::isFalseDep(), TTAMachine::Guard::isOpposite(), TTAProgram::Move::isUnconditional(), MoveNode::move(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
Referenced by trueDependenceGraph().
|
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.
Definition at line 3669 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, and procedureDDG_.
Referenced by resultUsed().
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.
Definition at line 1838 of file DataDependenceGraph.cc.
References MoveNode::cycle(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().
Referenced by ResourceConstraintAnalyzer::analyzeRegisterAntideps(), LoopPrologAndEpilogBuilder::build(), dotString(), BBSchedulerController::executeDDGPass(), BUBasicBlockScheduler::handleLoopDDG(), BasicBlockScheduler::handleLoopDDG(), and BasicBlockScheduler::scheduleMove().
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.
moveNode | The move node of which guard defining move to find. |
Definition at line 721 of file DataDependenceGraph.cc.
References MoveNode::cycle(), and guardDefMoves().
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.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 882 of file DataDependenceGraph.cc.
References allParamRegs_, assert, MoveNode::cycle(), delaySlots_, TTAProgram::Move::destination(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::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(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::registerFile(), TTAMachine::RegisterGuard::registerIndex(), DisassemblyRegister::registerName(), and TTAProgram::Move::source().
Referenced by RegisterRenamer::findPartiallyUsedRegistersBeforeCycle(), and RegisterRenamer::findPartiallyUsedRegistersInRFBeforeCycle().
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.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 1163 of file DataDependenceGraph.cc.
References MoveNode::cycle(), TTAProgram::MoveGuard::guard(), TTAProgram::Move::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().
MoveNode * DataDependenceGraph::lastScheduledRegisterKill | ( | const TTAMachine::BaseRegisterFile & | rf, |
int | registerIndex | ||
) | const |
Returns the MoveNode of unconditional move with highest cycle that writes the given register.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 1285 of file DataDependenceGraph.cc.
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 BFRegCopy::createAntidepsForReg(), RegisterCopyAdder::createAntidepsForReg(), lastScheduledRegisterGuardReads(), lastScheduledRegisterReads(), and lastScheduledRegisterWrites().
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.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 766 of file DataDependenceGraph.cc.
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().
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.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 1080 of file DataDependenceGraph.cc.
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 BFRegCopy::createAntidepsForReg(), RegisterCopyAdder::createAntidepsForReg(), and RegisterRenamer::renameLiveRange().
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.
rf | The register file. |
registerIndex | Index of the register. |
Definition at line 1206 of file DataDependenceGraph.cc.
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 BFRegCopy::createAntidepsForReg(), RegisterCopyAdder::createAntidepsForReg(), and RegisterRenamer::renameLiveRange().
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.
moveNode | The move node for which to find the latest cycle. |
Definition at line 543 of file DataDependenceGraph.cc.
References __func__, assert, MoveNode::cycle(), DataDependenceEdge::data(), delaySlots_, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), MoveNode::destinationOperation(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_FUSTATE, DataDependenceEdge::EDGE_MEMORY, DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), getOperationLatency(), MoveNode::guardLatency(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::inSameOperation(), DataDependenceEdge::isBackEdge(), MoveNode::isDestinationOperation(), MoveNode::isPlaced(), MoveNode::isSourceOperation(), DataDependenceEdge::loopDepth(), machine_, BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), MoveNode::sourceOperation(), DataDependenceEdge::tailPseudo(), and TTAMachine::Machine::triggerInvalidatesResults().
Referenced by CycleLookBackSoftwareBypasser::bypass(), BFSchedulePreLoopShared::operator()(), BFPushAntidepsDown::operator()(), BFRemoveGuardsFromSuccs::operator()(), BFPushMoveUp::operator()(), BFShareOperands::operator()(), BFPushAntidepDown::operator()(), BFPushMoveUp2::operator()(), BFScheduleExact::operator()(), BasicBlockScheduler::scheduleMove(), BUBasicBlockScheduler::scheduleMove(), BUBasicBlockScheduler::scheduleOperandWrites(), BasicBlockScheduler::tryToDelayOperands(), BUBasicBlockScheduler::tryToOptimizeWaw(), and BUBasicBlockScheduler::tryToSwitchInputs().
|
inline |
Definition at line 260 of file DataDependenceGraph.hh.
References machine_.
Referenced by ResourceConstraintAnalyzer::analyzeMoveNode(), ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage(), and setMachine().
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.
References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), DataDependenceGraph(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_MEMORY, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), machine_, BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), registerAntidependenceLevel_, and setMachine().
Referenced by ResourceConstraintAnalyzer::analyze().
Checks if software bypassing is allowed without causing a deadlock through some circlar ddg dependence.
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.
References __func__, DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), exclusingGuards(), BoostGraph< MoveNode, DataDependenceEdge >::hasEdge(), BoostGraph< MoveNode, DataDependenceEdge >::hasPath(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), MoveNode::isMove(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), BoostGraph< MoveNode, DataDependenceEdge >::outEdge(), DataDependenceEdge::tailPseudo(), MoveNode::toString(), and GraphBase< MoveNode, DataDependenceEdge >::writeToDotFile().
Referenced by mergeAndKeepSource(), and mergeAndKeepUser().
bool DataDependenceGraph::mergeAndKeepSource | ( | MoveNode & | resultNode, |
MoveNode & | userNode, | ||
bool | force = false |
||
) |
Definition at line 1962 of file DataDependenceGraph.cc.
References TTAProgram::AnnotatedInstructionElement::addAnnotation(), MoveNode::addDestinationOperationPtr(), TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST, TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST, TTAProgram::AnnotatedInstructionElement::annotation(), BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), TTAProgram::Terminal::copy(), copyDepsOver(), BoostGraph< GraphNode, GraphEdge >::copyInEdge(), DataDependenceEdge::data(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), MoveNode::destinationOperationPtr(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), TTAProgram::Terminal::equals(), DataDependenceEdge::guardUse(), BoostGraph< GraphNode, GraphEdge >::headNode(), TTAProgram::ProgramAnnotation::id(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), BoostGraph< MoveNode, DataDependenceEdge >::inEdge(), DataDependenceEdge::isBackEdge(), MoveNode::isDestinationOperation(), isLoopBypass(), mergeAndKeepAllowed(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_, 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::setDestination(), TTAProgram::Move::source(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
bool DataDependenceGraph::mergeAndKeepUser | ( | MoveNode & | resultNode, |
MoveNode & | userNode, | ||
bool | force = false |
||
) |
Definition at line 2079 of file DataDependenceGraph.cc.
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::data(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_RA, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), TTAProgram::Terminal::equals(), exclusingGuards(), DataDependenceEdge::guardUse(), BoostGraph< GraphNode, GraphEdge >::headNode(), TTAProgram::ProgramAnnotation::id(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), BoostGraph< MoveNode, DataDependenceEdge >::inEdge(), DataDependenceEdge::isBackEdge(), DataDependenceEdge::isFalseDep(), 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(), BoostGraph< GraphNode, GraphEdge >::tailNode(), and DataDependenceEdge::tailPseudo().
Referenced by RegisterCopyAdder::addConnectionRegisterCopies(), CycleLookBackSoftwareBypasser::bypassNode(), and BUBasicBlockScheduler::bypassNode().
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.
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().
DataDependenceGraph::NodeSet DataDependenceGraph::movesAtCycle | ( | int | cycle | ) | const |
Returns the moves that are scheduled at the given cycle.
cycle | The cycle. |
Definition at line 699 of file DataDependenceGraph.cc.
References MoveNode::cycle(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().
Referenced by dotString(), and BasicBlockScheduler::handleRemovedResultMoves().
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.
move | move. |
Definition at line 3600 of file DataDependenceGraph.cc.
References __func__, POMDisassembler::disassemble(), nodesOfMoves_, and Conversion::toString().
Referenced by LoopAnalyzer::analyze(), DataDependenceGraphBuilder::constructIndividualBB(), MoveNodeDuplicator::duplicateMove(), fixInterBBAntiEdges(), ControlFlowGraph::mergeNodes(), BFShareOperandsLate::operator()(), ControlFlowGraph::removeJumpToTarget(), and ControlFlowGraph::removeUnreachableNodes().
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.
References guardDefMoves().
Referenced by LoopAnalyzer::analyze(), findLoopLimitAndIndex(), BF2Scheduler::handleLoopDDG(), and writesJumpGuard().
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.
mn | MoveNode whose incoming edges we are searching. |
Definition at line 4024 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), and BoostGraph< MoveNode, DataDependenceEdge >::tailNode().
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.
References BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), and BoostGraph< MoveNode, DataDependenceEdge >::inEdge().
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.
References BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdge().
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.
References MoveNode::isSourceReg(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and onlyRegisterRawSource().
Referenced by OffsetAliasAnalyzer::analyze(), and OffsetAliasAnalyzer::isAddressTraceable().
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.
mn | MoveNode whose succssor moves we are searching. |
Definition at line 4163 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::guardUse(), DataDependenceEdge::headPseudo(), DataDependenceEdge::isBackEdge(), and DataDependenceEdge::tailPseudo().
Referenced by BF2ScheduleFront::allNodesOfSameOperation(), BUBasicBlockScheduler::bypassNode(), BUBasicBlockScheduler::findBypassDestinations(), and BUMoveNodeSelector::mightBeReady().
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.
mn | MoveNode whose succssor moves we are searching. |
Definition at line 4124 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::headPseudo(), DataDependenceEdge::isBackEdge(), and DataDependenceEdge::tailPseudo().
Referenced by BFLateBypasses::operator()().
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.
mn | MoveNode whose predecessor noves we are searching. |
Definition at line 4083 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::guardUse(), DataDependenceEdge::headPseudo(), DataDependenceEdge::isBackEdge(), and DataDependenceEdge::tailPseudo().
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().
DataDependenceGraph::EdgeSet DataDependenceGraph::operationInEdges | ( | const MoveNode & | node | ) | const |
Definition at line 5913 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, BoostGraph< MoveNode, DataDependenceEdge >::edgeDescriptors_, DataDependenceEdge::edgeReason(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, and BoostGraph< MoveNode, DataDependenceEdge >::node().
Referenced by BFPushMoveUp2::isLoopBypass(), and ExecutionPipelineBroker::isLoopBypass().
bool DataDependenceGraph::otherSuccessorsScheduled | ( | MoveNode & | node, |
const NodeSet & | ignoredNodes | ||
) | const |
Definition at line 3266 of file DataDependenceGraph.cc.
References AssocTools::containsKey(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::isBackEdge(), MoveNode::isPlaced(), and BoostGraph< MoveNode, DataDependenceEdge >::node().
Referenced by BUMoveNodeSelector::isReadyToBeScheduled().
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.
Definition at line 3176 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), MoveNode::destinationOperation(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::isBackEdge(), MoveNode::isDestinationOperation(), MoveNode::isPlaced(), MoveNode::isSourceOperation(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and MoveNode::sourceOperation().
Referenced by CriticalPathBBMoveNodeSelector::isReadyToBeScheduled().
ProgramOperation & DataDependenceGraph::programOperation | ( | int | index | ) |
Returs programoperation which is in this graph.
index | index of the programoperation. |
Definition at line 227 of file DataDependenceGraph.cc.
References programOperations_.
Referenced by BF2Scheduler::countLoopInvariantValueUsages(), PreOptimizer::handleCFGDDG(), and BF2Scheduler::reservePreallocatedFUs().
const ProgramOperation & DataDependenceGraph::programOperation | ( | int | index | ) | const |
Definition at line 232 of file DataDependenceGraph.cc.
References programOperations_.
int DataDependenceGraph::programOperationCount | ( | ) | const |
Returns the number of programoperations in this ddg.
Definition at line 246 of file DataDependenceGraph.cc.
References programOperations_.
Referenced by addProgramOperation(), BF2Scheduler::countLoopInvariantValueUsages(), PreOptimizer::handleCFGDDG(), and BF2Scheduler::reservePreallocatedFUs().
ProgramOperationPtr DataDependenceGraph::programOperationPtr | ( | int | index | ) |
Definition at line 237 of file DataDependenceGraph.cc.
References programOperations_.
|
private |
Definition at line 4918 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::hasNode(), DataDependenceEdge::headPseudo(), DataDependenceEdge::isBackEdge(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInEdges(), and DataDependenceEdge::tailPseudo().
Referenced by findLiveRange().
|
private |
Counts all incoming antidependence edges to a movenode.
mn | MoveNode whose edges we are counting |
Definition at line 4001 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_REGISTER, and BoostGraph< MoveNode, DataDependenceEdge >::inEdges().
DataDependenceGraph::NodeSet DataDependenceGraph::regDepSiblings | ( | const MoveNode & | mn | ) | const |
Definition at line 5620 of file DataDependenceGraph.cc.
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()().
DataDependenceGraph::EdgeSet DataDependenceGraph::registerAndRAInEdges | ( | const MoveNode & | node | ) | const |
Definition at line 5930 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::edgeDescriptors_, BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::isRegisterOrRA(), and BoostGraph< MoveNode, DataDependenceEdge >::node().
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
node | The node of which successors to find. |
Definition at line 4310 of file DataDependenceGraph.cc.
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().
int DataDependenceGraph::regRawSuccessorCount | ( | const MoveNode & | mn, |
bool | onlyScheduled | ||
) |
Calculates number of register RAW dependecies originating from given node
mn | Movenodes whose dependencies to calculate |
onlySchedules | only care about dependencies to Scheduled nodes. |
Definition at line 3952 of file DataDependenceGraph.cc.
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().
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
node | The node of which successors to find. |
Definition at line 4272 of file DataDependenceGraph.cc.
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 BUBasicBlockScheduler::tryToOptimizeWaw(), and BasicBlockScheduler::tryToOptimizeWaw().
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
node | The node of which successors to find. |
Definition at line 4239 of file DataDependenceGraph.cc.
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().
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.
node | The node of which successors to find. |
Definition at line 4347 of file DataDependenceGraph.cc.
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().
void DataDependenceGraph::removeIncomingGuardEdges | ( | MoveNode & | node | ) |
Removes guard raw edges coming to some node.
This is called if the guard is removed from the node.
node | The node. |
Definition at line 5466 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::guardUse(), and BoostGraph< MoveNode, DataDependenceEdge >::node().
Referenced by BasicBlockScheduler::scheduleMove(), BUBasicBlockScheduler::scheduleMove(), BUBasicBlockScheduler::tryToOptimizeWaw(), BasicBlockScheduler::tryToOptimizeWaw(), and BFOptimization::unsetJumpGuard().
|
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.
node | MoveNode being removed. |
Reimplemented from BoostGraph< MoveNode, DataDependenceEdge >.
Definition at line 2843 of file DataDependenceGraph.cc.
References MoveNode::clearDestinationOperation(), MoveNode::destinationOperation(), MoveNode::destinationOperationCount(), MoveNode::isDestinationOperation(), MoveNode::isMove(), MoveNode::isSourceOperation(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::node(), nodesOfMoves_, ProgramOperation::removeInputNode(), BoostGraph< GraphNode, GraphEdge >::removeNode(), ProgramOperation::removeOutputNode(), MoveNode::sourceOperation(), and MoveNode::unsetSourceOperation().
Referenced by deleteNode(), MoveNodeDuplicator::disposeMoveNode(), ControlFlowGraph::removeJumpToTarget(), ControlFlowGraph::removeUnreachableNodes(), and BFRegCopy::undoDDG().
void DataDependenceGraph::removeOutgoingGuardWarEdges | ( | MoveNode & | node | ) |
Removes guard raw edges coming to some node.
This is called if the guard is removed from the node.
node | The node. |
Definition at line 5496 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::guardUse(), and BoostGraph< MoveNode, DataDependenceEdge >::node().
Referenced by BUBasicBlockScheduler::tryToOptimizeWaw(), and BasicBlockScheduler::tryToOptimizeWaw().
Removes raw edged between nodes.
Returns the register associated with the raw dependency
Definition at line 1937 of file DataDependenceGraph.cc.
References assert, BoostGraph< MoveNode, DataDependenceEdge >::connectingEdges(), DataDependenceEdge::data(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), MoveNode::toString(), and GraphBase< MoveNode, DataDependenceEdge >::writeToDotFile().
Referenced by guardConverted(), mergeAndKeepSource(), and mergeAndKeepUser().
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.
References assert, BoostGraph< MoveNode, DataDependenceEdge >::connectingEdge(), BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), copyDepsOver(), DataDependenceEdge::data(), DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inEdges(), DataDependenceEdge::loopDepth(), BoostGraph< MoveNode, DataDependenceEdge >::moveInEdge(), BoostGraph< MoveNode, DataDependenceEdge >::outEdges(), BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), and DataDependenceEdge::tailPseudo().
Referenced by PreOptimizer::tryToOptimizeAddressReg().
bool DataDependenceGraph::resultUsed | ( | MoveNode & | resultNode | ) |
Checks whether a result is used later or if the result move can be dropped.
resultNode | node being checked for nonused results. |
Definition at line 2348 of file DataDependenceGraph.cc.
Referenced by CycleLookBackSoftwareBypasser::bypassNode(), BUBasicBlockScheduler::bypassNode(), BUBasicBlockScheduler::finalizeSchedule(), BUBasicBlockScheduler::handleDDG(), BUBasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::scheduleResultReads(), BUBasicBlockScheduler::scheduleResultReadTempMoves(), and BUBasicBlockScheduler::scheduleRRTempMoves().
Checks whether a result is used later or if the result move can be dropped.
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.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::headPseudo(), MoveNode::isMove(), isRootGraphProcedureDDG(), TTAProgram::Move::isUnconditional(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), and BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdges().
int DataDependenceGraph::rWarEdgesOut | ( | MoveNode & | mn | ) |
Calculates number of register WAR antidependecies originating from given node
mn | Movenodes whose dependencies to calculate |
Definition at line 3930 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_WAR, DataDependenceEdge::EDGE_REGISTER, and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().
Referenced by RegisterCopyAdder::addConnectionRegisterCopies().
|
private |
Calculates number of register antidependecies originating from given node
mn | Movenodes whose dependencies to calculate |
Definition at line 3978 of file DataDependenceGraph.cc.
References DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAW, DataDependenceEdge::EDGE_REGISTER, BoostGraph< MoveNode, DataDependenceEdge >::headNode(), TTAProgram::Move::isUnconditional(), MoveNode::move(), and BoostGraph< MoveNode, DataDependenceEdge >::outEdges().
Definition at line 4506 of file DataDependenceGraph.cc.
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().
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.
In | case the graph contains failures. Exception message contains the reason. |
Definition at line 1399 of file DataDependenceGraph.cc.
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::MoveGuard::guard(), TTAProgram::Move::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(), TTAProgram::Terminal::registerFile(), TTAMachine::RegisterGuard::registerFile(), TTAProgram::Move::source(), BoostGraph< MoveNode, DataDependenceEdge >::tailNode(), MoveNode::toString(), Operation::writesMemory(), and GraphBase< MoveNode, DataDependenceEdge >::writeToDotFile().
Referenced by BasicBlockScheduler::scheduleOperation(), and BasicBlockScheduler::scheduleRRMove().
DataDependenceGraph::NodeSet DataDependenceGraph::scheduledMoves | ( | ) | const |
Returns all scheduled moves.
cycle | The cycle. |
Definition at line 1375 of file DataDependenceGraph.cc.
References MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().
Referenced by ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage(), BasicBlockScheduler::unscheduleAllNodes(), and BUBasicBlockScheduler::unscheduleAllNodes().
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.
Definition at line 1859 of file DataDependenceGraph.cc.
References MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().
Referenced by BUMoveNodeSelector::candidates(), CriticalPathBBMoveNodeSelector::candidates(), BUBasicBlockScheduler::handleDDG(), BasicBlockScheduler::handleDDG(), BUBasicBlockScheduler::handleLoopDDG(), BasicBlockScheduler::handleLoopDDG(), BF2Scheduler::handleLoopDDG(), CriticalPathBBMoveNodeSelector::isReadyToBeScheduled(), BF2Scheduler::scheduleDDG(), BasicBlockScheduler::scheduleMove(), and BUBasicBlockScheduler::unscheduleAllNodes().
void DataDependenceGraph::setBasicBlockNode | ( | const MoveNode & | mn, |
BasicBlockNode & | bbn | ||
) |
Definition at line 216 of file DataDependenceGraph.cc.
References moveNodeBlocks_.
Referenced by ControlFlowGraph::mergeNodes().
|
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.
References cycleGrouping_.
Referenced by BUMoveNodeSelector::BUMoveNodeSelector(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), CriticalPathBBMoveNodeSelector::notifyScheduled(), BasicBlockScheduler::scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), BasicBlockScheduler::scheduleRRMove(), and BUBasicBlockScheduler::scheduleRRMove().
void DataDependenceGraph::setEdgeWeightHeuristics | ( | EdgeWeightHeuristics | ewh | ) |
Definition at line 5716 of file DataDependenceGraph.cc.
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().
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.
machine | machine to be used for heristics |
Definition at line 3116 of file DataDependenceGraph.cc.
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_, TTAMachine::HWOperation::name(), BoostGraph< MoveNode, DataDependenceEdge >::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(), BUMoveNodeSelector::BUMoveNodeSelector(), createSubgraph(), CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector(), criticalPathGraph(), BF2Scheduler::handleLoopDDG(), memoryDependenceGraph(), BF2Scheduler::scheduleDDG(), and trueDependenceGraph().
void DataDependenceGraph::setNodeBB | ( | MoveNode & | mn, |
BasicBlockNode & | bblock, | ||
DataDependenceGraph * | modifier | ||
) |
Sets bookkeeping that the given movende belongs to the given basic block.
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.
References BoostGraph< MoveNode, DataDependenceEdge >::childGraphs_, moveNodeBlocks_, and BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_.
Referenced by addNode().
|
inlinevirtual |
Definition at line 224 of file DataDependenceGraph.hh.
References dotProgramOperationNodes_.
Referenced by ResourceConstraintAnalyzer::analyze(), and ResourceConstraintAnalyzer::analyzePreSchedule().
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.
Definition at line 1818 of file DataDependenceGraph.cc.
References MoveNode::cycle(), MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().
Referenced by ResourceConstraintAnalyzer::analyzeRegisterAntideps(), dotString(), BBSchedulerController::executeDDGPass(), and BUBasicBlockScheduler::handleLoopDDG().
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.
mn | MoveNode whose source or guard is renamed. |
guard | true if renamed gaurd, not source. |
Definition at line 4970 of file DataDependenceGraph.cc.
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().
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.
Definition at line 3228 of file DataDependenceGraph.cc.
References BoostGraph< MoveNode, DataDependenceEdge >::descriptor(), MoveNode::destinationOperation(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), BoostGraph< MoveNode, DataDependenceEdge >::graph_, DataDependenceEdge::isBackEdge(), MoveNode::isDestinationOperation(), MoveNode::isPlaced(), MoveNode::isSourceOperation(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and MoveNode::sourceOperation().
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.
References allParamRegs_, BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph(), DataDependenceGraph(), BoostGraph< GraphNode, GraphEdge >::dropEdge(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_MEMORY, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::isFalseDep(), 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().
void DataDependenceGraph::undo | ( | UndoData & | undoData | ) |
Definition at line 5898 of file DataDependenceGraph.cc.
References DataDependenceGraph::UndoData::changedDataEdges, BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), DataDependenceGraph::UndoData::newEdges, DataDependenceGraph::UndoData::removedEdges, and BoostGraph< MoveNode, DataDependenceEdge >::removeEdge().
Referenced by BFRenameLiveRange::undoOnlyMe().
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.
sourceNode | node which writes to the register mergedNode should read. |
mergedNode | node being changed |
Definition at line 2240 of file DataDependenceGraph.cc.
References TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_SRC, TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC, TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC, assert, BoostGraph< MoveNode, DataDependenceEdge >::connectNodes(), TTAProgram::Terminal::copy(), DataDependenceEdge::data(), DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), BoostGraph< MoveNode, DataDependenceEdge >::edge(), DataDependenceEdge::EDGE_OPERATION, DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), TTAProgram::Terminal::equals(), exclusingGuards(), fixAntidepsAfterLoopUnmergeUser(), DataDependenceEdge::guardUse(), BoostGraph< MoveNode, DataDependenceEdge >::headNode(), DataDependenceEdge::headPseudo(), BoostGraph< MoveNode, DataDependenceEdge >::inDegree(), BoostGraph< MoveNode, DataDependenceEdge >::inEdge(), TTAProgram::Terminal::isGPR(), MoveNode::isSourceOperation(), MoveNode::isSourceVariable(), DataDependenceEdge::loopDepth(), MoveNode::move(), BoostGraph< MoveNode, DataDependenceEdge >::outDegree(), BoostGraph< MoveNode, DataDependenceEdge >::outEdge(), DisassemblyRegister::registerName(), TTAProgram::AnnotatedInstructionElement::removeAnnotations(), BoostGraph< MoveNode, DataDependenceEdge >::removeEdge(), ProgramOperation::removeOutputNode(), BoostGraph< MoveNode, DataDependenceEdge >::rootGraph(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), MoveNode::sourceOperation(), DataDependenceEdge::tailPseudo(), and MoveNode::unsetSourceOperation().
Referenced by CycleLookBackSoftwareBypasser::bypassNode(), CycleLookBackSoftwareBypasser::removeBypass(), BUBasicBlockScheduler::undoBypass(), and BUBasicBlockScheduler::unscheduleAllNodes().
DataDependenceGraph::NodeSet DataDependenceGraph::unscheduledMoves | ( | ) | const |
Returns all unscheduled moves.
cycle | The cycle. |
Definition at line 1355 of file DataDependenceGraph.cc.
References MoveNode::isPlaced(), BoostGraph< MoveNode, DataDependenceEdge >::node(), and BoostGraph< MoveNode, DataDependenceEdge >::nodeCount().
Referenced by BUMoveNodeSelector::candidates(), CriticalPathBBMoveNodeSelector::candidates(), CriticalPathBBMoveNodeSelector::isReadyToBeScheduled(), and BasicBlockScheduler::scheduleMove().
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.
mnd | data about the register usage. |
Definition at line 5367 of file DataDependenceGraph.cc.
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().
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.
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.
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().
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.
References onlyGuardDefOfMove(), and BoostGraph< MoveNode, DataDependenceEdge >::successors().
void DataDependenceGraph::writeToXMLFile | ( | std::string | fileName | ) | const |
Writes the graph into an XML file.
Definition at line 1747 of file DataDependenceGraph.cc.
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(), TTAMachine::Component::name(), BoostGraph< MoveNode, DataDependenceEdge >::name(), BoostGraph< MoveNode, DataDependenceEdge >::node(), BoostGraph< MoveNode, DataDependenceEdge >::nodeCount(), GraphNode::nodeID(), DataDependenceEdge::saveState(), XMLSerializer::setDestinationFile(), ObjectState::setValue(), Conversion::toString(), MoveNode::toString(), and XMLSerializer::writeState().
Referenced by BasicBlockPass::ddgSnapshot(), BasicBlockScheduler::ddgSnapshot(), BF2Scheduler::handleLoopDDG(), BBSchedulerController::handleProcedure(), and BF2Scheduler::scheduleDDG().
|
private |
Definition at line 430 of file DataDependenceGraph.hh.
Referenced by createSubgraph(), criticalPathGraph(), firstRegisterCycle(), lastRegisterCycle(), memoryDependenceGraph(), and trueDependenceGraph().
|
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().
|
private |
Definition at line 449 of file DataDependenceGraph.hh.
Referenced by earliestCycle(), edgeLatency(), edgeWeight(), firstRegisterCycle(), lastRegisterCycle(), latestCycle(), and setMachine().
|
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().
|
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().
|
private |
Definition at line 448 of file DataDependenceGraph.hh.
Referenced by createSubgraph(), criticalPathGraph(), earliestCycle(), latestCycle(), machine(), memoryDependenceGraph(), setMachine(), and trueDependenceGraph().
|
private |
Definition at line 438 of file DataDependenceGraph.hh.
Referenced by createSubgraph(), getBasicBlockNode(), setBasicBlockNode(), and setNodeBB().
|
private |
Definition at line 434 of file DataDependenceGraph.hh.
Referenced by addNode(), nodeOfMove(), and removeNode().
|
private |
Definition at line 450 of file DataDependenceGraph.hh.
Referenced by getOperationLatency(), and setMachine().
|
private |
Definition at line 453 of file DataDependenceGraph.hh.
Referenced by ~DataDependenceGraph().
|
private |
Definition at line 454 of file DataDependenceGraph.hh.
Referenced by dotString(), and isRootGraphProcedureDDG().
|
private |
Definition at line 437 of file DataDependenceGraph.hh.
Referenced by addProgramOperation(), createSubgraph(), dropProgramOperation(), programOperation(), programOperationCount(), programOperationPtr(), and ~DataDependenceGraph().
|
private |
Definition at line 455 of file DataDependenceGraph.hh.
Referenced by createSubgraph(), criticalPathGraph(), hasAllRegisterAntidependencies(), hasIntraBBRegisterAntidependencies(), hasSingleBBLoopRegisterAntidependencies(), memoryDependenceGraph(), and trueDependenceGraph().
|
private |
Definition at line 451 of file DataDependenceGraph.hh.
Referenced by edgeWeight(), and setMachine().