#include <CriticalPathBBMoveNodeSelector.hh>

Inheritance diagram for CriticalPathBBMoveNodeSelector:

Collaboration diagram for CriticalPathBBMoveNodeSelector:

Public Member Functions
	CriticalPathBBMoveNodeSelector (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &machine)

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

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

virtual	~CriticalPathBBMoveNodeSelector ()

virtual MoveNodeGroup	candidates ()

virtual void	notifyScheduled (MoveNode &node)

virtual DataDependenceGraph &	dataDependenceGraph ()

void	mightBeReady (MoveNode &node)

Public Member Functions inherited from MoveNodeSelector
	MoveNodeSelector ()

virtual	~MoveNodeSelector ()

Private Member Functions
bool	isReadyToBeScheduled (MoveNode &node) const

void	initializeReadylist ()
	Initializes ready list from nodes that are ready.

Private Attributes
DataDependenceGraph *	ddg_
	The data dependence graph built from the basic block.

ReadyMoveNodeGroupList	readyList_
	The prioritized ready list.

bool	ddgOwned_

Detailed Description

Selects move nodes from a basic block and prioritizes move nodes on the critical path of the data dependence graph.

Definition at line 70 of file CriticalPathBBMoveNodeSelector.hh.

Constructor & Destructor Documentation

◆ CriticalPathBBMoveNodeSelector() [1/3]

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

Constructor.

Parameters

bb	The basic block from which to select moves.

Definition at line 96 of file CriticalPathBBMoveNodeSelector.cc.

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

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

Referenced by CriticalPathBBMoveNodeSelector(), CriticalPathBBMoveNodeSelector(), and CriticalPathBBMoveNodeSelector().

Here is the call graph for this function:

◆ CriticalPathBBMoveNodeSelector() [2/3]

CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector	(	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 75 of file CriticalPathBBMoveNodeSelector.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(), CriticalPathBBMoveNodeSelector(), ddg_, initializeReadylist(), machine, Exception::setCause(), and DataDependenceGraph::setMachine().

Here is the call graph for this function:

◆ CriticalPathBBMoveNodeSelector() [3/3]

CriticalPathBBMoveNodeSelector::CriticalPathBBMoveNodeSelector	(	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 119 of file CriticalPathBBMoveNodeSelector.cc.

                                                                : 
    ddg_(&ddg), ddgOwned_(false) {
    
    ddg_->setMachine(machine);
    
#ifdef WRITE_DOT_SNAPSHOTS
    ddg_->setCycleGrouping(true);
    ddg_->writeToDotFile("ddg.dot");
#endif
 
    initializeReadylist();
}

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

Here is the call graph for this function:

◆ ~CriticalPathBBMoveNodeSelector()

CriticalPathBBMoveNodeSelector::~CriticalPathBBMoveNodeSelector ( )

virtual

Destructor.

Definition at line 136 of file CriticalPathBBMoveNodeSelector.cc.

                                                                {
    if (ddgOwned_) {
        delete ddg_;
    }
}

References ddg_, ddgOwned_, and ~CriticalPathBBMoveNodeSelector().

Referenced by ~CriticalPathBBMoveNodeSelector().

Here is the call graph for this function:

Member Function Documentation

◆ candidates()

MoveNodeGroup CriticalPathBBMoveNodeSelector::candidates ( )

virtual

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

Returns: Move node group.

Implements MoveNodeSelector.

Definition at line 148 of file CriticalPathBBMoveNodeSelector.cc.

                                           {
 
    // find a MoveNodeGroup with unscheduled MoveNodes
    while (readyList_.size() > 0) {
        MoveNodeGroup moves = readyList_.top();
        if (!moves.isAlive() || moves.isScheduled())
            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;
            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 ddg_, MoveNodeGroup::isAlive(), MoveNodeGroup::isScheduled(), mightBeReady(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), readyList_, DataDependenceGraph::scheduledNodeCount(), and DataDependenceGraph::unscheduledMoves().

Referenced by BasicBlockScheduler::handleDDG(), BasicBlockScheduler::handleLoopDDG(), and ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage().

Here is the call graph for this function:

◆ dataDependenceGraph()

DataDependenceGraph & CriticalPathBBMoveNodeSelector::dataDependenceGraph ( )

virtual

Returns the DDG used internally.

This is needed temporarily only until the MoveNodeManager is done.

Returns: The DDG.

Definition at line 191 of file CriticalPathBBMoveNodeSelector.cc.

                                                    {
    return *ddg_;
}

References ddg_.

◆ initializeReadylist()

void CriticalPathBBMoveNodeSelector::initializeReadylist ( )

private

Initializes ready list from nodes that are ready.

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

Definition at line 50 of file CriticalPathBBMoveNodeSelector.cc.

                                                    {
    DataDependenceGraph::NodeSet roots = ddg_->rootNodes();
    for (DataDependenceGraph::NodeSet::iterator i = roots.begin(); 
         i != roots.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())
            mightBeReady(**i);
        else if (node.move().destination().operationIndex() == 1) {
            mightBeReady(**i); 
        }
    }
 
}

References ddg_, TTAProgram::Move::destination(), MoveNode::isDestinationOperation(), mightBeReady(), MoveNode::move(), TTAProgram::Terminal::operationIndex(), and BoostGraph< GraphNode, GraphEdge >::rootNodes().

Referenced by CriticalPathBBMoveNodeSelector(), CriticalPathBBMoveNodeSelector(), and CriticalPathBBMoveNodeSelector().

Here is the call graph for this function:

◆ isReadyToBeScheduled()

bool CriticalPathBBMoveNodeSelector::isReadyToBeScheduled ( MoveNode & node ) const

private

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

It should be noted that moves within same operation are treated specially. Result move is considered ready even if the operands moves are not to allow scheduling all moves in the same operation as a single entity. Additionally, as we are considering a basic block at a time, the branch operation is considered never 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 324 of file CriticalPathBBMoveNodeSelector.cc.

          {
 
    // the control flow move(s) are ready only if all other moves have been
    // scheduled. In rare case of conditional branching with SPU operation set
    // branch operation can have 2 moves, condition register and destination.
    if (node.move().isControlFlowMove() && 
        ddg_->nodeCount() - ddg_->scheduledNodeCount() > 1) {
        DataDependenceGraph::NodeSet unscheduledMoves = ddg_->unscheduledMoves();
        for (DataDependenceGraph::NodeSet::iterator i = unscheduledMoves.begin(); 
            i != unscheduledMoves.end(); ++i) {
            if ((*i)->move().isControlFlowMove() == false) {
                return false;
            }
        }
    }
    return ddg_->predecessorsReady(node);
}

References ddg_, TTAProgram::Move::isControlFlowMove(), MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), DataDependenceGraph::predecessorsReady(), DataDependenceGraph::scheduledNodeCount(), and DataDependenceGraph::unscheduledMoves().

Referenced by mightBeReady().

Here is the call graph for this function:

◆ mightBeReady()

void CriticalPathBBMoveNodeSelector::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 parents in the DDG have been scheduled.

In case the node belongs to an operation, also checks that the other operand 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 235 of file CriticalPathBBMoveNodeSelector.cc.

                                                           {
 
    if (node.isScheduled()) {
        return;
    }
 
    if (!isReadyToBeScheduled(node)) 
        return;
 
    if (node.isDestinationOperation() || node.isSourceOperation()) {
        // it's a trigger, result, or operand move, let's see if all the
        // moves of the operation are ready to be scheduled
        ProgramOperation& operation = 
            (node.isDestinationOperation()?
             (node.destinationOperation()) : node.sourceOperation());
        bool allReady = true;
        MoveNodeGroup moves(*ddg_);
        for (int inputIndex = 0; inputIndex < operation.inputMoveCount();
             ++inputIndex) {
            MoveNode& m = operation.inputMove(inputIndex);
            if (&m != &node) {
                if (!isReadyToBeScheduled(m)) {
                    allReady = false;
                    break;
                } 
            } 
            if (!m.isScheduled())
                moves.addNode(m);
        }
        if (allReady) {
            // let's add also the output move(s) to the MoveNodeGroup
            for (int outputIndex = 0; 
                 outputIndex < operation.outputMoveCount();
                 ++outputIndex) {
                MoveNode& m = operation.outputMove(outputIndex);
                if (&m != &node) { 
                    if (!isReadyToBeScheduled(m)) {
                        allReady = false;
                        break;
                    }
                }
                if (!m.isScheduled())
                    moves.addNode(m);
            }
            if (allReady) {
                readyList_.push(moves);
            }
        }
    } else if ((node.isSourceVariable() || node.move().source().isRA()) &&
               (node.isDestinationVariable() || 
                node.move().destination().isRA())) {
        // it's a register to register move, we can always schedule these
        // as soon as all the dependencies are satisfied
        // handle RA -> ireg also as a register to register move
        if (isReadyToBeScheduled(node)) {
            MoveNodeGroup move(*ddg_);
            move.addNode(node);
            readyList_.push(move);
        }
    } else if (node.isSourceConstant() && node.isDestinationVariable()) {
        if (isReadyToBeScheduled(node)) {
            MoveNodeGroup move(*ddg_);
            move.addNode(node);
            readyList_.push(move);
        }
        
    } else {
        throw IllegalProgram(
            __FILE__, __LINE__, __func__,
            (boost::format("Illegal move '%s'.") % 
             POMDisassembler::disassemble(node.move())).str());
    }
}

References __func__, MoveNodeGroup::addNode(), ddg_, TTAProgram::Move::destination(), MoveNode::destinationOperation(), POMDisassembler::disassemble(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isDestinationOperation(), MoveNode::isDestinationVariable(), TTAProgram::Terminal::isRA(), isReadyToBeScheduled(), MoveNode::isScheduled(), MoveNode::isSourceConstant(), MoveNode::isSourceOperation(), MoveNode::isSourceVariable(), MoveNode::move(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), readyList_, TTAProgram::Move::source(), and MoveNode::sourceOperation().

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

Here is the call graph for this function:

◆ notifyScheduled()

void CriticalPathBBMoveNodeSelector::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 202 of file CriticalPathBBMoveNodeSelector.cc.

                                                              {
 
    assert(node.isScheduled() && "Notifying scheduled even though it isn't.");
    DataDependenceGraph::NodeSet succ = ddg_->successors(node);
    for (DataDependenceGraph::NodeSet::iterator i = succ.begin(); 
         i != succ.end(); ++i) {
        MoveNode& successor = **i;
 
        // we schedule operations as entities, so if the successor is a
        // (result) move, it's already in the ready list along with the
        // move itself
        if (!successor.inSameOperation(node))
            mightBeReady(**i);
    }
 
#ifdef WRITE_DOT_SNAPSHOTS
    ddg_->setCycleGrouping(true);
    ddg_->writeToDotFile("ddg.dot");
#endif
}