#include <SequentialScheduler.hh>

Inheritance diagram for SequentialScheduler:

Collaboration diagram for SequentialScheduler:

Public Member Functions
	SequentialScheduler (InterPassData &data)

virtual	~SequentialScheduler ()

void	handleProcedure (TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetMachine)

virtual void	handleBasicBlock (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, BasicBlockNode *bbn=NULL)

virtual std::string	shortDescription () const

virtual std::string	longDescription () const

Public Member Functions inherited from BasicBlockPass
	BasicBlockPass (InterPassData &data)

virtual	~BasicBlockPass ()

virtual void	executeDDGPass (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)

virtual bool	executeLoopPass (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)

virtual DataDependenceGraphBuilder &	ddgBuilder ()

Public Member Functions inherited from SchedulerPass
	SchedulerPass (InterPassData &data)

virtual	~SchedulerPass ()

InterPassData &	interPassData ()

Public Member Functions inherited from ControlFlowGraphPass
	ControlFlowGraphPass (InterPassData &data)

virtual	~ControlFlowGraphPass ()

virtual void	handleControlFlowGraph (ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine)

void	executeBasicBlockPass (ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine, BasicBlockPass &bbPass)

Public Member Functions inherited from ProcedurePass
	ProcedurePass (InterPassData &data)

virtual	~ProcedurePass ()

Public Member Functions inherited from ProgramPass
	ProgramPass (InterPassData &data)

virtual	~ProgramPass ()

virtual void	handleProgram (TTAProgram::Program &program, const TTAMachine::Machine &targetMachine)

Private Member Functions
int	scheduleOperation (MoveNodeGroup &moves, int earliestCycle)

int	scheduleOperandWrites (int cycle, MoveNodeGroup &moves, RegisterCopyAdder::AddedRegisterCopies &regCopies)

int	scheduleResultReads (int triggerCycle, MoveNodeGroup &moves, RegisterCopyAdder::AddedRegisterCopies &regCopies)

int	scheduleRRMove (int cycle, MoveNode &moveNode)

int	scheduleRRTempMoves (int cycle, MoveNode &regToRegMove, RegisterCopyAdder::AddedRegisterCopies &regCopies)

int	scheduleMove (int earliestCycle, MoveNode &move)

int	scheduleInputOperandTempMoves (int cycle, MoveNode &operandMove, RegisterCopyAdder::AddedRegisterCopies &regCopies)

void	unscheduleInputOperandTempMoves (MoveNode &operandMove, RegisterCopyAdder::AddedRegisterCopies &regCopies)

int	scheduleResultTempMoves (int cycle, MoveNode &resultMove, RegisterCopyAdder::AddedRegisterCopies &regCopies)

void	createBasicBlocks (TTAProgram::Procedure &cs, std::vector< TTAProgram::BasicBlock * > &basicBlocks, std::vector< int > &bbAddresses)

void	copyBasicBlocksToProcedure (TTAProgram::Procedure &cs, std::vector< TTAProgram::BasicBlock * > &basicBlocks, std::vector< int > &bbAddresses)

void	unschedule (MoveNode &moveNode)

Private Attributes
const TTAMachine::Machine *	targetMachine_
	The target machine we are scheduling the program against.

SimpleResourceManager *	rm_
	Resource Manager of the currently scheduled BB.

MoveNodeSelector *	selector_

Additional Inherited Members
Static Public Member Functions inherited from BasicBlockPass
static void	copyRMToBB (SimpleResourceManager &rm, TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, int lastCycle=-1)

Static Public Member Functions inherited from ProcedurePass
static void	copyCfgToProcedure (TTAProgram::Procedure &procedure, ControlFlowGraph &cfg)

static void	executeControlFlowGraphPass (TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetmachine, ControlFlowGraphPass &cfgp)

Static Public Member Functions inherited from ProgramPass
static void	executeProcedurePass (TTAProgram::Program &program, const TTAMachine::Machine &targetMachine, ProcedurePass &procedurePass)

Protected Member Functions inherited from BasicBlockPass
void	ddgSnapshot (DataDependenceGraph *ddg, std::string &name, DataDependenceGraph::DumpFileFormat format, bool final)

virtual DataDependenceGraph *	createDDGFromBB (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &mach)

Detailed Description

A class that implements the functionality of a basic block scheduler.

Schedules the program one basic block at a time. Does not fill delay slots if they couldn't be filled with the basic block's contents itself (no instruction importing).

Definition at line 56 of file SequentialScheduler.hh.

Constructor & Destructor Documentation

◆ SequentialScheduler()

SequentialScheduler::SequentialScheduler ( InterPassData & data )

Constructs the sequential scheduler.

Parameters

data	Interpass data

Definition at line 78 of file SequentialScheduler.cc.

                                                            :
    BasicBlockPass(data), 
    ControlFlowGraphPass(data),
    ProcedurePass(data),
    ProgramPass(data), 
    rm_(NULL) {
}

◆ ~SequentialScheduler()

SequentialScheduler::~SequentialScheduler ( )

virtual

Destructor.

Definition at line 89 of file SequentialScheduler.cc.

89 {

90}

Member Function Documentation

◆ copyBasicBlocksToProcedure()

void SequentialScheduler::copyBasicBlocksToProcedure	(	TTAProgram::Procedure &	cs,
		std::vector< TTAProgram::BasicBlock * > &	basicBlocks,
		std::vector< int > &	bbAddresses
	)

private

Definition at line 701 of file SequentialScheduler.cc.

                                 {
    TTAProgram::InstructionReferenceManager& irm =
        proc.parent().instructionReferenceManager();
 
    for (unsigned int i = 0; i < basicBlocks.size(); i++) {
        TTAProgram::BasicBlock& bb = *basicBlocks.at(i);
        TTAProgram::Instruction& bbIns = bb.instructionAtIndex(0);
        TTAProgram::Instruction& oldProcIns = proc.instructionAt(
            bbAddresses[i]);
        if (irm.hasReference(oldProcIns)) {
            irm.replace(oldProcIns, bbIns);
        }
    }
 
    proc.clear();
    for (unsigned int i = 0; i < basicBlocks.size(); i++) {
        TTAProgram::BasicBlock& bb = *basicBlocks.at(i);
 
        // first one is a special case. can contain ref which need to
        // be update
        TTAProgram::Instruction& ins = bb.firstInstruction();
        TTAProgram::Instruction* insCopy = ins.copy();
        proc.CodeSnippet::add(insCopy); // delay address fix
 
        if (irm.hasReference(ins)) {
            irm.replace(ins, *insCopy);
        }
 
        for (int j = 1; j < bb.instructionCount(); j++) {
            TTAProgram::Instruction& ins = bb.instructionAtIndex(j);
            TTAProgram::Instruction* insCopy = ins.copy();
            proc.CodeSnippet::add(insCopy); // delay address fix
        }
    }
 
    // update inst addresses
    if (proc.isInProgram()) {
        if (!(&proc == &proc.parent().lastProcedure())) {
            proc.parent().moveProcedure(
                proc.parent().nextProcedure(proc),
                proc.instructionCount());
        }
    }
}

