#include <BoostGraph.hh>
Classes | |
| class | GraphHashFunctions |
| struct | PathLengthHelper |
| struct | RemovedEdgeDatum |
Public Types | |
| typedef std::set< GraphNode *, typename GraphNode::Comparator > | NodeSet |
| typedef std::set< GraphEdge *, typename GraphEdge::Comparator > | EdgeSet |
| typedef GraphNode | Node |
| The (base) node type managed by this graph. | |
| typedef GraphEdge | Edge |
| The (base) edge type managed by this graph. | |
 Public Types inherited from GraphBase< GraphNode, GraphEdge > | |
| typedef std::set< GraphNode *, typename GraphNode::Comparator > | NodeSet |
| typedef std::set< GraphEdge *, typename GraphEdge::Comparator > | EdgeSet |
| typedef GraphNode | Node |
| Node type of this graph (possibly, a base class). | |
| typedef GraphEdge | Edge |
| Edge type of this graph (possibly, a base class). | |
Public Member Functions | |
| BoostGraph (bool allowLoopEdges=true) | |
| BoostGraph (const TCEString &name, bool allowLoopEdges=true) | |
| BoostGraph (const BoostGraph &other, bool allowLoopEdges=true) | |
| ~BoostGraph () | |
| int | nodeCount () const |
| int | edgeCount () const |
| Node & | node (const int index) const |
| Node & | node (const int index, bool cacheResult) const |
| virtual Edge & | edge (const int index) const |
| virtual void | addNode (Node &node) |
| virtual Edge & | outEdge (const Node &node, const int index) const |
| virtual Edge & | inEdge (const Node &node, const int index) const |
| virtual EdgeSet | outEdges (const Node &node) const |
| virtual EdgeSet | inEdges (const Node &node) const |
| virtual EdgeSet | rootGraphOutEdges (const Node &node) const |
| virtual EdgeSet | rootGraphInEdges (const Node &node) const |
| virtual Edge & | rootGraphInEdge (const Node &node, const int index) const |
| virtual Edge & | rootGraphOutEdge (const Node &node, const int index) const |
| virtual int | rootGraphInDegree (const Node &node) const |
| virtual int | rootGraphOutDegree (const Node &node) const |
| virtual int | outDegree (const Node &node) const |
| virtual int | inDegree (const Node &node) const |
| virtual Node & | tailNode (const Edge &edge) const |
| virtual Node & | headNode (const Edge &edge) const |
| virtual void | connectNodes (const Node &nTail, const Node &nHead, Edge &e) |
| virtual void | disconnectNodes (const Node &nTail, const Node &nHead) |
| virtual void | moveInEdges (const Node &source, const Node &destination) |
| virtual void | moveOutEdges (const Node &source, const Node &destination) |
| virtual void | moveInEdge (const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false) |
| virtual void | moveOutEdge (const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false) |
| virtual void | copyInEdge (const Node &destination, Edge &edge, const Node *tail=NULL) |
| virtual void | copyOutEdge (const Node &destination, Edge &edge, const Node *head=NULL) |
| virtual void | removeNode (Node &node) |
| virtual void | removeEdge (Edge &e) |
| virtual void | dropNode (Node &node) |
| virtual void | dropEdge (Edge &edge) |
| virtual bool | hasEdge (const Node &nTail, const Node &nHead) const |
| virtual NodeSet | rootNodes () const |
| useful utility functions | |
| virtual NodeSet | sinkNodes () const |
| virtual NodeSet | successors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const |
| virtual NodeSet | predecessors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const |
| int | maxPathLength (const GraphNode &node) const |
| int | maxSinkDistance (const GraphNode &node) const |
| int | maxSourceDistance (const GraphNode &node) const |
| bool | isInCriticalPath (const GraphNode &node) const |
| int | height () const |
| void | findAllPaths () const |
| void | detachSubgraph (BoostGraph &subGraph) |
| BoostGraph * | parentGraph () |
| BoostGraph * | rootGraph () |
| const BoostGraph * | rootGraph () const |
| bool | hasNode (const Node &) const |
| virtual const TCEString & | name () const |
| void | setName (const TCEString &newName) |
| bool | hasPath (GraphNode &src, const GraphNode &dest) const |
| void | restoreNodeFromParent (GraphNode &node) |
| bool | detectIllegalCycles () const |
| EdgeSet | connectingEdges (const Node &nTail, const Node &nHead) const |
| Public Member Functions inherited from GraphBase< GraphNode, GraphEdge > | |
| GraphBase () | |
| virtual | ~GraphBase () |
| virtual Node & | tailNode (const Edge &edge) const =0 |
| virtual Node & | headNode (const Edge &edge) const =0 |
| virtual TCEString | dotString () const |
| virtual void | writeToDotFile (const TCEString &fileName) const |
| virtual void | removeEdge (Edge &e)=0 |
| virtual void | connectNodes (const Node &nTail, const Node &nHead, Edge &e)=0 |
Protected Types | |
| typedef std::set< RemovedEdgeDatum > | RemovedEdgeMap |
| typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, Node *, Edge * > | Graph |
| Internal graph type, providing actual graph-like operations. This type definition relies on bundled properties of boost library, which need the host compiler to support partial template specialisation. | |
| typedef boost::graph_traits< Graph > | GraphTraits |
| Traits characterising the internal graph type. | |
| typedef GraphTraits::out_edge_iterator | OutEdgeIter |
| Output edge iterator type. | |
| typedef GraphTraits::in_edge_iterator | InEdgeIter |
| Input edge iterator type. | |
| typedef GraphTraits::edge_iterator | EdgeIter |
| Iterator type for the list of all edges in the graph. | |
| typedef GraphTraits::vertex_iterator | NodeIter |
| Iterator type for the list of all nodes in the graph. | |
| typedef GraphTraits::edge_descriptor | EdgeDescriptor |
| Type with which edges of the graph are seen internally. | |
| typedef GraphTraits::vertex_descriptor | NodeDescriptor |
| Type with which nodes of the graph are seen internally. | |
| typedef hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions > | EdgeDescMap |
| typedef hash_map< const Node *, NodeDescriptor, GraphHashFunctions > | NodeDescMap |
| typedef std::vector< std::vector< int > > | PathCache |
Protected Member Functions | |
| void | restoreRemovedEdges (RemovedEdgeMap removedEdges) |
| EdgeDescriptor | descriptor (const Edge &e) const |
| EdgeDescriptor | edgeDescriptor (const NodeDescriptor &tailNode, const Edge &e) const |
| EdgeDescriptor | edgeDescriptor (const Edge &e, const NodeDescriptor &headNode) const |
| NodeDescriptor | descriptor (const Node &n) const |
| 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 |
| EdgeDescriptor | connectingEdge (const Node &nTail, const Node &nHead) const |
| Node & | tailNode (const Edge &edge, const NodeDescriptor &headNode) const |
| Node & | headNode (const Edge &edge, const NodeDescriptor &tailNode) const |
| void | replaceNodeWithLastNode (GraphNode &dest) |
| void | calculatePathLengths () const |
| void | calculatePathLengthsFast () const |
| void | calculateSinkDistance (const GraphNode &node, int len, bool looping=false) const |
| void | calculateSourceDistances (const GraphNode *startNode=NULL, int startingLength=0, bool looping=false) const |
| void | calculatePathLengthsOnConnect (const GraphNode &nTail, const GraphNode &nHead, GraphEdge &e) |
| void | sinkDistDecreased (const GraphNode &n) const |
| void | sourceDistDecreased (const GraphNode &n) const |
| virtual int | edgeWeight (GraphEdge &e, const GraphNode &n) const |
| void | clearDescriptorCache (EdgeSet edges) |
| virtual void | removeNode (Node &node, BoostGraph *modifierGraph) |
| virtual void | removeEdge (Edge &e, const GraphNode *tailNode, const GraphNode *headNode, BoostGraph *modifierGraph=NULL) |
| virtual void | connectNodes (const Node &nTail, const Node &nHead, Edge &e, GraphBase< GraphNode, GraphEdge > *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) |
| void | constructSubGraph (BoostGraph &subGraph, NodeSet &nodes) |
Protected Attributes | |
| std::unordered_map< const GraphNode *, int > | sourceDistances_ |
| std::unordered_map< const GraphNode *, int > | sinkDistances_ |
| std::unordered_map< const GraphNode *, int > | loopingSourceDistances_ |
| std::unordered_map< const GraphNode *, int > | loopingSinkDistances_ |
| int | height_ |
| Graph | graph_ |
| The internal graph structure. | |
| EdgeDescMap | edgeDescriptors_ |
| NodeDescMap | nodeDescriptors_ |
| BoostGraph< GraphNode, GraphEdge > * | parentGraph_ |
| std::vector< BoostGraph< GraphNode, GraphEdge > * > | childGraphs_ |
| TCEString | name_ |
| int | sgCounter_ |
| std::set< Edge * > | ownedEdges_ |
| bool | allowLoopEdges_ |
| PathCache * | pathCache_ |
Private Member Functions | |
| BoostGraph & | operator= (const BoostGraph &) |
| Assignment forbidden. | |
Detailed Description
Graph-based program representation.
Boost::graph based implementation.
Definition at line 83 of file BoostGraph.hh.
Member Typedef Documentation
◆ Edge
| typedef GraphEdge BoostGraph< GraphNode, GraphEdge >::Edge |
The (base) edge type managed by this graph.
Definition at line 92 of file BoostGraph.hh.
◆ EdgeDescMap
|
protected |
Definition at line 336 of file BoostGraph.hh.
◆ EdgeDescriptor
|
protected |
Type with which edges of the graph are seen internally.
Definition at line 262 of file BoostGraph.hh.
◆ EdgeIter
|
protected |
Iterator type for the list of all edges in the graph.
Definition at line 257 of file BoostGraph.hh.
◆ EdgeSet
| typedef std::set<GraphEdge*, typename GraphEdge::Comparator > BoostGraph< GraphNode, GraphEdge >::EdgeSet |
Definition at line 87 of file BoostGraph.hh.
◆ Graph
|
protected |
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.
Definition at line 247 of file BoostGraph.hh.
◆ GraphTraits
|
protected |
Traits characterising the internal graph type.
Definition at line 250 of file BoostGraph.hh.
◆ InEdgeIter
|
protected |
Input edge iterator type.
Definition at line 255 of file BoostGraph.hh.
◆ Node
| typedef GraphNode BoostGraph< GraphNode, GraphEdge >::Node |
The (base) node type managed by this graph.
- Todo:
- What's the point of these typedefs?
Definition at line 90 of file BoostGraph.hh.
◆ NodeDescMap
|
protected |
Definition at line 338 of file BoostGraph.hh.
◆ NodeDescriptor
|
protected |
Type with which nodes of the graph are seen internally.
Definition at line 264 of file BoostGraph.hh.
◆ NodeIter
|
protected |
Iterator type for the list of all nodes in the graph.
Definition at line 259 of file BoostGraph.hh.
◆ NodeSet
| typedef std::set<GraphNode*, typename GraphNode::Comparator > BoostGraph< GraphNode, GraphEdge >::NodeSet |
Definition at line 86 of file BoostGraph.hh.
◆ OutEdgeIter
|
protected |
Output edge iterator type.
Definition at line 253 of file BoostGraph.hh.
◆ PathCache
|
protected |
Definition at line 387 of file BoostGraph.hh.
◆ RemovedEdgeMap
|
protected |
Definition at line 236 of file BoostGraph.hh.
Constructor & Destructor Documentation
◆ BoostGraph() [1/3]
| BoostGraph< GraphNode, GraphEdge >::BoostGraph | ( | bool | allowLoopEdges = true | ) |
◆ BoostGraph() [2/3]
| BoostGraph< GraphNode, GraphEdge >::BoostGraph | ( | const TCEString & | name, |
| bool | allowLoopEdges = true |
||
| ) |
◆ BoostGraph() [3/3]
| BoostGraph< GraphNode, GraphEdge >::BoostGraph | ( | const BoostGraph< GraphNode, GraphEdge > & | other, |
| bool | allowLoopEdges = true |
||
| ) |
◆ ~BoostGraph()
| BoostGraph< GraphNode, GraphEdge >::~BoostGraph | ( | ) |
Member Function Documentation
◆ addNode()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Reimplemented in DataDependenceGraph.
Referenced by LoopPrologAndEpilogBuilder::addEpilogIntoCfg(), DataDependenceGraph::addNode(), LoopPrologAndEpilogBuilder::addPrologIntoCfg(), llvm::LLVMTCEIRBuilder::buildTCECFG(), OperationDAGBuilder::createOperationNode(), TDGen::createTrivialDAG(), OperationDAGBuilder::finalize(), OperationDAGBuilder::getBinding(), OperationDAGBuilder::getConstantBinding(), ProgramDependenceGraph::processEntry(), ProgramDependenceGraph::processLoopClose(), ProgramDependenceGraph::processPredicate(), and ProgramDependenceGraph::processRegion().
◆ calculatePathLengths()
|
protected |
◆ calculatePathLengthsFast()
|
protected |
◆ calculatePathLengthsOnConnect()
|
protected |
◆ calculateSinkDistance()
|
protected |
◆ calculateSourceDistances()
|
protected |
◆ clearDescriptorCache()
|
protected |
◆ connectingEdge()
|
protected |
◆ connectingEdges()
◆ connectNodes() [1/2]
|
virtual |
Referenced by LoopPrologAndEpilogBuilder::addEpilogIntoCfg(), ProgramDependenceGraph::addLeafEdges(), LoopPrologAndEpilogBuilder::addPrologIntoCfg(), LLVMTCEDataDependenceGraphBuilder::buildLocalDDG(), llvm::LLVMTCEIRBuilder::buildTCECFG(), OperationDAGBuilder::connectOperandToNode(), RegisterCopyAdder::createAntidepsForReg(), ControlDependenceGraph::createPostDominanceTree(), TDGen::createTrivialDAG(), OperationDAGBuilder::finalize(), RegisterCopyAdder::fixDDGEdgesInTempReg(), RegisterCopyAdder::fixDDGEdgesInTempRegChain(), RegisterCopyAdder::fixDDGEdgesInTempRegChainImmediate(), DataDependenceGraph::guardConverted(), DataDependenceGraph::mergeAndKeepUser(), BFConnectNodes::operator()(), ProgramDependenceGraph::processEntry(), ProgramDependenceGraph::processLoopEntry(), ProgramDependenceGraph::processPredicate(), ProgramDependenceGraph::processRegion(), BFRenameLiveRange::renameLiveRange(), RegisterRenamer::renameLiveRange(), BFCopyRegWithOp::splitMove(), BasicBlockScheduler::tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), BFRemoveEdge::undoOnlyMe(), SimpleIfConverter::updateCfg(), Peel2BBLoops::updateCFG(), CopyingDelaySlotFiller::updateFTBBAndCfg(), and CopyingDelaySlotFiller::updateJumpsAndCfg().
◆ connectNodes() [2/2]
|
protectedvirtual |
◆ constructSubGraph()
|
protected |
◆ copyInEdge()
◆ copyOutEdge()
◆ descriptor() [1/2]
|
protected |
◆ descriptor() [2/2]
|
protected |
◆ detachSubgraph()
| void BoostGraph< GraphNode, GraphEdge >::detachSubgraph | ( | BoostGraph< GraphNode, GraphEdge > & | subGraph | ) |
◆ detectIllegalCycles()
| bool BoostGraph< GraphNode, GraphEdge >::detectIllegalCycles | ( | ) | const |
◆ disconnectNodes()
|
virtual |
◆ dropEdge()
|
virtual |
Referenced by DataDependenceGraph::trueDependenceGraph().
◆ dropNode()
|
virtual |
Referenced by BUBasicBlockScheduler::finalizeSchedule(), BF2Scheduler::handleLoopDDG(), BFDREEarly::operator()(), BFDRELate::operator()(), BFDRELoop::operator()(), BFDropPreShared::operator()(), BFKillNode::operator()(), BFShareOperandLate::operator()(), BFShareOperandWithScheduled::operator()(), BFPostpassDRE::operator()(), BFPostpassLoopDRE::operator()(), CycleLookBackSoftwareBypasser::removeDeadResults(), BFRemoveLoopChecksAndJump::removeMoveFromQueue(), BFRemoveLoopChecksAndJump::removePoFromQueue(), and BF2Scheduler::scheduleDDG().
◆ edge()
|
virtual |
◆ edgeCount()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by ResourceConstraintAnalyzer::dumpGraphWithStats(), and ProgramDependenceGraph::ProgramDependenceGraph().
◆ edgeDescriptor() [1/2]
|
protected |
◆ edgeDescriptor() [2/2]
|
protected |
◆ edgeWeight()
|
protectedvirtual |
Reimplemented in DataDependenceGraph.
◆ findAllPaths()
| void BoostGraph< GraphNode, GraphEdge >::findAllPaths | ( | ) | const |
Referenced by VirtRegIndependenceGraph::VirtRegIndependenceGraph().
◆ hasEdge() [1/3]
|
protected |
◆ hasEdge() [2/3]
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
◆ hasEdge() [3/3]
|
protected |
◆ hasNode()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by CopyingDelaySlotFiller::bbnScheduled(), OperationDAGBuilder::connectOperandToNode(), MoveNodeDuplicator::disposeMoveNode(), MoveNodeDuplicator::duplicateMoveNode(), BF2Scheduler::handleLoopDDG(), MoveNodeGroup::isAlive(), ExecutionPipelineBroker::isLoopBypass(), ExecutionPipelineResource::isLoopBypass(), BUMoveNodeSelector::isReadyToBeScheduled(), BUMoveNodeSelector::mightBeReady(), CopyingDelaySlotFiller::mightFillIncomingTo(), CycleLookBackSoftwareBypasser::removeDeadResults(), BF2Scheduler::scheduleDDG(), BUBasicBlockScheduler::scheduleOperandWrites(), RegisterRenamer::updateAntiEdgesFromLRTo(), and MoveNodeGroup::writesJumpGuard().
◆ hasPath()
| bool BoostGraph< GraphNode, GraphEdge >::hasPath | ( | GraphNode & | src, |
| const GraphNode & | dest | ||
| ) | const |
◆ headNode() [1/2]
|
virtual |
Referenced by LoopPrologAndEpilogBuilder::addEpilogIntoCfg(), ResourceConstraintAnalyzer::analyzeRegisterAntideps(), CopyingDelaySlotFiller::bbnScheduled(), BFEarlyBypasser::bypassSourceLatestCycle(), TDGen::canBeImmediate(), SimpleIfConverter::canConvert(), PreOptimizer::checkGuardReversalAllowed(), BFOptimization::checkPrologDDG(), TDGen::constantNodeString(), ControlDependenceGraph::createPostDominanceTree(), ControlDependenceGraph::detectControlDependencies(), SimpleIfConverter::detectDiamond(), SimpleIfConverter::detectTriangleViaFt(), SimpleIfConverter::detectTriangleViaJump(), ResourceConstraintAnalyzer::dumpGraphWithStats(), TDGen::emulatingOpNodeLLVMName(), OperationDAGSelector::findDags(), TDGen::immediateOperandNameForEmulatedOperation(), PreOptimizer::inverseGuardsOfHeads(), DataDependenceGraph::mergeAndKeepSource(), DataDependenceGraph::mergeAndKeepUser(), OperationDAGBehavior::OperationDAGBehavior(), BFPushAntidepsDown::operator()(), BFRemoveLoopChecksAndJump::operator()(), BFRemoveGuardsFromSuccs::operator()(), ProgramDependenceGraph::ProgramDependenceGraph(), LiveRangeData::registersAlive(), ProgramDependenceGraph::removeGuardedJump(), BFRegCopyAfter::splitMove(), BFRegCopyBefore::splitMove(), FUGen::subOpConnection(), SimpleIfConverter::successors(), Peel2BBLoops::testIf2BBLoop(), PreOptimizer::tryToOptimizeAddressReg(), SimpleIfConverter::updateCfg(), BFMergeAndKeepUser::updateEdges(), CopyingDelaySlotFiller::updateFTBBAndCfg(), OperationDAGConverter::writeNode(), and MoveNodeGroup::writesJumpGuard().
◆ headNode() [2/2]
|
protected |
◆ height()
| int BoostGraph< GraphNode, GraphEdge >::height | ( | ) | const |
◆ inDegree()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by LoopPrologAndEpilogBuilder::addPrologIntoCfg(), TDGen::canBeImmediate(), BFRemoveLoopChecksAndJump::checkAliveMove(), BFRemoveLoopChecksAndJump::checkAlivePO(), TDGen::constantNodeString(), TDGen::dagNodeToString(), SimpleIfConverter::detectDiamond(), SimpleIfConverter::detectTriangleViaFt(), SimpleIfConverter::detectTriangleViaJump(), TDGen::emulatingOpNodeLLVMName(), MemoryAliasAnalyzer::findTwoPartAddressOperands(), OperationDAGBehavior::OperationDAGBehavior(), TDGen::operationNodeToString(), BFMergeAndKeepUser::operator()(), ProgramDependenceGraph::ProgramDependenceGraph(), BFRemoveLoopChecksAndJump::removeMoveFromQueue(), BFRemoveLoopChecksAndJump::removePoFromQueue(), Peel2BBLoops::testIf2BBLoop(), CopyingDelaySlotFiller::updateFTBBAndCfg(), CopyingDelaySlotFiller::updateJumpsAndCfg(), TDGen::writeEmulationPattern(), and OperationDAGConverter::writeNode().
◆ inEdge()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by LoopPrologAndEpilogBuilder::addPrologIntoCfg(), BFRemoveLoopChecksAndJump::checkAliveMove(), BFRemoveLoopChecksAndJump::checkAlivePO(), TDGen::dagNodeToString(), TDGen::emulatingOpNodeLLVMName(), MemoryAliasAnalyzer::findTwoPartAddressOperands(), OperationDAGBehavior::OperationDAGBehavior(), TDGen::operationNodeToString(), BFMergeAndKeepUser::operator()(), ProgramDependenceGraph::ProgramDependenceGraph(), BFRemoveLoopChecksAndJump::removeMoveFromQueue(), BFRemoveLoopChecksAndJump::removePoFromQueue(), BFCopyRegWithOp::splitMove(), Peel2BBLoops::testIf2BBLoop(), BFCopyRegWithOp::undoSplit(), TDGen::writeEmulationPattern(), and OperationDAGConverter::writeNode().
◆ inEdges()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by CopyingDelaySlotFiller::areAllJumpPredsFilled(), CopyingDelaySlotFiller::areAllJumpPredsScheduled(), CycleLookBackSoftwareBypasser::bypassNode(), PreOptimizer::checkGuardReversalAllowed(), CopyingDelaySlotFiller::checkIncomingDeps(), BFOptimization::checkPrologDDG(), BF2Scheduler::findBypassEdge(), CopyingDelaySlotFiller::finishBB(), RegisterCopyAdder::fixDDGEdgesInTempReg(), RegisterCopyAdder::fixDDGEdgesInTempRegChain(), RegisterCopyAdder::fixDDGEdgesInTempRegChainImmediate(), ExecutionPipelineResource::isLoopBypass(), ProGeTools::maxLatencyToNode(), Automagic::maxLatencyToNode(), BFPushDepsUp::operator()(), BFRemoveGuard::operator()(), BFRemoveGuardFromSucc::operator()(), BasicBlockScheduler::scheduleInputOperandTempMoves(), BUBasicBlockScheduler::scheduleInputOperandTempMoves(), BFRegCopyAfter::splitMove(), BFRegCopyBefore::splitMove(), Peel2BBLoops::testIf2BBLoop(), PreOptimizer::tryToOptimizeAddressReg(), BasicBlockScheduler::tryToOptimizeWaw(), and BUBasicBlockScheduler::tryToOptimizeWaw().
◆ isInCriticalPath()
|
inline |
Definition at line 179 of file BoostGraph.hh.
References BoostGraph< GraphNode, GraphEdge >::height(), BoostGraph< GraphNode, GraphEdge >::maxSinkDistance(), BoostGraph< GraphNode, GraphEdge >::maxSourceDistance(), and BoostGraph< GraphNode, GraphEdge >::node().
◆ maxPathLength()
| int BoostGraph< GraphNode, GraphEdge >::maxPathLength | ( | const GraphNode & | node | ) | const |
◆ maxSinkDistance()
| int BoostGraph< GraphNode, GraphEdge >::maxSinkDistance | ( | const GraphNode & | node | ) | const |
◆ maxSourceDistance()
| int BoostGraph< GraphNode, GraphEdge >::maxSourceDistance | ( | const GraphNode & | node | ) | const |
◆ moveInEdge()
|
virtual |
Referenced by LoopPrologAndEpilogBuilder::addEpilogIntoCfg(), LoopPrologAndEpilogBuilder::addPrologIntoCfg(), RegisterCopyAdder::fixDDGEdgesInTempReg(), RegisterCopyAdder::fixDDGEdgesInTempRegChain(), RegisterCopyAdder::fixDDGEdgesInTempRegChainImmediate(), BFCopyRegWithOp::splitMove(), and BFCopyRegWithOp::undoSplit().
◆ moveInEdges() [1/2]
|
virtual |
◆ moveInEdges() [2/2]
|
protected |
◆ moveOutEdge()
◆ moveOutEdges() [1/2]
|
virtual |
◆ moveOutEdges() [2/2]
|
protectedvirtual |
◆ name()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by LoopAnalyzer::analyze(), DataDependenceGraphBuilder::build(), llvm::LLVMTCEIRBuilder::compileOptimized(), DataDependenceGraphBuilder::constructIndividualBB(), DataDependenceGraphBuilder::createRegisterDeps(), BasicBlockScheduler::ddgSnapshot(), BBSchedulerController::executeDDGPass(), BBSchedulerController::handleBBNode(), SimpleIfConverter::handleControlFlowGraph(), BF2Scheduler::handleDDG(), BF2Scheduler::handleLoopDDG(), BBSchedulerController::handleProcedure(), FalseAliasAnalyzer::isEnabled(), BF2Scheduler::scheduleDDG(), BasicBlockScheduler::scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), BasicBlockScheduler::scheduleRRMove(), BUBasicBlockScheduler::scheduleRRMove(), and DataDependenceGraphBuilder::searchRegisterDeaths().
◆ node() [1/2]
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by ResourceConstraintAnalyzer::analyzeRegisterAntideps(), LoopPrologAndEpilogBuilder::build(), LLVMTCEDataDependenceGraphBuilder::buildFromCFG(), OperationDAGBehavior::canBeSimulated(), ProGeTools::canGenerateFromDAG(), Automagic::canGenerateFromDAG(), PreOptimizer::cfgAllowsJumpReversal(), DataDependenceGraphBuilder::clearUnneededBookkeeping(), ProcedurePass::copyCfgToProcedure(), OperationDAGSelector::countUnknownOperations(), OperationDAGConverter::createOsalCode(), ControlDependenceGraph::createPostDominanceTree(), OperationDAGConverter::createSimulationCode(), DataDependenceGraph::createSubgraph(), ControlDependenceGraph::detectControlDependencies(), ResourceConstraintAnalyzer::dumpGraphWithStats(), ControlFlowGraphPass::executeBasicBlockPass(), CopyingDelaySlotFiller::fillDelaySlots(), CompiledSimCodeGenerator::findBasicBlocks(), OperationDAGSelector::findDags(), BF2Scheduler::findJump(), DataDependenceGraphBuilder::findStaticRegisters(), BBSchedulerController::handleCFGDDG(), ScheduleEstimator::handleControlFlowGraph(), CallsToJumps::handleControlFlowGraph(), Peel2BBLoops::handleControlFlowGraph(), BUBasicBlockScheduler::handleDDG(), BasicBlockScheduler::handleDDG(), BF2Scheduler::handleLoopDDG(), BasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), DataDependenceGraphBuilder::initializeBBStates(), RegisterRenamer::initializeFreeRegisters(), BoostGraph< GraphNode, GraphEdge >::isInCriticalPath(), OperationDAGBehavior::OperationDAGBehavior(), TDGen::operationDAGCanBeMatched(), BFRemoveLoopChecksAndJump::operator()(), BFPostpassBypasser::operator()(), BoostGraph< GraphNode, GraphEdge >::GraphHashFunctions::operator()(), ResourceConstraintAnalyzer::optimalScheduleResourceUsage(), ProgramDependenceGraph::ProgramDependenceGraph(), LiveRangeData::registersAlive(), SimpleIfConverter::searchCandidate(), and BF2Scheduler::unreservePreallocatedFUs().
◆ node() [2/2]
| Node & BoostGraph< GraphNode, GraphEdge >::node | ( | const int | index, |
| bool | cacheResult | ||
| ) | const |
◆ nodeCount()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by ResourceConstraintAnalyzer::analyzeRegisterAntideps(), LoopPrologAndEpilogBuilder::build(), LLVMTCEDataDependenceGraphBuilder::buildFromCFG(), llvm::LLVMTCEIRBuilder::buildTCECFG(), SoftwareBypasser::bypass(), OperationDAGBehavior::canBeSimulated(), BUMoveNodeSelector::candidates(), CriticalPathBBMoveNodeSelector::candidates(), ProGeTools::canGenerateFromDAG(), Automagic::canGenerateFromDAG(), PreOptimizer::cfgAllowsJumpReversal(), DataDependenceGraphBuilder::clearUnneededBookkeeping(), ProcedurePass::copyCfgToProcedure(), OperationDAGSelector::countUnknownOperations(), OperationDAGConverter::createOsalCode(), ControlDependenceGraph::createPostDominanceTree(), OperationDAGConverter::createSimulationCode(), DataDependenceGraph::createSubgraph(), ControlDependenceGraph::detectControlDependencies(), ProgramDependenceGraph::disassemble(), ResourceConstraintAnalyzer::dumpGraphWithStats(), ControlFlowGraphPass::executeBasicBlockPass(), CopyingDelaySlotFiller::fillDelaySlots(), CompiledSimCodeGenerator::findBasicBlocks(), OperationDAGSelector::findDags(), BF2Scheduler::findJump(), DataDependenceGraphBuilder::findStaticRegisters(), BBSchedulerController::handleBBNode(), BBSchedulerController::handleCFGDDG(), ControlDependenceGraphPass::handleControlDependenceGraph(), ScheduleEstimator::handleControlFlowGraph(), CallsToJumps::handleControlFlowGraph(), Peel2BBLoops::handleControlFlowGraph(), BUBasicBlockScheduler::handleDDG(), DDGPass::handleDDG(), BasicBlockScheduler::handleDDG(), BF2Scheduler::handleLoopDDG(), BasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), BBSchedulerController::handleProcedure(), DataDependenceGraphBuilder::initializeBBStates(), RegisterRenamer::initializeFreeRegisters(), CriticalPathBBMoveNodeSelector::isReadyToBeScheduled(), OperationDAGBehavior::OperationDAGBehavior(), TDGen::operationDAGCanBeMatched(), BFRemoveLoopChecksAndJump::operator()(), BFPostpassBypasser::operator()(), ResourceConstraintAnalyzer::optimalScheduleResourceUsage(), ProgramDependenceGraph::ProgramDependenceGraph(), LiveRangeData::registersAlive(), SoftwareBypasser::removeBypass(), SoftwareBypasser::removeDeadResults(), BF2Scheduler::scheduleDDG(), BasicBlockScheduler::scheduleMove(), SimpleIfConverter::searchCandidate(), OperationDAGSelector::OperationDAGList::smallestNodeCount(), and BF2Scheduler::unreservePreallocatedFUs().
◆ operator=()
|
private |
Assignment forbidden.
◆ outDegree()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by LoopPrologAndEpilogBuilder::addEpilogIntoCfg(), ResourceConstraintAnalyzer::analyzeRegisterAntideps(), TDGen::canBeImmediate(), PreOptimizer::cfgAllowsJumpReversal(), TDGen::constantNodeString(), ControlDependenceGraph::createPostDominanceTree(), TDGen::dagNodeToString(), ControlDependenceGraph::detectControlDependencies(), SimpleIfConverter::detectDiamond(), SimpleIfConverter::detectTriangleViaFt(), SimpleIfConverter::detectTriangleViaJump(), TDGen::emulatingOpNodeLLVMName(), OperationDAGBehavior::OperationDAGBehavior(), BFRemoveLoopChecksAndJump::operator()(), ProgramDependenceGraph::removeGuardedJump(), SimpleIfConverter::searchCandidate(), Peel2BBLoops::testIf2BBLoop(), DataDependenceGraph::trueDependenceGraph(), and OperationDAGConverter::writeNode().
◆ outEdge()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by LoopPrologAndEpilogBuilder::addEpilogIntoCfg(), ResourceConstraintAnalyzer::analyzeRegisterAntideps(), TDGen::canBeImmediate(), PreOptimizer::cfgAllowsJumpReversal(), TDGen::constantNodeString(), ControlDependenceGraph::createPostDominanceTree(), ControlDependenceGraph::detectControlDependencies(), SimpleIfConverter::detectDiamond(), SimpleIfConverter::detectTriangleViaFt(), SimpleIfConverter::detectTriangleViaJump(), TDGen::emulatingOpNodeLLVMName(), OperationDAGBehavior::OperationDAGBehavior(), BFRemoveLoopChecksAndJump::operator()(), ProgramDependenceGraph::removeGuardedJump(), BFCopyRegWithOp::splitMove(), SimpleIfConverter::successors(), Peel2BBLoops::testIf2BBLoop(), DataDependenceGraph::trueDependenceGraph(), BFCopyRegWithOp::undoSplit(), and OperationDAGConverter::writeNode().
◆ outEdges()
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Referenced by ProgramDependenceGraph::addLeafEdges(), CopyingDelaySlotFiller::bbnScheduled(), BFEarlyBypasser::bypassSourceLatestCycle(), SimpleIfConverter::canConvert(), BFOptimization::checkPrologDDG(), SimpleIfConverter::detectDiamond(), BFDRELoop::dreAllowed(), BFPostpassLoopDRE::dreAllowed(), OperationDAGSelector::findDags(), RegisterCopyAdder::fixDDGEdgesInTempReg(), RegisterCopyAdder::fixDDGEdgesInTempRegChain(), RegisterCopyAdder::fixDDGEdgesInTempRegChainImmediate(), TDGen::immediateOperandNameForEmulatedOperation(), BFPushAntidepsDown::operator()(), BFRemoveGuard::operator()(), BFRemoveGuardFromSucc::operator()(), BFRemoveGuardsFromSuccs::operator()(), LiveRangeData::registersAlive(), BFRegCopyAfter::splitMove(), BFRegCopyBefore::splitMove(), Peel2BBLoops::testIf2BBLoop(), PreOptimizer::tryToOptimizeAddressReg(), PreOptimizer::tryToRemoveGuardInversingOp(), SimpleIfConverter::updateCfg(), CopyingDelaySlotFiller::updateFTBBAndCfg(), and MoveNodeGroup::writesJumpGuard().
◆ parentGraph()
| BoostGraph * BoostGraph< GraphNode, GraphEdge >::parentGraph | ( | ) |
Referenced by BF2Scheduler::handleLoopDDG().
◆ predecessors()
|
virtual |
Referenced by TDGen::constantNodeString(), BUBasicBlockScheduler::finalizeSchedule(), ResourceConstraintAnalyzer::findResourceConstrainedParent(), MemoryAliasAnalyzer::findTwoPartAddressOperands(), BUMoveNodeSelector::notifyScheduled(), BFRenameLiveRange::notifySelector(), BFDREEarly::operator()(), BFDRELate::operator()(), BFLateBypass::operator()(), BFEarlyBypass::operator()(), BUBasicBlockScheduler::precedingTempMove(), RegisterRenamer::renameLiveRange(), TDGen::subPattern(), and DataDependenceGraphBuilder::updatePreceedingRegistersUsedAfter().
◆ removeEdge() [1/2]
|
virtual |
Referenced by ControlDependenceGraph::createPostDominanceTree(), BFRemoveEdge::operator()(), BasicBlockScheduler::tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), BFRenameLiveRange::undoNewAntiDeps(), BFKillNode::undoOnlyMe(), BFConnectNodes::undoOnlyMe(), and SimpleIfConverter::updateCfg().
◆ removeEdge() [2/2]
|
protectedvirtual |
◆ removeNode() [1/2]
|
virtual |
Implements GraphBase< GraphNode, GraphEdge >.
Reimplemented in DataDependenceGraph.
Referenced by CycleLookBackSoftwareBypasser::clearCaches(), BUBasicBlockScheduler::clearRemovedNodes(), BF2Scheduler::finalizeSchedule(), DataDependenceGraph::removeNode(), CopyingDelaySlotFiller::updateFTBBAndCfg(), and CopyingDelaySlotFiller::updateJumpsAndCfg().
◆ removeNode() [2/2]
|
protectedvirtual |
◆ replaceNodeWithLastNode()
|
protected |
◆ restoreNodeFromParent()
| void BoostGraph< GraphNode, GraphEdge >::restoreNodeFromParent | ( | GraphNode & | node | ) |
◆ restoreRemovedEdges()
|
protected |
◆ rootGraph() [1/2]
| BoostGraph * BoostGraph< GraphNode, GraphEdge >::rootGraph | ( | ) |
Referenced by LoopPrologAndEpilogBuilder::build(), CycleLookBackSoftwareBypasser::bypassNode(), CycleLookBackSoftwareBypasser::clearCaches(), BUBasicBlockScheduler::clearRemovedNodes(), BBSchedulerController::executeDDGPass(), BF2Scheduler::finalizeSchedule(), BUBasicBlockScheduler::finalizeSchedule(), RegisterCopyAdder::fixDDGEdgesInTempReg(), RegisterCopyAdder::fixDDGEdgesInTempRegChain(), RegisterCopyAdder::fixDDGEdgesInTempRegChainImmediate(), BFRemoveLoopChecksAndJump::operator()(), BFConnectNodes::operator()(), BFRemoveEdge::operator()(), CycleLookBackSoftwareBypasser::removeDeadResults(), RegisterRenamer::renameLiveRange(), BFOptimization::rootDDG(), BFCopyRegWithOp::splitMove(), BFRegCopyAfter::splitMove(), BFRegCopyBefore::splitMove(), BFConnectNodes::undoOnlyMe(), BFRemoveEdge::undoOnlyMe(), BFCopyRegWithOp::undoSplit(), and BFMergeAndKeepUser::updateEdges().
◆ rootGraph() [2/2]
| const BoostGraph * BoostGraph< GraphNode, GraphEdge >::rootGraph | ( | ) | const |
◆ rootGraphInDegree()
|
virtual |
Referenced by BFMergeAndKeepUser::updateEdges().
◆ rootGraphInEdge()
|
virtual |
Referenced by BFMergeAndKeepUser::updateEdges().
◆ rootGraphInEdges()
|
virtual |
◆ rootGraphOutDegree()
|
virtual |
Referenced by BFMergeAndKeepUser::updateEdges().
◆ rootGraphOutEdge()
|
virtual |
Referenced by BFMergeAndKeepUser::updateEdges().
◆ rootGraphOutEdges()
|
virtual |
◆ rootNodes()
|
virtual |
useful utility functions
Referenced by TDGen::immediateOperandNameForEmulatedOperation(), and CriticalPathBBMoveNodeSelector::initializeReadylist().
◆ setName()
|
inline |
Definition at line 195 of file BoostGraph.hh.
References BoostGraph< GraphNode, GraphEdge >::name_.
◆ sinkDistDecreased()
|
protected |
◆ sinkNodes()
|
virtual |
◆ sourceDistDecreased()
|
protected |
◆ successors()
|
virtual |
Referenced by BF2Scheduler::hasUnscheduledSuccessors(), CriticalPathBBMoveNodeSelector::notifyScheduled(), BFRenameLiveRange::notifySelector(), BFRescheduleSuccessorsClose::operator()(), DataDependenceGraphBuilder::queueFirstBB(), CycleLookBackSoftwareBypasser::removeDeadResults(), RegisterRenamer::renameLiveRange(), DataDependenceGraphBuilder::setSucceedingPredeps(), BasicBlockScheduler::succeedingTempMove(), SimpleIfConverter::successors(), and CopyingDelaySlotFiller::updateJumpsAndCfg().
◆ tailNode() [1/2]
|
virtual |
Referenced by LoopPrologAndEpilogBuilder::addPrologIntoCfg(), CopyingDelaySlotFiller::areAllJumpPredsFilled(), CopyingDelaySlotFiller::areAllJumpPredsScheduled(), CycleLookBackSoftwareBypasser::bypassNode(), CopyingDelaySlotFiller::checkIncomingDeps(), BFOptimization::checkPrologDDG(), TDGen::dagNodeToString(), ResourceConstraintAnalyzer::dumpGraphWithStats(), TDGen::emulatingOpNodeLLVMName(), DataDependenceGraph::findLoopIndexInit(), MemoryAliasAnalyzer::findTwoPartAddressOperands(), CopyingDelaySlotFiller::finishBB(), DataDependenceGraph::guardConverted(), ProGeTools::maxLatencyToNode(), Automagic::maxLatencyToNode(), DataDependenceGraph::mergeAndKeepUser(), CopyingDelaySlotFiller::mightFillIncomingTo(), OperationDAGBehavior::OperationDAGBehavior(), TDGen::operationNodeToString(), BFEarlyBypasser::operator()(), BFPushDepsUp::operator()(), ProgramDependenceGraph::ProgramDependenceGraph(), BFRemoveLoopChecksAndJump::removeMoveFromQueue(), BFRemoveLoopChecksAndJump::removePoFromQueue(), BasicBlockScheduler::scheduleInputOperandTempMoves(), BUBasicBlockScheduler::scheduleInputOperandTempMoves(), BFRegCopyAfter::splitMove(), BFRegCopyBefore::splitMove(), FUGen::subOpConnection(), Peel2BBLoops::testIf2BBLoop(), BFPostpassBypasser::tryBypassNode(), PreOptimizer::tryToOptimizeAddressReg(), BasicBlockScheduler::tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), BFMergeAndKeepUser::updateEdges(), TDGen::writeEmulationPattern(), and OperationDAGConverter::writeNode().
◆ tailNode() [2/2]
|
protected |
Member Data Documentation
◆ allowLoopEdges_
|
protected |
Definition at line 384 of file BoostGraph.hh.
◆ childGraphs_
|
protected |
Definition at line 378 of file BoostGraph.hh.
◆ edgeDescriptors_
|
mutableprotected |
Definition at line 340 of file BoostGraph.hh.
◆ graph_
|
protected |
The internal graph structure.
Definition at line 331 of file BoostGraph.hh.
◆ height_
|
mutableprotected |
Definition at line 328 of file BoostGraph.hh.
◆ loopingSinkDistances_
|
mutableprotected |
Definition at line 326 of file BoostGraph.hh.
◆ loopingSourceDistances_
|
mutableprotected |
Definition at line 324 of file BoostGraph.hh.
◆ name_
|
protected |
Definition at line 380 of file BoostGraph.hh.
Referenced by BoostGraph< GraphNode, GraphEdge >::setName().
◆ nodeDescriptors_
|
mutableprotected |
Definition at line 341 of file BoostGraph.hh.
◆ ownedEdges_
|
protected |
Definition at line 383 of file BoostGraph.hh.
◆ parentGraph_
|
protected |
Definition at line 377 of file BoostGraph.hh.
◆ pathCache_
|
mutableprotected |
Definition at line 388 of file BoostGraph.hh.
◆ sgCounter_
|
protected |
Definition at line 381 of file BoostGraph.hh.
◆ sinkDistances_
|
mutableprotected |
Definition at line 320 of file BoostGraph.hh.
◆ sourceDistances_
|
mutableprotected |
Definition at line 318 of file BoostGraph.hh.
The documentation for this class was generated from the following file:
