BUMoveNodeSelector Class Reference

#include <BUMoveNodeSelector.hh>

Inheritance diagram for BUMoveNodeSelector:

Collaboration diagram for BUMoveNodeSelector:

Public Member Functions
	BUMoveNodeSelector (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &machine)
	BUMoveNodeSelector (DataDependenceGraph &bigDDG, TTAProgram::BasicBlock &bb, const TTAMachine::Machine &machine)
	BUMoveNodeSelector (DataDependenceGraph &ddg, const TTAMachine::Machine &machine)
virtual	~BUMoveNodeSelector ()
virtual MoveNodeGroup	candidates ()
virtual void	notifyScheduled (MoveNode &node)
virtual void	mightBeReady (MoveNode &node)
virtual DataDependenceGraph &	dataDependenceGraph ()
virtual void	initializeReadylist ()
	Initializes ready list from nodes that are ready. More...
Public Member Functions inherited from MoveNodeSelector
	MoveNodeSelector ()
virtual	~MoveNodeSelector ()

Static Public Member Functions
static void	queueOperation (ProgramOperation &po, const DataDependenceGraph::NodeSet &nodes, DataDependenceGraph::NodeSet &queue)

Private Member Functions
bool	isReadyToBeScheduled (DataDependenceGraph::NodeSet &nodes) const
bool	isReadyToBeScheduled (MoveNode &mn, DataDependenceGraph::NodeSet &nodes) const
virtual bool	isReadyToBeScheduled (MoveNodeGroup &nodes) const

Private Attributes
DataDependenceGraph *	ddg_
	The data dependence graph built from the basic block. More...
ReadyMoveNodeGroupListBU	readyList_
	The prioritized ready list. More...
bool	ddgOwned_

Detailed Description

Selects move nodes from a basic block and prioritizes move nodes on the critical path of the data dependence graph. This version prioritiezed for bottom up scheduling.

Definition at line 70 of file BUMoveNodeSelector.hh.

Constructor & Destructor Documentation

BUMoveNodeSelector() [1/3]

BUMoveNodeSelector::BUMoveNodeSelector	(	TTAProgram::BasicBlock &	bb,
		const TTAMachine::Machine &	machine
	)

Constructor.

Parameters

bb	The basic block from which to select moves.

Definition at line 109 of file BUMoveNodeSelector.cc.

                                                                : 
    ddgOwned_(true) {    
    DataDependenceGraphBuilder ddgBuilder;
    ddg_ = ddgBuilder.build(
        bb,DataDependenceGraph::INTRA_BB_ANTIDEPS, machine);
    ddg_->setMachine(machine);
    initializeReadylist();
#if 0    
        ddg_->setCycleGrouping(true);
        ddg_->writeToDotFile("ddg.dot");    
#endif
}