References TTAProgram::Procedure::clear(), TTAProgram::Instruction::copy(), TTAProgram::CodeSnippet::firstInstruction(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::CodeSnippet::instructionAt(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Program::instructionReferenceManager(), TTAProgram::CodeSnippet::isInProgram(), TTAProgram::Program::lastProcedure(), TTAProgram::Program::moveProcedure(), TTAProgram::Program::nextProcedure(), TTAProgram::CodeSnippet::parent(), and TTAProgram::InstructionReferenceManager::replace().

Referenced by handleProcedure().

Here is the call graph for this function:

◆ createBasicBlocks()

void SequentialScheduler::createBasicBlocks	(	TTAProgram::Procedure &	proc,
		std::vector< TTAProgram::BasicBlock * > &	basicBlocks,
		std::vector< int > &	bbAddresses
	)

private

Splits a procedure into basic blocks.

Definition at line 648 of file SequentialScheduler.cc.

                                 {
    TTAProgram::InstructionReferenceManager& irm =
        proc.parent().instructionReferenceManager();
    TTAProgram::BasicBlock* currentBB = NULL;
    int lastStartAddress = 0;
    // loop thru all instructions in the given BB.
    for (int i = 0; i < proc.instructionCount(); i++) {
        TTAProgram::Instruction& ins = proc.instructionAtIndex(i);
        TTAProgram::Instruction* insCopy = ins.copy();
 
        // if has references, starts a new BB, from this instruction.
        if (irm.hasReference(ins)) {
            if (currentBB != NULL) {
                // only add non-empty BBs.
                if (currentBB->instructionCount() != 0) {
                    basicBlocks.push_back(currentBB);
                    bbAddresses.push_back(lastStartAddress);
                } else {
                    delete currentBB;
                }
            }
            lastStartAddress = ins.address().location();
            currentBB = new TTAProgram::BasicBlock(lastStartAddress);
            // update instruction references.
//            irm.replace(ins, *insCopy);
        }
        assert(currentBB != NULL); // first ins of proc should have a ref.
        currentBB->add(insCopy);
 
        // jump or call starts a new BB, after this instruction.
        if (ins.hasControlFlowMove()) {
            basicBlocks.push_back(currentBB);
            bbAddresses.push_back(lastStartAddress);
            lastStartAddress = ins.address().location() + 1;
            currentBB = new TTAProgram::BasicBlock(lastStartAddress);
        }
    }
 
    if (currentBB != nullptr) {
        // at end, add last BB if non-empty
        if (currentBB->instructionCount() != 0) {
            basicBlocks.push_back(currentBB);
            bbAddresses.push_back(lastStartAddress);
        } else {
            delete currentBB;
        }
    }
}

References TTAProgram::CodeSnippet::add(), TTAProgram::Instruction::address(), assert, TTAProgram::Instruction::copy(), TTAProgram::Instruction::hasControlFlowMove(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Program::instructionReferenceManager(), TTAProgram::Address::location(), and TTAProgram::CodeSnippet::parent().

Referenced by handleProcedure().

Here is the call graph for this function:

◆ handleBasicBlock()

void SequentialScheduler::handleBasicBlock	(	TTAProgram::BasicBlock &	bb,
		const TTAMachine::Machine &	targetMachine,
		TTAProgram::InstructionReferenceManager &	irm,
		BasicBlockNode *	bbn = `NULL`
	)

virtual

Schedules a single basic block.

Parameters

bb	The basic block to schedule.
targetMachine	The target machine.

Exceptions

Exception several TCE exceptions can be thrown in case of a scheduling error.

Reimplemented from BasicBlockPass.

Definition at line 101 of file SequentialScheduler.cc.

                                                                 {
    if (bb.instructionCount() == 0)
        return;
 
    targetMachine_ = &targetMachine;
    rm_ = SimpleResourceManager::createRM(targetMachine);
 
    int cycle = 0;
 
    SequentialMoveNodeSelector selector(bb);
    selector_ = &selector;
 
    // loop as long as selector gives things to schedule
    MoveNodeGroup moves = selector.candidates();
    while (moves.nodeCount() > 0) {
 
        MoveNode& firstMove = moves.node(0);
        if (firstMove.isOperationMove()) {
            cycle = scheduleOperation(moves, cycle) + 1;
        } else {
            if (firstMove.move().destination().isRA()) {
                cycle = scheduleMove(cycle, firstMove) + 1;
            } else {
                cycle = scheduleRRMove(cycle, firstMove) + 1;
            }
        }
 
        if (!moves.isScheduled()) {
            std::string message = " Move(s) did not get scheduled: ";
            for (int i = 0; i < moves.nodeCount(); i++) {
                message += moves.node(i).toString() + " ";
            }
            throw ModuleRunTimeError(__FILE__, __LINE__, __func__, message);
        }
 
        for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
            MoveNode& moveNode = moves.node(moveIndex);
            selector.notifyScheduled(moveNode);
        }
        moves = selector.candidates();
    }
    copyRMToBB(*rm_, bb, targetMachine, irm);
    SimpleResourceManager::disposeRM(rm_); rm_ = NULL;
}

References __func__, SequentialMoveNodeSelector::candidates(), BasicBlockPass::copyRMToBB(), SimpleResourceManager::createRM(), TTAProgram::Move::destination(), SimpleResourceManager::disposeRM(), TTAProgram::CodeSnippet::instructionCount(), MoveNode::isOperationMove(), TTAProgram::Terminal::isRA(), MoveNodeGroup::isScheduled(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), SequentialMoveNodeSelector::notifyScheduled(), rm_, scheduleMove(), scheduleOperation(), scheduleRRMove(), selector_, targetMachine_, and MoveNode::toString().

Referenced by handleProcedure().

Here is the call graph for this function:

◆ handleProcedure()

void SequentialScheduler::handleProcedure	(	TTAProgram::Procedure &	procedure,
		const TTAMachine::Machine &	targetMachine
	)

virtual

Schedules a procedure.

The original procedure is modified during scheduling.

Parameters

procedure	The procedure to schedule.
targetMachine	The target machine.

Exceptions

Exception In case of an error during scheduling. The exception type can be any subtype of Exception.

Reimplemented from ProcedurePass.

Definition at line 599 of file SequentialScheduler.cc.

                                            {
    std::vector<TTAProgram::BasicBlock*> basicBlocks;
    std::vector<int> bbAddresses;
    createBasicBlocks(procedure, basicBlocks, bbAddresses);
 
    for (unsigned int i = 0; i < basicBlocks.size();i++) {
        handleBasicBlock(
            *basicBlocks[i], targetMachine,
            procedure.parent().instructionReferenceManager());
    }
 
    copyBasicBlocksToProcedure(procedure, basicBlocks, bbAddresses);
 
    // delete the basic blocks.
    for (unsigned int i = 0; i < basicBlocks.size();i++) {
        delete basicBlocks[i];
    }
}

References copyBasicBlocksToProcedure(), createBasicBlocks(), handleBasicBlock(), TTAProgram::Program::instructionReferenceManager(), and TTAProgram::CodeSnippet::parent().

Here is the call graph for this function:

◆ longDescription()

std::string SequentialScheduler::longDescription ( ) const

virtual

Optional longer description of the pass.

This description can include usage instructions, details of choice of algorithmic details, etc.

Returns: The description as a string.

Reimplemented from SchedulerPass.

Definition at line 640 of file SequentialScheduler.cc.

                                           {
    return "Sequential Instruction scheduler";
}

◆ scheduleInputOperandTempMoves()

int SequentialScheduler::scheduleInputOperandTempMoves	(	int	cycle,
		MoveNode &	operandMove,
		RegisterCopyAdder::AddedRegisterCopies &	regCopies
	)

private

Schedules the (possible) temporary register copy moves (due to missing connectivity) preceeding the given input move.

Parameters

operandMove	The move of which temp moves to schedule.
regCopies	Temp register copy moves associated with operandMove

Returns: cycle next available cycle

Definition at line 479 of file SequentialScheduler.cc.

                                                     {
    if (regCopies.count_ > 0) {
        if (MapTools::containsKey(regCopies.operandCopies_,&operandMove)) {
            DataDependenceGraph::NodeSet tempMoves = 
        regCopies.operandCopies_[&operandMove]; 
            //in the tempMoves nodeset, the first move is the original one;
            //in case of input operand temp moves, it must be scheduled first
            DataDependenceGraph::NodeSet::iterator i = tempMoves.begin();
            cycle = scheduleMove(cycle, **i) + 1;
            //then all the other moves follows;
            //they must be scheduled in reverse order
            i = tempMoves.end();
            --i;
            while(i != tempMoves.begin()){
                cycle = scheduleMove(cycle, **i) + 1;
                --i;
            }
        }
    }
    return cycle;
}

References MapTools::containsKey(), RegisterCopyAdder::AddedRegisterCopies::count_, RegisterCopyAdder::AddedRegisterCopies::operandCopies_, and scheduleMove().

Referenced by scheduleOperandWrites().

Here is the call graph for this function:

◆ scheduleMove()

int SequentialScheduler::scheduleMove	(	int	earliestCycle,
		MoveNode &	moveNode
	)

private

Schedules a single move to the earliest possible cycle, taking in account the resource constraints, and latencies in producing source values.

This method assumes the move is possible to schedule with regards to connectivity and resources. Short immediates are converted to long immediates when needed.

Parameters

move	The move to schedule.
earliestCycle	The earliest cycle to try.

Returns: cycle where the move got scheduled.

Definition at line 342 of file SequentialScheduler.cc.

                                                                       {
    if (moveNode.isScheduled()) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            (boost::format("Move '%s' is already scheduled!")
            % moveNode.toString()).str());
    }
 
    // if it's a conditional move then we have to be sure that the guard
    // is defined before executing the move
    if (!moveNode.move().isUnconditional()) {
        int guardLatency =
            targetMachine_->controlUnit()->globalGuardLatency();
 
        const TTAMachine::Guard& guard = moveNode.move().guard().guard();
        const TTAMachine::RegisterGuard* rg =
            dynamic_cast<const TTAMachine::RegisterGuard*>(&guard);
        if (rg != NULL) {
            guardLatency += rg->registerFile()->guardLatency();
        }
        earliestCycle += std::max(0, guardLatency - 1);
    }
 
    // RM hasConnection takes MoveNodeSet, however is called only for one
    // moveNode here.
    MoveNodeSet tempSet;
    tempSet.addMoveNode(moveNode);
    if (moveNode.isSourceConstant() &&
        !moveNode.move().hasAnnotations(
            TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM)) {
 
        // If source is constant and node does not have annotation already,
        // we add it if constant can not be transported so IU broker and
        // OutputPSocket brokers will add Immediate
        // Example : 999999 -> integer0.2
        if (!rm_->canTransportImmediate(moveNode)){
            TTAProgram::ProgramAnnotation annotation(
                TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM);
            moveNode.move().setAnnotation(annotation);
 
        } else if (!moveNode.isDestinationOperation() &&
                   rm_->earliestCycle(rm_->largestCycle()+1,moveNode) == -1) {
            // If source is constant and node does not have annotation
            // already, we add it if node has no connection, so IU broker and
            // OutputPSocket brokers will add Immediate
            // Example: 27 -> integer0.2
            // With bus capable of transporting 27 as short immediate but
            // no connection from that bus to integer0 unit
            TTAProgram::ProgramAnnotation annotation(
                TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM);
            moveNode.move().setAnnotation(annotation);
        }
    }
    // annotate the return move otherwise it might get undetected in the
    // simulator after the short to long immediate conversion and thus
    // stopping simulation automatically might not work
    if (moveNode.isSourceConstant() &&
        moveNode.move().isReturn() &&
        !rm_->canTransportImmediate(moveNode)) {
        TTAProgram::ProgramAnnotation annotation(
            TTAProgram::ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN);
        moveNode.move().setAnnotation(annotation);
    }
 
    earliestCycle = rm_->earliestCycle(earliestCycle, moveNode);
    if (earliestCycle == -1 || earliestCycle == INT_MAX) {
        if (moveNode.isSourceConstant() &&
            !moveNode.isDestinationOperation() &&
            moveNode.move().hasAnnotations(
                TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM)) {
            // If earliest cycle returns -1 and source is constant
            // and moveNode needs long immediate
            // there is most likely missing long immediate unit
            std::string msg = "Assignment of MoveNode " + moveNode.toString();
            msg += " failed! Most likely missing Long Immediate Unit";
            msg += " or Instruction Template!";
            throw IllegalMachine(
                __FILE__, __LINE__, __func__, msg);
        }
        std::string msg = "Assignment of MoveNode " + moveNode.toString();
        msg += " failed!";
            throw ModuleRunTimeError(
                __FILE__, __LINE__, __func__, msg);
    }
    rm_->assign(earliestCycle,  moveNode);
    if (!moveNode.isScheduled()) {
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__,
            (boost::format("Assignment of MoveNode '%s' failed!")
            % moveNode.toString()).str());
    }
    return earliestCycle;
}

References __func__, MoveNodeSet::addMoveNode(), TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM, TTAProgram::ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN, SimpleResourceManager::assign(), SimpleResourceManager::canTransportImmediate(), TTAMachine::Machine::controlUnit(), SimpleResourceManager::earliestCycle(), TTAMachine::ControlUnit::globalGuardLatency(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), TTAMachine::RegisterFile::guardLatency(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), MoveNode::isDestinationOperation(), TTAProgram::Move::isReturn(), MoveNode::isScheduled(), MoveNode::isSourceConstant(), TTAProgram::Move::isUnconditional(), SimpleResourceManager::largestCycle(), MoveNode::move(), TTAMachine::RegisterGuard::registerFile(), rm_, TTAProgram::AnnotatedInstructionElement::setAnnotation(), targetMachine_, and MoveNode::toString().

Referenced by handleBasicBlock(), scheduleInputOperandTempMoves(), scheduleOperandWrites(), scheduleResultReads(), scheduleResultTempMoves(), scheduleRRMove(), and scheduleRRTempMoves().

Here is the call graph for this function:

◆ scheduleOperandWrites()

int SequentialScheduler::scheduleOperandWrites	(	int	cycle,
		MoveNodeGroup &	moves,
		RegisterCopyAdder::AddedRegisterCopies &	regCopies
	)