References DataDependenceGraphBuilder::build(), ddg_, initializeReadylist(), DataDependenceGraph::INTRA_BB_ANTIDEPS, machine, DataDependenceGraph::setCycleGrouping(), DataDependenceGraph::setMachine(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

BUMoveNodeSelector() [2/3]

BUMoveNodeSelector::BUMoveNodeSelector	(	DataDependenceGraph &	bigDDG,
		TTAProgram::BasicBlock &	bb,
		const TTAMachine::Machine &	machine
	)

Constructor. Creates subgraph of the given big graph

Parameters

bigDDG	big ddg containing more than just the basic block
bb	basic block for this selector.

Definition at line 88 of file BUMoveNodeSelector.cc.

    : ddgOwned_(true) {
    try {
        ddg_ = bigDDG.createSubgraph(bb);
        ddg_->setMachine(machine);
    } catch (InstanceNotFound& inf) {
        ModuleRunTimeError e(
            __FILE__,__LINE__,__func__,"Creation of subgraph failed");
        e.setCause(inf);
        throw e;
    }
    initializeReadylist();
}

References __func__, DataDependenceGraph::createSubgraph(), ddg_, initializeReadylist(), machine, Exception::setCause(), and DataDependenceGraph::setMachine().

Here is the call graph for this function:

BUMoveNodeSelector() [3/3]

BUMoveNodeSelector::BUMoveNodeSelector	(	DataDependenceGraph &	ddg,
		const TTAMachine::Machine &	machine
	)

Constructor.

Parameters

ddg	The data dependence graph from which to select moves. Selector does not take the ownership of the ddg.

Definition at line 129 of file BUMoveNodeSelector.cc.

                                                                : 
    ddg_(&ddg), ddgOwned_(false) {    
    ddg_->setMachine(machine);
    initializeReadylist();
}

References ddg_, initializeReadylist(), machine, and DataDependenceGraph::setMachine().

Here is the call graph for this function:

~BUMoveNodeSelector()

BUMoveNodeSelector::~BUMoveNodeSelector ( )

virtual

Destructor.

Definition at line 138 of file BUMoveNodeSelector.cc.

                                        {
    if (ddgOwned_) {
        delete ddg_;
    }
}

References ddg_, and ddgOwned_.

Member Function Documentation

candidates()

MoveNodeGroup BUMoveNodeSelector::candidates ( )

virtual

Returns a group of move nodes which should be scheduled next.

Returns

Move node group.

Implements MoveNodeSelector.

Definition at line 157 of file BUMoveNodeSelector.cc.

                               {
    
    // find a MoveNodeGroup with unscheduled MoveNodes
    while (readyList_.size() > 0) {
        MoveNodeGroup moves = readyList_.top();
        if (!moves.isAlive() || moves.isScheduled() ||
            !isReadyToBeScheduled(moves))
            readyList_.pop();
        else
            return moves;
    }
    // nothing in ready list, let's see if there are "orphan" nodes
    // still to schedule
    if (ddg_->nodeCount() - ddg_->scheduledNodeCount() > 0) {
        DataDependenceGraph::NodeSet unscheduled = ddg_->unscheduledMoves();
        for (DataDependenceGraph::NodeSet::iterator i = unscheduled.begin(); 
             i != unscheduled.end();
             ++i) {
            MoveNode& node = **i;
#ifdef WARN_ORPHAN_NODES
            std::cerr << "Found orphan node: " << node.toString() << " max src dist: " 
                      << ddg_->maxSourceDistance(node) << " sink dist: " << 
                ddg_->maxSinkDistance(node) << std::endl;
            ddg_->writeToDotFile("oprhan.dot");
#ifdef ABORT_ORPHAN_NODES
            abortWithError("orphan node!");
#endif
#endif
            mightBeReady(node);
        }
    }
    
    // did we find new nodes?
    while (readyList_.size() > 0) {
        MoveNodeGroup moves = readyList_.top();
        if (moves.isScheduled())
            readyList_.pop();
        else
            return moves;
    }
    
    // return an empty move node group
    return MoveNodeGroup();
}

References abortWithError, ddg_, MoveNodeGroup::isAlive(), isReadyToBeScheduled(), MoveNodeGroup::isScheduled(), BoostGraph< GraphNode, GraphEdge >::maxSinkDistance(), BoostGraph< GraphNode, GraphEdge >::maxSourceDistance(), mightBeReady(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), readyList_, DataDependenceGraph::scheduledNodeCount(), MoveNode::toString(), DataDependenceGraph::unscheduledMoves(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by BUBasicBlockScheduler::handleDDG(), BUBasicBlockScheduler::handleLoopDDG(), BF2Scheduler::handleLoopDDG(), and BF2Scheduler::scheduleDDG().

Here is the call graph for this function:

dataDependenceGraph()

DataDependenceGraph & BUMoveNodeSelector::dataDependenceGraph ( )

virtual

Returns DDG used internally.

Definition at line 148 of file BUMoveNodeSelector.cc.

                                        {
    return *ddg_;
}

References ddg_.

initializeReadylist()

void BUMoveNodeSelector::initializeReadylist ( )

virtual

Initializes ready list from nodes that are ready.

Add the unscheduled sink nodes of the DDG to the ready list

Definition at line 57 of file BUMoveNodeSelector.cc.

                                        {
    while (!readyList_.empty()) {
        readyList_.pop();
    }
    DataDependenceGraph::NodeSet sinks = ddg_->sinkNodes();
    for (DataDependenceGraph::NodeSet::iterator i = sinks.begin(); 
         i != sinks.end(); 
         ++i) {
        MoveNode& node = **i;
 
        // a hack to avoid adding the root operations multiple times
        // (the count of input moves): only "announce" the move to the first
        // operand (every operation should have one input operand)
        if (node.isDestinationOperation() && !node.move().destination().isFUPort()) {
            std::cerr << "termimal not fuport even though dest op!: " << node.toString();
            ddg_->writeToDotFile("not_dest_port.dot");
        }
        if (!node.isDestinationOperation())
            mightBeReady(**i);
        else if (node.move().destination().operationIndex() == 1) {
            mightBeReady(**i); 
        }
    }
}

References ddg_, TTAProgram::Move::destination(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isFUPort(), mightBeReady(), MoveNode::move(), TTAProgram::Terminal::operationIndex(), readyList_, BoostGraph< GraphNode, GraphEdge >::sinkNodes(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by BUMoveNodeSelector(), and BF2Scheduler::handleLoopDDG().

Here is the call graph for this function:

isReadyToBeScheduled() [1/3]

bool BUMoveNodeSelector::isReadyToBeScheduled ( DataDependenceGraph::NodeSet &  nodes ) const

private

Returns true in case the move is "data ready", that is, all its successors have been scheduled.

It should be noted that moves within same operation are treated specially. Additionally, as we are considering a basic block at a time, the branch operation is considered always ready before all the other moves in the basic block have been scheduled.

Parameters

node	Move to check.

Returns

True if the move is ready to be scheduled.

Definition at line 349 of file BUMoveNodeSelector.cc.

          {
 
    for (DataDependenceGraph::NodeSet::iterator i = nodes.begin(); i != nodes.end(); i++) {
        MoveNode& node = **i;
        if (!isReadyToBeScheduled(node, nodes)) {
            return false;
        }
    }
    return true;
}

Referenced by candidates(), isReadyToBeScheduled(), and mightBeReady().

isReadyToBeScheduled() [2/3]

bool BUMoveNodeSelector::isReadyToBeScheduled ( MoveNode &  mn, DataDependenceGraph::NodeSet &  nodes  ) const

private

Definition at line 362 of file BUMoveNodeSelector.cc.

          {
    if (!ddg_->hasNode(node)) {
        return true;
    }
    
    return ddg_->otherSuccessorsScheduled(node, nodes);
}

References ddg_, BoostGraph< GraphNode, GraphEdge >::hasNode(), and DataDependenceGraph::otherSuccessorsScheduled().

Here is the call graph for this function:

isReadyToBeScheduled() [3/3]

bool BUMoveNodeSelector::isReadyToBeScheduled ( MoveNodeGroup &  nodes ) const

privatevirtual

Definition at line 372 of file BUMoveNodeSelector.cc.

                                                                   {
    DataDependenceGraph::NodeSet ns;
    for (int i = 0; i < nodes.nodeCount(); i++) {
        MoveNode& mn = nodes.node(i);
        ns.insert(&mn);
    }
    return isReadyToBeScheduled(ns);
}

References isReadyToBeScheduled(), MoveNodeGroup::node(), and MoveNodeGroup::nodeCount().

Here is the call graph for this function:

mightBeReady()

void BUMoveNodeSelector::mightBeReady ( MoveNode &  node )

virtual

Adds the given move node (along with the other possible move nodes in the same operation) to the ready list in case all its children in the DDG have been scheduled.

In case the node belongs to an operation, also checks that the other result moves are also ready. In that case adds all the nodes in the said MoveOperation to the ready list in a single MoveNodeGroup.

Parameters

node	Move node that might be ready.

Implements MoveNodeSelector.

Definition at line 237 of file BUMoveNodeSelector.cc.

                                               {
 
    if (node.isScheduled()) {
        return;
    }
 
    DataDependenceGraph::NodeSet queue;
    DataDependenceGraph::NodeSet nodes;
    queue.insert(&node);
 
    while (!queue.empty()) {
        MoveNode* mn = *queue.begin();
        nodes.insert(mn);
        queue.erase(mn);
        if (mn->isSourceOperation()) {
            queueOperation(mn->sourceOperation(), nodes, queue);
        }
 
        for (unsigned int i = 0; i < mn->destinationOperationCount(); i++) {
            queueOperation(mn->destinationOperation(i), nodes, queue);
        }
 
        if (mn->move().source().isUniversalMachineRegister()) {
            if (ddg_->hasNode(*mn)) {
                MoveNode* bypassSrc =
                    ddg_->onlyRegisterRawSource(*mn);
                if (bypassSrc != NULL) {
                    if (nodes.find(bypassSrc) == nodes.end()) {
                        queue.insert(bypassSrc);
                    }
                } else {
                    std::cerr << "Warning: Cannot find source for forced bypass. "
                              << " Instruction scheduler may fail/deadlock" << std::endl;
                }
            }
        }
        if (mn->move().destination().isUniversalMachineRegister()) {
            if (ddg_->hasNode(*mn)) {
                DataDependenceGraph::NodeSet rrDestinations = 
                    ddg_->onlyRegisterRawDestinations(*mn, false, false);
                for (DataDependenceGraph::NodeSet::iterator j = 
                         rrDestinations.begin(); j != rrDestinations.end(); j++) {
                    MoveNode* n = *j;
                    if (nodes.find(n) == nodes.end()) {
                        queue.insert(n);
                    }
                }
            }
        }
    }
    
    if (!isReadyToBeScheduled(nodes)) {
        return;
    }
 
 
    if (!nodes.empty()) {
        MoveNodeGroup moves(*ddg_);
        for (DataDependenceGraph::NodeSet::iterator i = nodes.begin(); i != nodes.end(); i++) {
            if (!((**i).isScheduled())) {
                moves.addNode(**i);
            }
        }
        if (moves.nodeCount()) {
            readyList_.push(moves);
        }
    }
 
}

References MoveNodeGroup::addNode(), ddg_, TTAProgram::Move::destination(), MoveNode::destinationOperation(), MoveNode::destinationOperationCount(), BoostGraph< GraphNode, GraphEdge >::hasNode(), isReadyToBeScheduled(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), TTAProgram::Terminal::isUniversalMachineRegister(), MoveNode::move(), MoveNodeGroup::nodeCount(), DataDependenceGraph::onlyRegisterRawDestinations(), DataDependenceGraph::onlyRegisterRawSource(), queueOperation(), readyList_, TTAProgram::Move::source(), and MoveNode::sourceOperation().

Referenced by candidates(), BUBasicBlockScheduler::finalizeSchedule(), initializeReadylist(), notifyScheduled(), and BF2ScheduleFront::scheduleFrontFromMove().

Here is the call graph for this function:

notifyScheduled()

void BUMoveNodeSelector::notifyScheduled ( MoveNode &  node )

virtual

This should be called by the client as soon as a MoveNode is scheduled in order to update the internal state of the selector.

Parameters

node	The scheduled MoveNode.

Implements MoveNodeSelector.

Definition at line 209 of file BUMoveNodeSelector.cc.

                                                  {
 
    assert(node.isScheduled() && "Notifying scheduled even though it isn't.");
    DataDependenceGraph::NodeSet pred = ddg_->predecessors(node);
    for (DataDependenceGraph::NodeSet::iterator i = pred.begin(); 
         i != pred.end(); ++i) {
        MoveNode& predecessor = **i;
 
        // we schedule operations as entities, so if the predecessor is a
        // (operand) move, it's already in the ready list along with the
        // move itself
        if (!predecessor.inSameOperation(node))
            mightBeReady(**i);
    }
}

References assert, ddg_, MoveNode::inSameOperation(), MoveNode::isScheduled(), mightBeReady(), and BoostGraph< GraphNode, GraphEdge >::predecessors().

Referenced by BUBasicBlockScheduler::finalizeSchedule(), and BF2ScheduleFront::scheduleFrontFromMove().

Here is the call graph for this function:

queueOperation()

void BUMoveNodeSelector::queueOperation ( ProgramOperation &  po, const DataDependenceGraph::NodeSet &  nodes, DataDependenceGraph::NodeSet &  queue  )

static

Queues all nodes of PO into queue, if they are not already in another set.

Parameters

po	ProgramOperation whose nodes to add
nodes	nodes where the final result is. if node is here, do not add to queue
queue	quque where to add the nodes.

Definition at line 315 of file BUMoveNodeSelector.cc.

                                       {
    for (int j = 0; j < po.inputMoveCount(); j++) {
        MoveNode& inputMove = po.inputMove(j);
        // only add if not already added
        if (nodes.find(&inputMove) == nodes.end()) {
            queue.insert(&inputMove);
        }
    }
 
    for (int j = 0; j < po.outputMoveCount(); j++) {
        MoveNode& outputMove = po.outputMove(j);
        // only add if not already added
        if (nodes.find(&outputMove) == nodes.end()) {
            queue.insert(&outputMove);
        }
    }
}

References ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), ProgramOperation::outputMove(), and ProgramOperation::outputMoveCount().

Referenced by BF2ScheduleFront::allNodesOfSameOperation(), and mightBeReady().

Here is the call graph for this function:

Member Data Documentation

ddg_

DataDependenceGraph* BUMoveNodeSelector::ddg_

private

The data dependence graph built from the basic block.

Definition at line 101 of file BUMoveNodeSelector.hh.

Referenced by BUMoveNodeSelector(), candidates(), dataDependenceGraph(), initializeReadylist(), isReadyToBeScheduled(), mightBeReady(), notifyScheduled(), and ~BUMoveNodeSelector().

ddgOwned_

bool BUMoveNodeSelector::ddgOwned_

private

Definition at line 105 of file BUMoveNodeSelector.hh.

Referenced by ~BUMoveNodeSelector().

readyList_

ReadyMoveNodeGroupListBU BUMoveNodeSelector::readyList_

private

The prioritized ready list.

Definition at line 103 of file BUMoveNodeSelector.hh.

Referenced by candidates(), initializeReadylist(), and mightBeReady().

---

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

• BUMoveNodeSelector.hh
• BUMoveNodeSelector.cc