private

Schedules operand moves of an operation execution.

Assumes the given MoveNodeGroup contains all moves in the operation execution. Also assumes that all inputs to the MoveNodeGroup have been scheduled. Exception to this are the possible temporary register copies inserted before the operand move due to missing connectivity. If found, the temp moves are scheduled atomically with the operand move. Assumes top-down scheduling.

Parameters

cycle	Earliest cycle for starting scheduling of operands
moves	Moves of the operation execution.

Returns: The cycle the trigger got scheduled

Definition at line 223 of file SequentialScheduler.cc.

                                                     {
    // Counts operands that are not scheduled at beginning.
    int scheduledMoves = 0;
    MoveNode* trigger = NULL;
    MoveNode& firstNode = moves.node(0);
    ProgramOperation& po = firstNode.destinationOperation();
 
    for (int i = 0; i < moves.nodeCount(); i++) {
 
        MoveNode& node = moves.node(i);
        // result read?
        if (!node.isDestinationOperation()) {
            continue;
        }
 
        cycle = scheduleInputOperandTempMoves(cycle, node, regCopies);
        scheduleMove(cycle, node);
        scheduledMoves++;
 
        TTAProgram::Terminal& dest = node.move().destination();
        // got trigger?
        if (dest.isFUPort() && dest.isTriggering()) {
 
            // if all operands not scheduled, delay trigger
            if (scheduledMoves < po.inputMoveCount()) {
                unscheduleInputOperandTempMoves(node, regCopies);
                trigger = &node;
                unschedule(node);
                scheduledMoves--;
                continue;
            }
        }
        cycle = node.cycle() + 1;
    }
    // trigger scheduling delayed, schedule at end
    if (trigger != NULL && !trigger->isScheduled()) {
        assert(scheduledMoves == po.inputMoveCount()-1);
        cycle = scheduleInputOperandTempMoves(cycle, *trigger, regCopies);
        return scheduleMove(cycle, *trigger);
    }
    return cycle - 1;
}

References assert, MoveNode::cycle(), TTAProgram::Move::destination(), MoveNode::destinationOperation(), ProgramOperation::inputMoveCount(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isFUPort(), MoveNode::isScheduled(), TTAProgram::Terminal::isTriggering(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), scheduleInputOperandTempMoves(), scheduleMove(), unschedule(), and unscheduleInputOperandTempMoves().

Referenced by scheduleOperation().

Here is the call graph for this function:

◆ scheduleOperation()

int SequentialScheduler::scheduleOperation	(	MoveNodeGroup &	moves,
		int	earliestCycle
	)

private

Schedules moves in a single operation execution.

Assumes the given MoveNodeGroup contains all moves in the operation execution. Also assumes that all inputs to the MoveNodeGroup have been scheduled.

Parameters

moves Moves of the operation execution.

Returns: returns the last cycle of the operation.

Definition at line 163 of file SequentialScheduler.cc.

                                             {
    ProgramOperation& po =
        (moves.node(0).isSourceOperation())?
        (moves.node(0).sourceOperation()):
        (moves.node(0).destinationOperation());
 
    RegisterCopyAdder regCopyAdder(
        BasicBlockPass::interPassData(), *rm_, *selector_);
 
 
    // TODO: registercopyader and ddg..
    RegisterCopyAdder::AddedRegisterCopies addedCopies =
        regCopyAdder.addMinimumRegisterCopies(po, *targetMachine_, NULL);
 
#ifdef DEBUG_REG_COPY_ADDER
    const int tempsAdded = addedCopies.count_;
#endif
 
    MoveNodeSet tempSet;
    for (int i = 0; i < moves.nodeCount(); i++) {
        // MoveNodeGroup relates to DDG so we copy it to more
        // simple MoveNodeSet container
        tempSet.addMoveNode(moves.node(i));
    }
 
    int triggerCycle  = scheduleOperandWrites(
        earliestCycle, moves, addedCopies);
    if (triggerCycle == -1) {
        throw ModuleRunTimeError(
            __FILE__,__LINE__,__func__,
            "Scheduling operands failed for: " +moves.toString());
    }
 
    int lastCycle = scheduleResultReads(triggerCycle+1, moves, addedCopies);
 
    if (lastCycle == -1) {
        throw ModuleRunTimeError(
            __FILE__,__LINE__,__func__,
            "Scheduling results failed for: " +moves.toString());
    }
    return lastCycle;
}

References __func__, RegisterCopyAdder::addMinimumRegisterCopies(), MoveNodeSet::addMoveNode(), RegisterCopyAdder::AddedRegisterCopies::count_, MoveNode::destinationOperation(), SchedulerPass::interPassData(), MoveNode::isSourceOperation(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), rm_, scheduleOperandWrites(), scheduleResultReads(), selector_, MoveNode::sourceOperation(), targetMachine_, and MoveNodeGroup::toString().

Referenced by handleBasicBlock().

Here is the call graph for this function:

◆ scheduleResultReads()

int SequentialScheduler::scheduleResultReads	(	int	cycle,
		MoveNodeGroup &	moves,
		RegisterCopyAdder::AddedRegisterCopies &	regCopies
	)

private

Schedules the result read moves of an operation execution.

Assumes the given MoveNodeGroup contains all moves in the operation execution. Also assumes that all operand moves have been scheduled.

Parameters

moves Moves of the operation execution.

Returns: cycle of last operand read, or -1 if fails

Definition at line 278 of file SequentialScheduler.cc.

                                                     {
    for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
        MoveNode& node = moves.node(moveIndex);
 
        if (!node.isScheduled()) {
            if (!node.isSourceOperation()) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    (boost::format("Move to schedule '%s' is not "
                    "result move!") % node.toString()).str());
            }
 
            cycle = std::max(cycle, node.earliestResultReadCycle());
            cycle = scheduleMove(cycle, node);
            cycle = scheduleResultTempMoves(cycle, node, regCopies);
 
            if (!node.isScheduled()) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    (boost::format("Move '%s' did not get scheduled!")
                    % node.toString()).str());
            }
        }
    }
    return cycle;
}

References __func__, MoveNode::earliestResultReadCycle(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), scheduleMove(), scheduleResultTempMoves(), and MoveNode::toString().

Referenced by scheduleOperation().

Here is the call graph for this function:

◆ scheduleResultTempMoves()

int SequentialScheduler::scheduleResultTempMoves	(	int	cycle,
		MoveNode &	resultMove,
		RegisterCopyAdder::AddedRegisterCopies &	regCopies
	)

private

Schedules the (possible) temporary register copy moves (due to missing connectivity) succeeding the given result move.

Parameters

operandMove	The move of which temp moves to schedule.
cycle	of the last actual result move

Returns: cycle cycle of last scheduled temp move

Definition at line 537 of file SequentialScheduler.cc.

                                                     {
    if (regCopies.count_ > 0) {
        if (MapTools::containsKey(regCopies.resultCopies_,&resultMove)) {
            DataDependenceGraph::NodeSet tempMoves = 
        regCopies.resultCopies_[&resultMove];
            //in the tempMoves nodeset, the first move is the original one,
            //in case of result temp moves it must be scheduled at the end;
            //all the temp moves must be scheduled in reverse order            
            DataDependenceGraph::NodeSet::iterator i = tempMoves.end();
            while (i != tempMoves.begin()) {
                --i;
                cycle = scheduleMove(cycle + 1, **i);
            }
        }
    }
    return cycle;
}

References MapTools::containsKey(), RegisterCopyAdder::AddedRegisterCopies::count_, RegisterCopyAdder::AddedRegisterCopies::resultCopies_, and scheduleMove().

Referenced by scheduleResultReads().

Here is the call graph for this function:

◆ scheduleRRMove()

int SequentialScheduler::scheduleRRMove	(	int	cycle,
		MoveNode &	moveNode
	)

private

Schedules a RR move and its temp compies.

Parameters

cycle	The earliest cycle to try.
moveNode	R-R Move to schedule.

Returns: Last cycle where the moves got scheduled.

Definition at line 315 of file SequentialScheduler.cc.

                                                                 {
    RegisterCopyAdder regCopyAdder(
        BasicBlockPass::interPassData(), *rm_, *selector_);
 
    RegisterCopyAdder::AddedRegisterCopies addedCopies =
      regCopyAdder.addRegisterCopiesToRRMove(moveNode, NULL);
 
    cycle = scheduleMove(cycle, moveNode) + 1;
    cycle = scheduleRRTempMoves(cycle, moveNode, addedCopies); 
 
    return cycle - 1;
}

References RegisterCopyAdder::addRegisterCopiesToRRMove(), SchedulerPass::interPassData(), rm_, scheduleMove(), scheduleRRTempMoves(), and selector_.

Referenced by handleBasicBlock().

Here is the call graph for this function:

◆ scheduleRRTempMoves()

int SequentialScheduler::scheduleRRTempMoves	(	int	cycle,
		MoveNode &	regToRegMove,
		RegisterCopyAdder::AddedRegisterCopies &	regCopies
	)

private

Schedules the (possible) temporary register copy moves (due to missing connectivity) succeeding the given RR move.

The function recursively goes through all the temporary moves added to the given RR move.

Parameters

cycle	Earliest cycle for starting scheduling
regToRegMove	A temp move whose successor has to be scheduled.
lastUse	Recursive function parameter, it should be set as 0 for the first function call.

Returns: cycle next available cycle

Definition at line 450 of file SequentialScheduler.cc.

                                                     {
    if (regCopies.count_ > 0) {
        if (MapTools::containsKey(regCopies.operandCopies_,&regToRegMove)) {
            DataDependenceGraph::NodeSet tempMoves = 
                regCopies.operandCopies_[&regToRegMove];
            //in the tempMoves nodeset, the first move is the original one,
            //in case of RR temp moves it must be scheduled at the end;
            //all the temp moves must be scheduled in reverse order            
            DataDependenceGraph::NodeSet::iterator i = tempMoves.end();
            while(i != tempMoves.begin()){
                --i;
                cycle = scheduleMove(cycle, **i) + 1;
            }
        }
    }
    return cycle;
}

References MapTools::containsKey(), RegisterCopyAdder::AddedRegisterCopies::count_, RegisterCopyAdder::AddedRegisterCopies::operandCopies_, and scheduleMove().

Referenced by scheduleRRMove().

Here is the call graph for this function:

◆ shortDescription()

std::string SequentialScheduler::shortDescription ( ) const

virtual

A short description of the pass, usually the optimization name, such as "basic block scheduler".

Returns: The description as a string.

Implements SchedulerPass.

Definition at line 627 of file SequentialScheduler.cc.

                                            {
    return "Sequential Instruction scheduler";
}

◆ unschedule()

void SequentialScheduler::unschedule ( MoveNode & moveNode )

private

Unschedules the given move.

Also restores a possible short immediate source in case it was converted to a long immediate register read during scheduling.

Parameters

moveNode Move to unschedule.

Definition at line 566 of file SequentialScheduler.cc.

                                                  {
    if (!moveNode.isScheduled()) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            (boost::format("Trying to unschedule move '%s' which "
            "is not scheduled!") % moveNode.toString()).str());
    }
    rm_->unassign(moveNode);
    if (moveNode.move().hasAnnotations(
        TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM)) {
        // If we added annotation during scheduleMove delete it
        moveNode.move().removeAnnotations(
        TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM);
    }
    if (moveNode.isScheduled() || moveNode.isPlaced()) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            (boost::format("Unscheduling of move '%s' failed!")
            % moveNode.toString()).str());
    }
}

References __func__, TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM, TTAProgram::AnnotatedInstructionElement::hasAnnotations(), MoveNode::isPlaced(), MoveNode::isScheduled(), MoveNode::move(), TTAProgram::AnnotatedInstructionElement::removeAnnotations(), rm_, MoveNode::toString(), and SimpleResourceManager::unassign().

Referenced by scheduleOperandWrites(), and unscheduleInputOperandTempMoves().

Here is the call graph for this function:

◆ unscheduleInputOperandTempMoves()

void SequentialScheduler::unscheduleInputOperandTempMoves	(	MoveNode &	operandMove,
		RegisterCopyAdder::AddedRegisterCopies &	regCopies
	)

private

Unschedules the (possible) temporary register copy moves (due to missing connectivity) preceeding the given input move.

Parameters

operandMove	Move to unschedule.
regCopies	Temp register copy moves associated with operandMove

Definition at line 511 of file SequentialScheduler.cc.

                                                                            {
    
    if (regCopies.count_ > 0) {
        if (MapTools::containsKey(regCopies.operandCopies_,&operandMove)) {
            DataDependenceGraph::NodeSet tempMoves = 
        regCopies.operandCopies_[&operandMove];
            for (DataDependenceGraph::NodeSet::iterator i = tempMoves.begin();
                 i != tempMoves.end(); ++i) {
                unschedule(**i);
            }
        }
    }
}

References MapTools::containsKey(), RegisterCopyAdder::AddedRegisterCopies::count_, RegisterCopyAdder::AddedRegisterCopies::operandCopies_, and unschedule().

Referenced by scheduleOperandWrites().

Here is the call graph for this function:

Member Data Documentation

◆ rm_

SimpleResourceManager* SequentialScheduler::rm_

private

Resource Manager of the currently scheduled BB.

Definition at line 124 of file SequentialScheduler.hh.

Referenced by handleBasicBlock(), scheduleMove(), scheduleOperation(), scheduleRRMove(), and unschedule().

◆ selector_

MoveNodeSelector* SequentialScheduler::selector_

private

Definition at line 126 of file SequentialScheduler.hh.

Referenced by handleBasicBlock(), scheduleOperation(), and scheduleRRMove().

◆ targetMachine_

const TTAMachine::Machine* SequentialScheduler::targetMachine_

private

The target machine we are scheduling the program against.

Definition at line 122 of file SequentialScheduler.hh.

Referenced by handleBasicBlock(), scheduleMove(), and scheduleOperation().

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

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SequentialScheduler()

◆ ~SequentialScheduler()

Member Function Documentation

◆ copyBasicBlocksToProcedure()

◆ createBasicBlocks()

◆ handleBasicBlock()

◆ handleProcedure()

◆ longDescription()

◆ scheduleInputOperandTempMoves()

◆ scheduleMove()

◆ scheduleOperandWrites()

◆ scheduleOperation()

◆ scheduleResultReads()

◆ scheduleResultTempMoves()

◆ scheduleRRMove()

◆ scheduleRRTempMoves()

◆ shortDescription()

◆ unschedule()

◆ unscheduleInputOperandTempMoves()

Member Data Documentation

◆ rm_

◆ selector_

◆ targetMachine_