BasicBlockScheduler Class Reference

#include <BasicBlockScheduler.hh>

Inheritance diagram for BasicBlockScheduler:

Collaboration diagram for BasicBlockScheduler:

Public Member Functions
	BasicBlockScheduler (InterPassData &data, SoftwareBypasser *bypasser=NULL, RegisterRenamer *renamer=NULL)
virtual	~BasicBlockScheduler ()
virtual int	handleDDG (DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine, int minCycle=0, bool testOnly=false) override
virtual int	handleLoopDDG (DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine, int tripCount, SimpleResourceManager *prologRM, bool testOnly=false) override
virtual std::string	shortDescription () const
virtual std::string	longDescription () const
virtual void	printStats () const
virtual DataDependenceGraphBuilder &	ddgBuilder ()
Public Member Functions inherited from DDGPass
	DDGPass (InterPassData &data)
virtual	~DDGPass ()
Public Member Functions inherited from SchedulerPass
	SchedulerPass (InterPassData &data)
virtual	~SchedulerPass ()
InterPassData &	interPassData ()
Public Member Functions inherited from BasicBlockPass
	BasicBlockPass (InterPassData &data)
virtual	~BasicBlockPass ()
virtual void	handleBasicBlock (TTAProgram::BasicBlock &basicBlock, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, BasicBlockNode *bbn=NULL)
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)

Static Public Member Functions
static MoveNode *	findTrigger (const ProgramOperation &po, const TTAMachine::Machine &mach)
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)

Protected Member Functions
void	scheduleRRMove (MoveNode &moveNode)
void	scheduleOperation (MoveNodeGroup &moves)
int	scheduleOperandWrites (int &cycle, MoveNodeGroup &moves)
bool	scheduleResultReads (MoveNodeGroup &moves)
void	scheduleMove (MoveNode &move, int earliestCycle, bool allowPredicationAndRenaming)
void	scheduleRRTempMoves (MoveNode &regToRegMove, MoveNode &firstMove, int lastUse)
void	scheduleInputOperandTempMoves (MoveNode &operandMove, MoveNode &operandWrite)
void	unschedule (MoveNode &moveNode)
void	unscheduleAllNodes ()
void	unscheduleInputOperandTempMoves (MoveNode &operandMove)
void	scheduleResultReadTempMoves (MoveNode &resultMove, MoveNode &resultRead, int lastUse)
void	unscheduleResultReadTempMoves (MoveNode &resultMove)
void	notifyScheduled (MoveNodeGroup &moves, MoveNodeSelector &selector)
void	ddgSnapshot (DataDependenceGraph &ddg, const std::string &name, DataDependenceGraph::DumpFileFormat format, bool final, bool resetCounter=false) const
MoveNode *	succeedingTempMove (MoveNode &current)
int	getTriggerOperand (const Operation &operation, const TTAMachine::Machine &machine)
bool	tryToSwitchInputs (ProgramOperation &op)
void	handleRemovedResultMoves (std::set< std::pair< TTAProgram::Move *, int > > removedMoves)
bool	tryToOptimizeWaw (const MoveNode &moveNode)
void	tryToDelayOperands (MoveNodeGroup &moves)
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)

Static Protected Member Functions
static MoveNode *	findTriggerFromUnit (const ProgramOperation &po, const TTAMachine::Unit &unit)

Protected Attributes
const TTAMachine::Machine *	targetMachine_
	The target machine we are scheduling the program against.
DataDependenceGraph *	ddg_
	DDG of the currently scheduled BB.
SimpleResourceManager *	rm_
	Resource Manager of the currently scheduled BB.
std::map< const MoveNode *, DataDependenceGraph::NodeSet >	scheduledTempMoves_
	Stores the MoveNodes that were scheduled as temp moves during scheduling of the operand move.
SoftwareBypasser *	softwareBypasser_
	The software bypasser to use to bypass registers when possible.
RegisterRenamer *	renamer_
int	minCycle_
	The earliest cycle to schedule moves in. Used to leave room for sched_yield() by the sched_yield() emitter.
MoveNodeSelector *	selector_
int	bypassedCount_
int	deadResults_
LLVMTCECmdLineOptions *	options_
MoveNode *	jumpNode_
int	tripCount_

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 63 of file BasicBlockScheduler.hh.

Constructor & Destructor Documentation

BasicBlockScheduler()

BasicBlockScheduler::BasicBlockScheduler	(	InterPassData &	data,
		SoftwareBypasser *	bypasser = NULL,
		RegisterRenamer *	renamer = NULL
	)

Constructs the basic block scheduler.

Parameters

data	Interpass data
bypasser	Helper module implementing software bypassing
delaySlotFiller	Helper module implementing jump delay slot filling

Definition at line 83 of file BasicBlockScheduler.cc.

                                                          :
    DDGPass(data), BasicBlockPass(data), ddg_(NULL), rm_(NULL),
    softwareBypasser_(bypasser), renamer_(renamer), minCycle_(0), 
    jumpNode_(NULL) {
    CmdLineOptions *cmdLineOptions = Application::cmdLineOptions();
    options_ = dynamic_cast<LLVMTCECmdLineOptions*>(cmdLineOptions);
}

References Application::cmdLineOptions(), and options_.

Here is the call graph for this function:

~BasicBlockScheduler()

BasicBlockScheduler::~BasicBlockScheduler ( )

virtual

Definition at line 93 of file BasicBlockScheduler.cc.

                                          {
}

Member Function Documentation

ddgBuilder()

virtual DataDependenceGraphBuilder & BasicBlockPass::ddgBuilder ( )

inlinevirtual

Reimplemented from BasicBlockPass.

Reimplemented in BUBasicBlockScheduler.

Definition at line 86 of file BasicBlockPass.hh.

{ return ddgBuilder_; }

ddgSnapshot()

void BasicBlockScheduler::ddgSnapshot ( DataDependenceGraph &  ddg, const std::string &  name, DataDependenceGraph::DumpFileFormat  format, bool  final, bool  resetCounter = false  ) const

protected

Prints DDG to a dot file before and after scheudling

Parameters

ddg	to print
name	operation name for ddg
final	specify if ddg is after scheduling
resetCounter
format	format of the file

Returns

number of cycles/instructions copied.

Definition at line 1629 of file BasicBlockScheduler.cc.

                                 {
 
    static int bbCounter = 0;
 
    if (resetCounter) {
        bbCounter = 0;
    }
 
    if (final) {
        if (format == DataDependenceGraph::DUMP_DOT) {
            ddg.writeToDotFile(
                (boost::format("bb_%s_%s_after_scheduling.dot") % 
                 ddg_->name() % name).str());
        } else {
            ddg.writeToXMLFile(
                (boost::format("bb_%s_%s_after_scheduling.xml") %
                 ddg_->name() % name).str());
        }
        
    } else {
        if (format == DataDependenceGraph::DUMP_DOT) {
            ddg.writeToDotFile(
                (boost::format("bb_%s_%d_%s_before_scheduling.dot")
                 % ddg.name() % bbCounter % name).str());
            DataDependenceGraph* criticalPath = ddg.criticalPathGraph();
            criticalPath->writeToDotFile(
                (boost::format(
                    "bb_%s_%d_%s_before_scheduling_critical_path.dot")
                 % ddg.name() % bbCounter % name).str());
            delete criticalPath;
        } else {
            ddg.writeToXMLFile(
                (boost::format("bb_%s_%d_%s_before_scheduling.xml")
                 % ddg.name() % bbCounter % name).str());
        }
    }
    ++bbCounter;
}

References DataDependenceGraph::criticalPathGraph(), ddg_, DataDependenceGraph::DUMP_DOT, BoostGraph< GraphNode, GraphEdge >::name(), GraphBase< GraphNode, GraphEdge >::writeToDotFile(), and DataDependenceGraph::writeToXMLFile().

Referenced by BUBasicBlockScheduler::handleDDG(), handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), and scheduleOperation().

Here is the call graph for this function:

findTrigger()

MoveNode * BasicBlockScheduler::findTrigger ( const ProgramOperation &  po, const TTAMachine::Machine &  mach  )

static

Definition at line 2090 of file BasicBlockScheduler.cc.

                                                               {
 
    MoveNode* triggerFromPO = po.triggeringMove();
    if (triggerFromPO) {
        return triggerFromPO;
    }
 
    // no scheduled moves. getting harder.
    
    TTAMachine::Machine::FunctionUnitNavigator nav = 
    mach.functionUnitNavigator();
    MoveNode* candidate = NULL;
    for (int i = 0; i < nav.count(); i++) {
        TTAMachine::FunctionUnit* fu = nav.item(i);
        if (fu->hasOperation(po.operation().name())) {
            if (candidate == NULL) {
                candidate = findTriggerFromUnit(po, *fu);
            } else {
                // make sure two different FU's don't have different
                // trigger ports.
                if (findTriggerFromUnit(po, *fu) != candidate) {
                    return NULL;
                }
            }
        }
    }
    
    if (mach.controlUnit()->hasOperation(po.operation().name())) {
        return findTriggerFromUnit(po, *mach.controlUnit());
    }
    return candidate;
    
}

References TTAMachine::Machine::controlUnit(), TTAMachine::Machine::Navigator< ComponentType >::count(), findTriggerFromUnit(), TTAMachine::Machine::functionUnitNavigator(), TTAMachine::FunctionUnit::hasOperation(), TTAMachine::Machine::Navigator< ComponentType >::item(), Operation::name(), ProgramOperation::operation(), and ProgramOperation::triggeringMove().

Referenced by BFOptimization::getSisterTrigger(), BF2Scheduler::mustBeTrigger(), and BUBasicBlockScheduler::scheduleOperandWrites().

Here is the call graph for this function:

findTriggerFromUnit()

MoveNode * BasicBlockScheduler::findTriggerFromUnit ( const ProgramOperation &  po, const TTAMachine::Unit &  unit  )

staticprotected

Definition at line 2126 of file BasicBlockScheduler.cc.

                                                            {
    const TTAMachine::FunctionUnit* fu =
    dynamic_cast<const TTAMachine::FunctionUnit*>(&unit);
    int ioIndex = -1;
 
    int portC = fu->portCount();
    for (int i = 0; i < portC; i++) {
        auto p = fu->port(i);
        const TTAMachine::FUPort* port = dynamic_cast<const TTAMachine::FUPort*>(p);
        if (port != nullptr && port->isTriggering()) {
            const TTAMachine::HWOperation* hwop =
            fu->operation(po.operation().name());
            ioIndex = hwop->io(*port);
            return &po.inputNode(ioIndex).at(0);
        }
    }
    return NULL;
}

References MoveNodeSet::at(), ProgramOperation::inputNode(), TTAMachine::HWOperation::io(), TTAMachine::FUPort::isTriggering(), Operation::name(), ProgramOperation::operation(), TTAMachine::FunctionUnit::operation(), TTAMachine::FunctionUnit::port(), and TTAMachine::Unit::portCount().

Referenced by findTrigger().

Here is the call graph for this function:

getTriggerOperand()

int BasicBlockScheduler::getTriggerOperand ( const Operation &  operation, const TTAMachine::Machine &  machine  )

protected

Returns the operand which is triggering in all FU's which support the operation. If operation not found, is not gcu or multiple FU's have different triggers, returns 0

Definition at line 1680 of file BasicBlockScheduler.cc.

                                      {
 
    const TCEString& opName = operation.name();
    TTAMachine::Machine::FunctionUnitNavigator fuNav = 
        machine.functionUnitNavigator();
 
    int trigger = 0;
    for (int i = 0; i < fuNav.count(); i++) {
        TTAMachine::FunctionUnit& fu = *fuNav.item(i);
        if (fu.hasOperation(opName)) {
            TTAMachine::HWOperation& hwop = *fu.operation(opName);
            for (int j = 1; j <= operation.numberOfInputs(); j++) {
                TTAMachine::FUPort& port = *hwop.port(j);
                if (port.isTriggering()) {
                    if (trigger == 0) {
                        trigger = j;
                    } else {
                        if (trigger != j) {
                            return 0;
                        }
                    }
                }
            }
        }
    }
    return trigger;
}

References TTAMachine::Machine::Navigator< ComponentType >::count(), TTAMachine::Machine::functionUnitNavigator(), TTAMachine::FunctionUnit::hasOperation(), TTAMachine::FUPort::isTriggering(), TTAMachine::Machine::Navigator< ComponentType >::item(), machine, Operation::name(), Operation::numberOfInputs(), TTAMachine::FunctionUnit::operation(), and TTAMachine::HWOperation::port().

Referenced by tryToSwitchInputs(), and BUBasicBlockScheduler::tryToSwitchInputs().

Here is the call graph for this function:

handleDDG()

int BasicBlockScheduler::handleDDG ( DataDependenceGraph &  ddg, SimpleResourceManager &  rm, const TTAMachine::Machine &  targetMachine, int  minCycle = 0, bool  test = false  )

overridevirtual

Schedules a piece of code in a DDG

Parameters

ddg	The ddg containing the code
rm	Resource manager that is to be used.
targetMachine	The target machine.

Returns

size of the produces schedule.

Exceptions

Exception

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

Reimplemented from DDGPass.

Reimplemented in BUBasicBlockScheduler.

Definition at line 107 of file BasicBlockScheduler.cc.

                                                                     {
    tripCount_ = 0;
    ddg_ = &ddg;
    targetMachine_ = &targetMachine;
    minCycle_ = minCycle;
 
    if (renamer_ != NULL) {
        renamer_->initialize(ddg);
    }
 
    if (options_ != NULL && options_->dumpDDGsDot()) {
        ddgSnapshot(
            ddg, std::string("0"), DataDependenceGraph::DUMP_DOT, false);
    }
 
    if (options_ != NULL && options_->dumpDDGsXML()) {
        ddgSnapshot(
            ddg, std::string("0"), DataDependenceGraph::DUMP_XML, false);
    }
 
    scheduledTempMoves_.clear();
 
    // empty DDGs can be ignored
    if (ddg.nodeCount() == 0 ||
        (ddg.nodeCount() == 1 && !ddg.node(0).isMove())) {
        return 0;
    }
 
    CriticalPathBBMoveNodeSelector selector(ddg, targetMachine);
    selector_ = &selector;
 
    rm_ = &rm;
 
 
    // register selector to bypasser for notfications.
    if (softwareBypasser_ != NULL) {
        softwareBypasser_->setSelector(&selector);
    }
 
    if (renamer_ != NULL) {
        renamer_->setSelector(&selector);
    }
 
    MoveNodeGroup moves = selector.candidates();
    while (moves.nodeCount() > 0) {
        bool movesRemoved = false;
        MoveNode& firstMove = moves.node(0);
        if (firstMove.isOperationMove()) {
            scheduleOperation(moves);
        } else {
            if (firstMove.move().destination().isRA()) {
                scheduleMove(firstMove,0, true);
            } else {
                scheduleRRMove(firstMove);
                int lastOperandFake = 0;
                if (softwareBypasser_ != NULL) {
                    int rv = 
                        softwareBypasser_->bypassNode(
                            firstMove, lastOperandFake, ddg, rm);
                    if (rv < 0) {
                        softwareBypasser_->removeBypass(
                            firstMove, ddg, rm, true);
                        scheduleRRMove(firstMove);
                    } 
                    
                    // did the bypass cause a reg-to-itself copy?
                    // if it did, let's kill it.
                    if (firstMove.move().source().equals(
                            firstMove.move().destination())) {
                        movesRemoved = true;
                    }
                    
                    if (rv > 0) {
                        std::set<std::pair<TTAProgram::Move*, int> >
                            removedMoves;                        
                        softwareBypasser_->removeDeadResults(
                            moves, ddg, rm, removedMoves);
                        // TODO: disabled becaused may be problematic
                        // when rescheduled to different buses
//                    handleRemovedResultMoves(removedMoves);
                    }
                }
            }
        }
 
        if (!movesRemoved) {
            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() + " ";
                }
                
                unscheduleAllNodes();
                
                throw ModuleRunTimeError(__FILE__,__LINE__,__func__,message);
            }
 
            // notifies successors of the scheduled moves.
            notifyScheduled(moves, selector);
        }
 
        moves = selector.candidates();
    }
    int size = rm.largestCycle();    
    if (test) {
        unscheduleAllNodes();
        return size;
    }
    if (softwareBypasser_ != NULL) {
        softwareBypasser_->clearCaches(ddg, true);
    }
 
    if (ddg.nodeCount() !=
        ddg.scheduledNodeCount()) {
        ddg.writeToDotFile("failed_bb.dot");
        std::cerr << ddg.nodeCount() <<  ", " << ddg.scheduledNodeCount()
        << std::endl;
        throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
            "All moves in the DDG didn't get scheduled.");
    }
 
    if (options_ != NULL && options_->dumpDDGsDot()) {
        ddgSnapshot(ddg, std::string("0"), DataDependenceGraph::DUMP_DOT, true);
    }
    
    if (options_ != NULL && options_->dumpDDGsXML()) {
        ddgSnapshot(ddg, std::string("0"), DataDependenceGraph::DUMP_XML, true);
    }
    return size;
}

References __func__, SoftwareBypasser::bypassNode(), CriticalPathBBMoveNodeSelector::candidates(), SoftwareBypasser::clearCaches(), ddg_, ddgSnapshot(), TTAProgram::Move::destination(), DataDependenceGraph::DUMP_DOT, DataDependenceGraph::DUMP_XML, LLVMTCECmdLineOptions::dumpDDGsDot(), LLVMTCECmdLineOptions::dumpDDGsXML(), TTAProgram::Terminal::equals(), RegisterRenamer::initialize(), MoveNode::isMove(), MoveNode::isOperationMove(), TTAProgram::Terminal::isRA(), MoveNodeGroup::isScheduled(), SimpleResourceManager::largestCycle(), minCycle_, MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::node(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), notifyScheduled(), options_, SoftwareBypasser::removeBypass(), SoftwareBypasser::removeDeadResults(), renamer_, rm_, DataDependenceGraph::scheduledNodeCount(), scheduledTempMoves_, scheduleMove(), scheduleOperation(), scheduleRRMove(), selector_, RegisterRenamer::setSelector(), SoftwareBypasser::setSelector(), softwareBypasser_, TTAProgram::Move::source(), targetMachine_, MoveNode::toString(), tripCount_, unscheduleAllNodes(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

handleLoopDDG()

int BasicBlockScheduler::handleLoopDDG ( DataDependenceGraph &  ddg, SimpleResourceManager &  rm, const TTAMachine::Machine &  targetMachine, int  tripCount, SimpleResourceManager *  prologRM, bool  testOnly = false  )

overridevirtual

Schedules loop in a DDG

Parameters

ddg	The ddg containing the loop
rm	Resource manager that is to be used.
targetMachine	The target machine.

Exceptions

Exception

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

Returns

negative if failed, else overlapcount.

Reimplemented from DDGPass.

Reimplemented in BUBasicBlockScheduler.

Definition at line 251 of file BasicBlockScheduler.cc.

                                           {
    tripCount_ = tripCount;
    ddg_ = &ddg;
    targetMachine_ = &targetMachine;
    minCycle_ = 0;
 
    if (renamer_ != NULL) {
        renamer_->initialize(ddg);
    }
 
    if (options_ != NULL && options_->dumpDDGsDot()) {
        ddgSnapshot(
            ddg, std::string("0"), DataDependenceGraph::DUMP_DOT, false, true);
    }
 
    if (options_ != NULL && options_->dumpDDGsXML()) {
        ddgSnapshot(
            ddg, std::string("0"), DataDependenceGraph::DUMP_XML, false, true);
    }
 
    scheduledTempMoves_.clear();
 
    // empty DDGs can be ignored
    if (ddg.nodeCount() == 0 ||
        (ddg.nodeCount() == 1 && !ddg.node(0).isMove())) {
        return 0;
    }
 
    CriticalPathBBMoveNodeSelector selector(ddg, targetMachine);
 
    rm_ = &rm;
 
    // register selector to bypasser for notfications.
    if (softwareBypasser_ != NULL) {
        softwareBypasser_->setSelector(&selector);
    }
 
    if (renamer_ != NULL) {
        renamer_->setSelector(&selector);
    }
    
    for (int i = ddg.nodeCount()-1; i>= 0 ; i--) {
        MoveNode& node = ddg.node(i);
        if (node.move().isControlFlowMove()) {
            jumpNode_ = &node;
            MoveNodeGroup mng;
            mng.addNode(node);
            scheduleOperation(mng);
        }
    }
 
    MoveNodeGroup moves = selector.candidates();
    while (moves.nodeCount() > 0) {
 
        MoveNode& firstMove = moves.node(0);
        if (firstMove.isOperationMove()) {
            scheduleOperation(moves);
        } else {
            if (firstMove.move().destination().isRA()) {
                scheduleMove(firstMove,0, true);
            } else {
                scheduleRRMove(firstMove);
            }
        }
 
        if (!moves.isScheduled()) {
            ddg_->writeToDotFile(
                std::string("ii_") + 
                Conversion::toString(rm.initiationInterval()) + 
                std::string("_dag.dot"));
 
            unscheduleAllNodes();
 
            return -1;
        }
 
        // notifies successors of the scheduled moves.
        notifyScheduled(moves, selector);
 
        moves = selector.candidates();
    }
    
    if (ddg.nodeCount() !=
        ddg.scheduledNodeCount()) {
        debugLog("All moves in the DDG didn't get scheduled.");
//        debugLog("Disassembly of the situation:");
//        Application::logStream() << bb.disassemble() << std::endl;
        ddg.writeToDotFile("failed_bb.dot");
        abortWithError("Should not happen!");
    }
 
    // loop schedulign did not help.
    if (static_cast<unsigned>(ddg.largestCycle()) < rm.initiationInterval()
        || testOnly) {
        if (static_cast<unsigned>(ddg.largestCycle()) < 
            rm.initiationInterval()) {
            Application::logStream() 
                << "No overlapping instructions." 
                << "Should Revert to ordinary scheduler."
                << std::endl;
        } 
        // this have to be calculated before unscheduling.
        int rv = ddg.largestCycle() / rm.initiationInterval();
        unscheduleAllNodes();
        return rv;
    }
 
    // test that ext-cond jump not in prolog (where it is skipped)
    int overlap_count = ddg.largestCycle() / rm.initiationInterval();
    if (overlap_count >= tripCount) {
        unscheduleAllNodes();
        return -1;
    }
    
    if (softwareBypasser_ != NULL) {
        softwareBypasser_->clearCaches(ddg, true);
    }
 
    if (options_ != NULL && options_->dumpDDGsDot()) {
        ddgSnapshot(ddg, std::string("0"), DataDependenceGraph::DUMP_DOT, true);
    }
 
    if (options_ != NULL && options_->dumpDDGsXML()) {
        ddgSnapshot(ddg, std::string("0"), DataDependenceGraph::DUMP_XML, true);
    }
 
    return ddg.largestCycle() / rm.initiationInterval();
}

References abortWithError, MoveNodeGroup::addNode(), CriticalPathBBMoveNodeSelector::candidates(), SoftwareBypasser::clearCaches(), ddg_, ddgSnapshot(), debugLog, TTAProgram::Move::destination(), DataDependenceGraph::DUMP_DOT, DataDependenceGraph::DUMP_XML, LLVMTCECmdLineOptions::dumpDDGsDot(), LLVMTCECmdLineOptions::dumpDDGsXML(), RegisterRenamer::initialize(), SimpleResourceManager::initiationInterval(), TTAProgram::Move::isControlFlowMove(), MoveNode::isMove(), MoveNode::isOperationMove(), TTAProgram::Terminal::isRA(), MoveNodeGroup::isScheduled(), jumpNode_, DataDependenceGraph::largestCycle(), Application::logStream(), minCycle_, MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::node(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), notifyScheduled(), options_, renamer_, rm_, DataDependenceGraph::scheduledNodeCount(), scheduledTempMoves_, scheduleMove(), scheduleOperation(), scheduleRRMove(), RegisterRenamer::setSelector(), SoftwareBypasser::setSelector(), softwareBypasser_, targetMachine_, Conversion::toString(), tripCount_, unscheduleAllNodes(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

handleRemovedResultMoves()

void BasicBlockScheduler::handleRemovedResultMoves ( std::set< std::pair< TTAProgram::Move *, int > >  removedMoves )

protected

Checks if the result moves that were removed might remove some resource bottleneck of already scheduled moves.

This situation happens at least when a result move used the last RF write port for a cycle and limited the earliest cycle of a previously scheduled move. Thus, after the last use of that result was scheduled and bypassed, the RF write port is freed as the result move becomes unnecessary, thus the move that was scheduled before could be scheduled earlier. Same thing can happen for bus (move slot) contrained moves and also moves that were restricted by a WaR edge due to the result move, etc.

Todo:

: reschedule also the moves dependent from the rescheduled ones that got earlier

Definition at line 1803 of file BasicBlockScheduler.cc.

                                                         {
 
    if (removedMoves.size() == 0)
        return;
 
#ifndef RESCHEDULE_NEXT_CYCLE_AFTER_DRE
    return;
#endif
 
    const bool DEBUG_PRINT = false; //Application::verboseLevel() > 0;
 
    if (DEBUG_PRINT) {
        Application::logStream()
            << removedMoves.size() << " dead results eliminated: " 
            << std::endl;
    }
 
    for (std::set<std::pair<TTAProgram::Move*, int> >::
             const_iterator i = removedMoves.begin(); 
         i != removedMoves.end(); ++i) {
 
        TTAProgram::Move& eliminatedMove = *(*i).first;
        int cycle = (*i).second;
 
        if (DEBUG_PRINT) {
            Application::logStream()
                << eliminatedMove.toString() << " (cycle " << cycle << ") ";
        }
 
        int oldCycle = cycle + 1;
        // look for already scheduled moves that were scheduled after 
        // the cycle of the result move, thus potentially were limited by 
        // the result move earlier
        DataDependenceGraph::NodeSet nextCycleMoves = 
            ddg_->movesAtCycle(oldCycle);
 
        // if true, try to reschedule all moves at the next cycle (slower,
        // but handles the case when the cycle was bus constrained previously),
        // if false, tries to schedule only potentially RF write port
        // constrained moves (faster)
        bool rescheduleAllSucceedingMoves = false;
        for (DataDependenceGraph::NodeSet::const_iterator m = 
                 nextCycleMoves.begin(); m != nextCycleMoves.end(); ++m) {
            MoveNode& moveNode = **m;
 
            if (rescheduleAllSucceedingMoves ||
                (moveNode.move().destination().isGPR() &&
                 &eliminatedMove.destination().registerFile() ==
                 &moveNode.move().destination().registerFile())) {
 
                if (DEBUG_PRINT) {
                    Application::logStream() 
                        << "Trying to reschedule "
                        << moveNode.toString() << " " << std::endl;
                }
 
                assert(moveNode.isScheduled() && moveNode.cycle() == oldCycle);
 
                unschedule(moveNode);
                // because a pontially removed WaR, we might be able to
                // schedule this move (write to the same reg) even earlier
                // than the dead result move cycle
                scheduleMove(moveNode, std::max(oldCycle - 10, 0), false);
 
                if (!moveNode.isScheduled()) {
                    for (int c = 4; c >= 0; --c) {
                        Application::logStream()
                            << "\t\t" << oldCycle - c << ": " 
                            << rm_->instruction(
                                std::max(oldCycle - c, 0))->toString() 
                            << std::endl;
                    }
                    assert(moveNode.isScheduled());
                }
 
                if (moveNode.cycle() < oldCycle) {
                    if (DEBUG_PRINT) {
                        Application::logStream() 
                            << " OK at cycle " << moveNode.cycle() << ". " << std::endl;
                    }
                } else {
                    // should not get worse schedule!
                    assert(moveNode.cycle() == oldCycle);
                    if (DEBUG_PRINT) {
                        Application::logStream() << " NO change. " << std::endl;
                    }
                }
                
            }
            /// @todo: reschedule also the moves dependent from the 
            /// rescheduled ones that got earlier
        }
 
        if (DEBUG_PRINT) {
            Application::logStream() << std::endl;
        }
    }
}

References assert, MoveNode::cycle(), ddg_, TTAProgram::Move::destination(), SimpleResourceManager::instruction(), TTAProgram::Terminal::isGPR(), MoveNode::isScheduled(), Application::logStream(), MoveNode::move(), DataDependenceGraph::movesAtCycle(), TTAProgram::Terminal::registerFile(), rm_, scheduleMove(), TTAProgram::Instruction::toString(), TTAProgram::Move::toString(), MoveNode::toString(), and unschedule().

Referenced by scheduleOperation().

Here is the call graph for this function:

longDescription()

std::string BasicBlockScheduler::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.

Reimplemented in BUBasicBlockScheduler.

Definition at line 1583 of file BasicBlockScheduler.cc.

                                           {
    return
        "Basic block scheduler that uses the longest path information of "
        "data dependency graph to prioritize the ready list. Assumes that "
        "the input has registers allocated and no connectivity missing.";
}

notifyScheduled()

void BasicBlockScheduler::notifyScheduled ( MoveNodeGroup &  moves, MoveNodeSelector &  selector  )

protected

Notifies to the selector that given nodes and their temp reg copies are scheduled .

Parameters

nodes	nodes which are scheduled.
selector	selector which to notify.

Definition at line 1598 of file BasicBlockScheduler.cc.

                                                      {
    
    for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
        MoveNode& moveNode = moves.node(moveIndex);
        selector.notifyScheduled(moveNode);
        std::map<const MoveNode*, DataDependenceGraph::NodeSet>::
            iterator tmIter = scheduledTempMoves_.find(&moveNode);
        if (tmIter != scheduledTempMoves_.end()) {
            DataDependenceGraph::NodeSet& tempMoves = tmIter->second;
            for (DataDependenceGraph::NodeSet::iterator i = 
                     tempMoves.begin(); i != tempMoves.end(); i++) {
                if ((**i).isScheduled()) {
                    selector.notifyScheduled(**i);
                }
            }
        }
    }
}

References MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), MoveNodeSelector::notifyScheduled(), and scheduledTempMoves_.

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

Here is the call graph for this function:

printStats()

void BasicBlockScheduler::printStats ( ) const

virtual

Definition at line 1904 of file BasicBlockScheduler.cc.

                                      {
    if (Application::verboseLevel() > 0) {
    }
}

References Application::verboseLevel().

Here is the call graph for this function:

scheduleInputOperandTempMoves()

void BasicBlockScheduler::scheduleInputOperandTempMoves ( MoveNode &  operandMove, MoveNode &  operandWrite  )

protected

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

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

Parameters

operandMove	A temp move whose predecessor has to be scheduled.
operandWrite	The original move of which temp moves to schedule.

Definition at line 1340 of file BasicBlockScheduler.cc.

                                                   {
    /* Because temporary register moves do not have WaR dependency edges
       between the other possible uses of the same temp register in
       the same operation, we have to limit the scheduling of the new
       temp reg move to the last use of the same temp register so
       we don't overwrite the temp registers of other operands. */
 
    /* <pekka> TODO: this could be improved by allowing to schedule also
     *before* the previous use, in the "holes" where it's unused. Now in effect
     the copies serialize the code quite badly. */
    int lastUse = 0;
    
    // find all unscheduled preceeding temp moves of the operand move
    DataDependenceGraph::EdgeSet inEdges = ddg_->inEdges(operandMove);
    MoveNode* tempMove = NULL;
    for (DataDependenceGraph::EdgeSet::iterator i = inEdges.begin();
         i != inEdges.end(); ++i) {
        if ((**i).edgeReason() != DataDependenceEdge::EDGE_REGISTER ||
            (**i).guardUse() ||
            (**i).dependenceType() != DataDependenceEdge::DEP_RAW) {
            continue;
        }
 
        MoveNode& m = ddg_->tailNode(**i);
        if (m.isScheduled() ||
            !m.move().hasAnnotations(
                TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE)) {
            continue;
        }
 
        assert(tempMove == NULL &&
               "Multiple unscheduled moves for the operand move, should have "
               "max. one (the temporary move)!");
        tempMove = &m;
        MoveNode* lastRead =
            ddg_->lastScheduledRegisterRead(
                tempMove->move().destination().registerFile(),
                tempMove->move().destination().index());
        if (lastRead != NULL)
            lastUse = lastRead->cycle();
    }
 
    if (tempMove == NULL)
        return; // no temp moves found
 
    // the temp move should have maximum of one unscheduled
    // preceeding reg to reg copy (in case of an additional temp reg copy),
    // schedule it first if found, calling recursively this function
    scheduleInputOperandTempMoves(*tempMove, operandWrite);
    
    // TODO: is the true correct here?
    scheduleMove(*tempMove, lastUse, true);
    assert(tempMove->isScheduled());
    scheduledTempMoves_[&operandWrite].insert(tempMove);
}

References TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE, assert, MoveNode::cycle(), ddg_, DataDependenceEdge::DEP_RAW, TTAProgram::Move::destination(), DataDependenceEdge::EDGE_REGISTER, TTAProgram::AnnotatedInstructionElement::hasAnnotations(), TTAProgram::Terminal::index(), BoostGraph< GraphNode, GraphEdge >::inEdges(), MoveNode::isScheduled(), DataDependenceGraph::lastScheduledRegisterRead(), MoveNode::move(), TTAProgram::Terminal::registerFile(), scheduledTempMoves_, scheduleInputOperandTempMoves(), scheduleMove(), and BoostGraph< GraphNode, GraphEdge >::tailNode().

Referenced by scheduleInputOperandTempMoves(), and scheduleOperandWrites().

Here is the call graph for this function:

scheduleMove()

void BasicBlockScheduler::scheduleMove ( MoveNode &  moveNode, int  earliestCycle, bool  allowPredicationAndRenaming  )

protected

Schedules a single move to the earliest possible cycle, taking in account the DDG, 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.
allowPredicationAndRenaming	Whether allowed to remove guard from the move being scheduled. Checks again side-effects are still made, this can be done only to operand moves and triggers without mem write or side-effects.

Definition at line 946 of file BasicBlockScheduler.cc.

                                                                             {
    if (moveNode.isScheduled()) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            (boost::format("Move '%s' is already scheduled!")
            % moveNode.toString()).str());
    }
 
    int sourceReadyCycle = 0;
    if (moveNode.isSourceOperation()) {
        sourceReadyCycle = moveNode.earliestResultReadCycle();
    }
 
    int ddgCycle = 0;
 
    unsigned int ii = rm_->initiationInterval();
 
    // schedule jumps and calls...
    if (moveNode.move().isControlFlowMove()) {
 
        // the branch should get scheduled last, so the DDG should have
        // only the branch move(s) at hand unscheduled. For software
         // pipelining (ii > 0), branches might be scheduled earlier.
        if (ii == 0 && ddg_->nodeCount() != ddg_->scheduledNodeCount() + 1) {    
        // in rare case the branch moves can have 2 parameters (SPU)
        // and therefore 2 nodes unscheduled. Check if the unscheduled
        // moves are all control flow moves.
            DataDependenceGraph::NodeSet unscheduledMoves =
                ddg_->unscheduledMoves();     
            for (DataDependenceGraph::NodeSet::iterator i = unscheduledMoves.begin(); 
                i != unscheduledMoves.end(); ++i) { 
                if (!(*i)->move().isControlFlowMove()) {
                    TCEString msg =
                        "Control Flow Move is not last of the unscheduled moves! ";
                    msg += "Scheduled count=" + 
                        Conversion::toString(ddg_->scheduledNodeCount());
                    msg += " Node count=" +
                        Conversion::toString(ddg_->nodeCount());          
                    throw InvalidData(__FILE__, __LINE__, __func__, msg);            
                }
            }
        }
 
        // try to fill the delay slots with moves within the same basic
        // block
        // @TODO: ignore argument/rv register deps in case of call as they
        // are not really used by the call instruction but by the called
        // procedure, thus we can schedule them at the delay slots
 
        // largest cycle of DDG is the highest cycle where something
        // was scheduled, however such a move can have pipeline
        // that spans more cycles and we should not change
        // the control flow while something is still in pipeline
        int largest = std::max(rm_->largestCycle(), ddg_->largestCycle());
        if (ii == 0) {
            ddgCycle =
                std::max(
                    ddg_->earliestCycle(moveNode),
                    largest - targetMachine_->controlUnit()->delaySlots());
        } else {
            unsigned int delaySlots = 
                targetMachine_->controlUnit()->delaySlots();
            // is the jump in first or later iteration?
        MoveNode* jumpLimit = ddg_->findLoopLimitAndIndex(moveNode).first;
 
            ddgCycle = (((ddg_->earliestCycle(moveNode, ii) + 
                          delaySlots) / ii) + 1)*ii  - 1 - delaySlots;
            if ((unsigned)ddgCycle >= ii - delaySlots) {
                
                int jumpOverlapCount = (ddgCycle + delaySlots) / ii;
                if (jumpLimit == NULL) {
                    // allow jump only in first iteration if we could
                    // not find the limit
                    return;
                } else {
                    // update loop limit counter.
                    TTAProgram::TerminalImmediate& ti = dynamic_cast<
            TTAProgram::TerminalImmediate&>(jumpLimit->move().source());
                    int jumpLimitValue = ti.value().unsignedValue();
                    int loopCounterStep = 1;
                    if (jumpLimitValue != tripCount_) {
                        if (jumpLimitValue == 2 * tripCount_) {
                            loopCounterStep = 2;
                        } else {
                            if (jumpLimitValue == 4 * tripCount_) {
                                loopCounterStep = 4;
                            } else {
                                // don't know how much to decr. counter.
                                return;
                            }
                        }
                    }
                        
                    if (tripCount_ > jumpOverlapCount) {
            jumpLimit->move().setSource(
                            new TTAProgram::TerminalImmediate(
                                SimValue(
                                    jumpLimitValue - 
                                    (jumpOverlapCount * loopCounterStep), 
                                    ti.value().width())));
                    } else {
                        // loop limit is too short. 
                        // would be always executed too many times.
                        return;
                    }
                }
            }
        }
    } else { // not a control flow move:
        ddgCycle = ddg_->earliestCycle(moveNode, ii);
 
        // <pekka> This is now always called even though renaming is disabled?
        int minRenamedEC = std::max(
            sourceReadyCycle, ddg_->earliestCycle(moveNode, ii, true, true));
        
        // rename if can and may alow scheuduling earlier.
        if (renamer_ != NULL && minRenamedEC < ddgCycle && 
            allowPredicationAndRenaming) {
            minRenamedEC =  rm_->earliestCycle(minRenamedEC, moveNode);
            if (minRenamedEC < ddgCycle) {
                
                if (renamer_->renameDestinationRegister(
                        moveNode, ii != 0, true, true, minRenamedEC)) {
                    ddgCycle = ddg_->earliestCycle(moveNode, ii);
                } else {
#ifdef THIS_IS_BUGGY_WITH_REGCOPY_ADDER                    
                    // renaming already scheduled ones may fail if
                    // loop scheudling.
                    if (rm_->initiationInterval() == 0) {
                        MoveNode *limitingAdep =
                            ddg_->findLimitingAntidependenceSource(moveNode);
                        if (limitingAdep != NULL) {
                            // don't try to rename is same operation.
                            // as it would not help at all.
                            if (!moveNode.isSourceOperation() ||
                                !limitingAdep->isDestinationOperation() ||
                                &moveNode.sourceOperation() !=
                                &limitingAdep->destinationOperation()) {
                                if (renamer_->renameSourceRegister(
                                        *limitingAdep, false, true, true)) {
                                    ddgCycle = ddg_->earliestCycle(
                                        moveNode);
                                }
                            }
                        }
                    }
#endif
                }
            }
        }
    }
 
    // if it's a conditional move then we have to be sure that the guard
    // is defined before executing the move.
    // this is already handled by DDGs earliestCycle, except cases
    // where the guard is defined in a previous BB. 
    // So this prevents scheduling unconditional moves at the beginning
    // of a BB.
    
    if (!moveNode.move().isUnconditional()) {
        ddgCycle = std::max(ddgCycle, moveNode.guardLatency()-1);
 
        if (allowPredicationAndRenaming) {
            // try to get rid of the guard if it gives earlier earliestcycle.
            if (ddg_->earliestCycle(moveNode, ii, false, false, true) 
                < ddgCycle) {
                bool guardNeeded = false;
                if (moveNode.move().destination().isGPR() || 
                    moveNode.move().isControlFlowMove()) {
                    guardNeeded = true;
                } else {
                    // this would be needed only for trigger,
                    // but trigger may change during scheduling.
                    // so lets just limit all operands, it seems 
                    // this does not make the schedule any worse.
                    if (moveNode.isDestinationOperation()) {
                        const Operation& o = 
                            moveNode.destinationOperation().operation();
                        if (o.writesMemory() || o.hasSideEffects() ||
                            o.affectsCount() != 0) {
                            guardNeeded = true;
                        }
                    }
                }
                if (!guardNeeded) {
                    moveNode.move().setGuard(NULL);
                    ddg_->removeIncomingGuardEdges(moveNode);
                    ddgCycle = ddg_->earliestCycle(moveNode, ii);
                    assert(moveNode.move().isUnconditional());
                }
            }
            
            if (ii == 0 && tryToOptimizeWaw(moveNode)) {
                ddgCycle = std::max(ddg_->earliestCycle(moveNode, ii),
                                    moveNode.guardLatency()-1);
            }
 
        }
    }
 
    // Earliest cycle from which to start, could depend on result ready
    // for result moves.
    int minCycle = std::max(std::max(earliestCycle, ddgCycle), minCycle_);
    minCycle = std::max(minCycle, sourceReadyCycle);    
 
    // 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
                   && rm_->initiationInterval() == 0) {
 
            // 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
            // this may mess up modulo scheduling.
            // TODO: do this more cleanly, this is a kludge.
            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);
    }
 
    minCycle = rm_->earliestCycle(minCycle, moveNode);
    if (minCycle == -1 || minCycle == 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!";
            if (rm_->initiationInterval() == 0) {
                ddg_->writeToDotFile("illegalmach.dot");
                throw IllegalMachine(
                    __FILE__, __LINE__, __func__, msg);
            } else {
                ddg_->writeToDotFile(
                    std::string("ii_") + 
                    Conversion::toString(rm_->initiationInterval()) + 
                    std::string("_dag.dot"));
 
                unscheduleAllNodes();
                throw ModuleRunTimeError(
                    __FILE__, __LINE__, __func__, msg);
            }   
        }
        return;
    }
 
    int latestDDG = ddg_->latestCycle(moveNode, ii);
 
    if (ii != 0 && (minCycle > latestDDG)) {
        
        if (ddg_->latestCycle(moveNode, ii, true) > latestDDG) {
 
            if (renamer_ != NULL && allowPredicationAndRenaming) {
                // todo: do also otherway
                if (renamer_->renameSourceRegister(moveNode,true, true, true)) {
                    latestDDG = ddg_->latestCycle(moveNode, ii);
                } 
            }
        }
    }
 
    // test again after renaming? 
 
    if (ii != 0 && (minCycle > latestDDG)) {
 
        // if we pre-scheduled jump, unschedule it and try to schdule
        // the node again.
        if (jumpNode_ != NULL) {
            ddg_->writeToDotFile("unschedJump.dot");
            unschedule(*jumpNode_);
            jumpNode_ = NULL;
            scheduleMove(moveNode, earliestCycle, allowPredicationAndRenaming);
            return;
        }
 
        ddg_->writeToDotFile(
            std::string("ii_") + Conversion::toString(ii) + 
            std::string("_dag.dot"));
        
        unscheduleAllNodes();
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__, "Schedule failed try bigger ii.");
    }
 
    try {
        rm_->assign(minCycle,  moveNode);
    } catch (const Exception& e) {
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__, e.errorMessageStack());
    }
 
    if (!moveNode.isScheduled()) {
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__,
            (boost::format("Assignment of MoveNode '%s' failed!")
            % moveNode.toString()).str());
    }
    assert(moveNode.cycle() >= minCycle_);
}

References __func__, MoveNodeSet::addMoveNode(), Operation::affectsCount(), TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM, TTAProgram::ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN, assert, SimpleResourceManager::assign(), SimpleResourceManager::canTransportImmediate(), TTAMachine::Machine::controlUnit(), MoveNode::cycle(), ddg_, TTAMachine::ControlUnit::delaySlots(), TTAProgram::Move::destination(), MoveNode::destinationOperation(), DataDependenceGraph::earliestCycle(), SimpleResourceManager::earliestCycle(), MoveNode::earliestResultReadCycle(), Exception::errorMessageStack(), DataDependenceGraph::findLimitingAntidependenceSource(), DataDependenceGraph::findLoopLimitAndIndex(), MoveNode::guardLatency(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), Operation::hasSideEffects(), SimpleResourceManager::initiationInterval(), TTAProgram::Move::isControlFlowMove(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isReturn(), MoveNode::isScheduled(), MoveNode::isSourceConstant(), MoveNode::isSourceOperation(), TTAProgram::Move::isUnconditional(), jumpNode_, DataDependenceGraph::largestCycle(), SimpleResourceManager::largestCycle(), DataDependenceGraph::latestCycle(), minCycle_, MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), ProgramOperation::operation(), DataDependenceGraph::removeIncomingGuardEdges(), RegisterRenamer::renameDestinationRegister(), renamer_, RegisterRenamer::renameSourceRegister(), rm_, DataDependenceGraph::scheduledNodeCount(), scheduleMove(), TTAProgram::AnnotatedInstructionElement::setAnnotation(), TTAProgram::Move::setGuard(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), MoveNode::sourceOperation(), targetMachine_, MoveNode::toString(), Conversion::toString(), tripCount_, tryToOptimizeWaw(), unschedule(), unscheduleAllNodes(), DataDependenceGraph::unscheduledMoves(), SimValue::unsignedValue(), TTAProgram::TerminalImmediate::value(), SimValue::width(), Operation::writesMemory(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by handleDDG(), handleLoopDDG(), handleRemovedResultMoves(), scheduleInputOperandTempMoves(), scheduleMove(), scheduleOperandWrites(), scheduleResultReads(), scheduleResultReadTempMoves(), scheduleRRMove(), scheduleRRTempMoves(), and tryToOptimizeWaw().

scheduleOperandWrites()

int BasicBlockScheduler::scheduleOperandWrites ( int &  cycle, MoveNodeGroup &  moves  )

protected

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. This parameter is modified to the highest cycle one should try next in case scheduling starting from the given cycle failed.
moves	Moves of the operation execution.

Returns

The cycle the earliest of the operands got scheduled

Definition at line 629 of file BasicBlockScheduler.cc.

                                                                           {
    const int MAX_OPERAND_CYCLE_DIFFERENCE = 15;
 
    const int MAX_OPERATION_START_BEFORE_EARLIEST_READ = 50;
    
    int lastOperandCycle = 0;
    int earliestScheduledOperand = INT_MAX;
    int startCycle = 0;
    MoveNode* trigger = NULL;
    MoveNode* firstToSchedule = NULL;
 
    // find the movenode which has highest DDG->earliestCycle and limit
    // the starting cycle of all operands close to that.
    // this should prevent trying to schedule immediate writes very early
    // and having lots of retries until the cycle has risen to the level of
    // other moves.
    // this might make SCHEDULING_WINDOW or SimpleBrokerDirector unnecessary / 
    // allow groving it much smaller without scheduler slowdown.
    for (int i = 0; i < moves.nodeCount(); i++) {
        int limit = 0;
        if (moves.node(i).isDestinationOperation()) {
            limit = ddg_->earliestCycle(
                moves.node(i), rm_->initiationInterval()) - 
                MAX_OPERAND_CYCLE_DIFFERENCE;
        } else if (moves.node(i).isSourceOperation()) {
            limit = ddg_->earliestCycle(
                moves.node(i), rm_->initiationInterval()) - 
                MAX_OPERATION_START_BEFORE_EARLIEST_READ;
        } else {
            continue;
        }
        if (limit < 0) {
            limit = 0;
        }
        if (limit > cycle) {
            cycle = limit;
        }
    }
 
    // Find and schedule moveNode which has highest "earliest Cycle"
    // other moveNodes could be scheduled in earlier cycle but this
    // makes sure there will be no problems with operands overwritting
    // and assignment failures. At least it reduced a count of such.
    // Also find smallest of all earliest cycles,
    // make no sense to start from 0
    for (int i = 0; i < moves.nodeCount(); i++) {
        if (!moves.node(i).isDestinationOperation()) {
            continue;
        }
 
        // Temporary moves needs to be scheduled so DDG can find
        // earliest cycle
        // TODO: this should also have cycle limit?
    scheduleInputOperandTempMoves(moves.node(i), moves.node(i));
        int earliestDDG = ddg_->earliestCycle(
            moves.node(i), rm_->initiationInterval());
 
        if (earliestDDG == INT_MAX) {
            ddg_->writeToDotFile("failed_bb.dot");
            unscheduleInputOperandTempMoves(moves.node(i));
            throw InvalidData(
                __FILE__, __LINE__, __func__,
                (boost::format("InputTempMoves failed to schedule "
                "successfully for '%s' ") % moves.node(i).toString()).str());
        }
 
        // passed argument could be larger than what DDG thinks is earliest
        earliestDDG = std::max(earliestDDG, cycle);
        int earliest = rm_->earliestCycle(earliestDDG, moves.node(i));
        if (earliest == -1) {
            unscheduleInputOperandTempMoves(moves.node(i));
            continue;
        }
        if (earliest >= startCycle) {
            // Find first moveNode that will be scheduled
            startCycle = earliest;
            firstToSchedule = &moves.node(i);
        }
        unscheduleInputOperandTempMoves(moves.node(i));
 
        // Find also smallest of earliestCycles
        cycle = std::min(cycle, earliest);
    }
    
    if (firstToSchedule != NULL) {
        // start cycle could be null if there was problem scheduling
        // all input temp operands
        scheduleInputOperandTempMoves(*firstToSchedule, *firstToSchedule);
        // earliestCycle gave us the startCycle so this must pass
        scheduleMove(*firstToSchedule, startCycle, true);
        if (!firstToSchedule->isScheduled()) {
            ddg_->writeToDotFile(
                std::string("ii_") + 
                Conversion::toString(rm_->initiationInterval()) + 
                std::string("_dag.dot"));
 
            unscheduleAllNodes();
            throw ModuleRunTimeError(
                __FILE__, __LINE__, __func__,
                (boost::format("Move '%s' failed to schedule")
                % firstToSchedule->toString()).str());
        }
        startCycle = firstToSchedule->cycle();
        if (firstToSchedule->move().destination().isTriggering()) {
            trigger = firstToSchedule;
        } else {
            lastOperandCycle = std::max(lastOperandCycle, startCycle);
        }
    } else {        
        ddg_->writeToDotFile(
            std::string("ii_") + 
            Conversion::toString(rm_->initiationInterval()) + 
            std::string("_dag.dot"));
        
        unscheduleAllNodes();
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__,
            (boost::format(
                "Unable to schedule '%s' is there enough resources?")
             % moves.toString()).str());
    }
 
    // try to schedule all input moveNodes, except trigger
    for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
        MoveNode& moveNode = moves.node(moveIndex);
        // skip the result reads
        if (!moveNode.isDestinationOperation()) {
            continue;
        }
        
        if (moveNode.isScheduled()) {
            earliestScheduledOperand =
                std::min(earliestScheduledOperand, moveNode.cycle());
            if (moveNode.move().destination().isTriggering()) {
                trigger = &moveNode;
            }
            continue;
        }
        
        // in case the operand move requires register copies due to
        // missing connectivity, schedule them first
        scheduleInputOperandTempMoves(moveNode, moveNode);
        scheduleMove(moveNode, cycle, true);
        
        if (moveNode.isScheduled()) {
            earliestScheduledOperand =
                std::min(earliestScheduledOperand, moveNode.cycle());
            if (moveNode.move().destination().isTriggering()) {
                trigger = &moveNode;
                earliestScheduledOperand =
                    std::min(earliestScheduledOperand, moveNode.cycle());
            } else {
                lastOperandCycle =
                    std::max(lastOperandCycle, moveNode.cycle());
            }
        } else {
            // Movenode scheduling failed.
            unscheduleInputOperandTempMoves(moveNode);
            // try to unschedule trigger and then schedule this operand.
            if (trigger != NULL && trigger->isScheduled()) {
                unschedule(*trigger);
                unscheduleInputOperandTempMoves(*trigger);
                scheduleInputOperandTempMoves(moveNode, moveNode);
                scheduleMove(moveNode, cycle, true);
                if (!moveNode.isScheduled()) {
                // if still failed return -1
                    unscheduleInputOperandTempMoves(moveNode);
                    // but make sure high-level loop advances some more cycles
                    if (earliestScheduledOperand != INT_MAX) {
                        cycle = earliestScheduledOperand;
                    }
                    return -1;
                }
                earliestScheduledOperand =
                    std::min(earliestScheduledOperand, moveNode.cycle());
                lastOperandCycle =
                    std::max(lastOperandCycle, moveNode.cycle());
            } else {
                // failed even though no trigger scheduled.
                // but make sure high-level loop advances some more cycles
                if (earliestScheduledOperand != INT_MAX) {
                    cycle = earliestScheduledOperand;
                }
                return -1;
            }
        }
    }
 
    // if trigger unscheduled, schedule it again.
    assert(trigger != NULL);
    if (!trigger->isScheduled()) {
        scheduleInputOperandTempMoves(*trigger, *trigger);
        scheduleMove(*trigger, lastOperandCycle, true);
        
        if (!trigger->isScheduled()) {
            // trigger scheduling failed.
            unscheduleInputOperandTempMoves(*trigger);
            return -1;
        }
        earliestScheduledOperand =
            std::min(earliestScheduledOperand, trigger->cycle());
    }
    
    return earliestScheduledOperand;
}

References __func__, assert, MoveNode::cycle(), ddg_, TTAProgram::Move::destination(), DataDependenceGraph::earliestCycle(), SimpleResourceManager::earliestCycle(), SimpleResourceManager::initiationInterval(), MoveNode::isDestinationOperation(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), TTAProgram::Terminal::isTriggering(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), rm_, scheduleInputOperandTempMoves(), scheduleMove(), MoveNodeGroup::toString(), MoveNode::toString(), Conversion::toString(), unschedule(), unscheduleAllNodes(), unscheduleInputOperandTempMoves(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by scheduleOperation().

Here is the call graph for this function:

scheduleOperation()

void BasicBlockScheduler::scheduleOperation ( MoveNodeGroup &  moves )

protected

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.

Definition at line 397 of file BasicBlockScheduler.cc.

                                                           {
    ProgramOperation& po =
        (moves.node(0).isSourceOperation())?
        (moves.node(0).sourceOperation()):
        (moves.node(0).destinationOperation());
 
    // may switch operands of commutative operations. Do it before
    // regcopyadder because it's easier here.
    // cooperation with regcopyadder might make it perform better though.
    tryToSwitchInputs(po);
 
#ifdef DEBUG_REG_COPY_ADDER
    ddg_->setCycleGrouping(true);
    ddg_->writeToDotFile(
        (boost::format("%s_before_ddg.dot") % ddg_->name()).str());
#endif
 
    RegisterCopyAdder regCopyAdder(
        DDGPass::interPassData(), *rm_, *selector_);
    RegisterCopyAdder::AddedRegisterCopies copies = 
        regCopyAdder.addMinimumRegisterCopies(po, *targetMachine_, ddg_);
#ifdef DEBUG_REG_COPY_ADDER
    const int tempsAdded = copies.count_;
#endif
 
#ifdef DEBUG_REG_COPY_ADDER
    if (tempsAdded > 0) {
        ddg_->writeToDotFile(
            (boost::format("%s_after_regcopy_ddg.dot") % ddg_->name()).str());
    }
    ddg_->sanityCheck();
#endif
 
    MoveNodeSet tempSet;
    for (int i = 0; i < moves.nodeCount(); i++) {
        // MoveNodeGroup relates to DDG so we copy it to
        // a simpler MoveNodeSet container
        tempSet.addMoveNode(moves.node(i));
    }
 
    bool operandsFailed = true;
    bool resultsFailed = true;
    int operandsStartCycle = 0;
 
    int maxFromRm = rm_->largestCycle();
 
    // Magic number defining how many times we should try to schedule
    // operands and results. Should not be needed in final version of
    // scheduler
    const int retryCount = 20;
    int minOperand = operandsStartCycle;
 
    bool tryBypassing = softwareBypasser_ != NULL;
    bool bypassTrigger = true;
 
    while ((operandsFailed || resultsFailed) &&
           operandsStartCycle < maxFromRm + retryCount) {
 
        minOperand = scheduleOperandWrites(operandsStartCycle, moves);
        if (minOperand != -1) {
            operandsFailed = false;
        } else {
            // Scheduling some operand failed, unschedule and try later cycle
            for (int i = 0; i < moves.nodeCount(); i++){
                MoveNode& moveNode = moves.node(i);
                if (moveNode.isScheduled() &&
                    moveNode.isDestinationOperation()) {
                    unschedule(moveNode);
                    unscheduleInputOperandTempMoves(moveNode);
                }
            }
            operandsFailed = true;
            operandsStartCycle++;
            continue;
        }
 
        regCopyAdder.operandsScheduled(copies, *ddg_);
 
        int bypassedMoves = -1;
        if (tryBypassing) {
            bypassedMoves = softwareBypasser_->bypass(
                moves, *ddg_, *rm_, bypassTrigger);
            if (bypassedMoves == -1){
                // bypassing failed try again without attempt to bypass
                // this restores the original schedule of operands
                // and disable bypassing
                operandsFailed = true;
                if (bypassTrigger == false) {
                    tryBypassing = false;
                } else {
                    bypassTrigger = false;
                }
                softwareBypasser_->removeBypass(moves, *ddg_, *rm_);
                continue;
            }
            // bypass was success
        }
 
    // TODO: disabled because may cause fail if rescheduled
    // to different bus.
//        tryToDelayOperands(moves);
 
        if (scheduleResultReads(moves)) {
            resultsFailed = false;
            // Results were scheduled, we are not going to change schedule
            // of this program operation. Lets check if some of the
            // bypassed operands did not produce dead result moves
            if (tryBypassing) {
                try {
                    std::set<std::pair<TTAProgram::Move*, int> >
                        removedMoves;                        
                    softwareBypasser_->removeDeadResults(
                        moves, *ddg_, *rm_, removedMoves);
                    handleRemovedResultMoves(removedMoves);
                } catch (const Exception& e) {
                    throw ModuleRunTimeError(
                        __FILE__, __LINE__, __func__, e.errorMessageStack());
                }
            }
        } else {
            // Scheduling results failed, most likely due to large distance
            // between trigger and earliest result cycle
            // Some other operation is overwritting result on same FU
            for (int i = 0; i < moves.nodeCount(); i++){
                MoveNode& moveNode = moves.node(i);
                if (moveNode.isScheduled()) {
                    // Operands were scheduled successfully but result can
                    // not be, we unschedule everything
                    unschedule(moveNode);
                    if (moveNode.isDestinationOperation()) {
                        unscheduleInputOperandTempMoves(moveNode);
                    }
                    if (moveNode.isSourceOperation()) {
                        unscheduleResultReadTempMoves(moveNode);
                    }
                }
            }
            resultsFailed = true;
            // If some operands were bypassed, we need to remove bypassing
            if (tryBypassing) {
                softwareBypasser_->removeBypass(moves, *ddg_, *rm_);
                tryBypassing = false;
                continue;
            }
            // We will try to schedule operands in later cycle
            // taking larger strides
            operandsStartCycle++;
            minOperand++;
            operandsStartCycle = std::max(minOperand, operandsStartCycle);
        }
    }
    // This fails if there is "timeout" on retry count.
    // Should not be needed in final version.
 
    if (operandsFailed) {
        ddg_->writeToDotFile(
            std::string("ii_") + 
            Conversion::toString(rm_->initiationInterval()) + 
            std::string("_dag.dot"));
 
        unscheduleAllNodes();
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__,
            "Operands scheduling failed for \'" + moves.toString());
    }
    if (resultsFailed) {
        ddg_->writeToDotFile(
            std::string("ii_") + 
            Conversion::toString(rm_->initiationInterval()) + 
            std::string("_dag.dot"));
 
        unscheduleAllNodes();
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__,
            "Results scheduling failed for \'" + moves.toString());
    }
 
    if (options_ != NULL &&
        (options_->dumpDDGsDot() || options_->dumpDDGsDot()) &&
        (resultsFailed || operandsFailed)) {
 
        //static int failedCounter = 0;
    if (options_->dumpDDGsDot()) {
        ddgSnapshot(*ddg_, std::string("2_failed.dot"),
            DataDependenceGraph::DUMP_DOT, true);
    } else {
        ddgSnapshot(*ddg_, std::string("2_failed.xml"),
            DataDependenceGraph::DUMP_XML, true);
    }
 
        unscheduleAllNodes();
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__,
            (boost::format("Bad BB %s") % ddg_->name()).str());
    }
 
    regCopyAdder.resultsScheduled(copies, *ddg_);
 
#ifdef DEBUG_REG_COPY_ADDER
    if (tempsAdded > 0) {
        ddg_->writeToDotFile(
            (boost::format("%s_after_scheduler_ddg.dot") %
             ddg_->name()).str());
        Application::logStream()
            << "(operation fix #" << ddg_->name() << ")" << std::endl
            << std::endl;
 
        ++graphCount;
    }
#endif
}

References __func__, RegisterCopyAdder::addMinimumRegisterCopies(), MoveNodeSet::addMoveNode(), SoftwareBypasser::bypass(), RegisterCopyAdder::AddedRegisterCopies::count_, ddg_, ddgSnapshot(), MoveNode::destinationOperation(), DataDependenceGraph::DUMP_DOT, DataDependenceGraph::DUMP_XML, LLVMTCECmdLineOptions::dumpDDGsDot(), Exception::errorMessageStack(), handleRemovedResultMoves(), SimpleResourceManager::initiationInterval(), SchedulerPass::interPassData(), MoveNode::isDestinationOperation(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), SimpleResourceManager::largestCycle(), Application::logStream(), BoostGraph< GraphNode, GraphEdge >::name(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), RegisterCopyAdder::operandsScheduled(), options_, SoftwareBypasser::removeBypass(), SoftwareBypasser::removeDeadResults(), RegisterCopyAdder::resultsScheduled(), rm_, DataDependenceGraph::sanityCheck(), scheduleOperandWrites(), scheduleResultReads(), selector_, DataDependenceGraph::setCycleGrouping(), softwareBypasser_, MoveNode::sourceOperation(), targetMachine_, MoveNodeGroup::toString(), Conversion::toString(), tryToSwitchInputs(), unschedule(), unscheduleAllNodes(), unscheduleInputOperandTempMoves(), unscheduleResultReadTempMoves(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by handleDDG(), and handleLoopDDG().

Here is the call graph for this function:

scheduleResultReads()

bool BasicBlockScheduler::scheduleResultReads ( MoveNodeGroup &  moves )

protected

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.

Definition at line 843 of file BasicBlockScheduler.cc.

                                                             {
    int tempRegLimitCycle = 0;
 
    for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
        MoveNode& moveNode = moves.node(moveIndex);
 
        if (!moveNode.isScheduled()) {
            if (!moveNode.isSourceOperation()) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    (boost::format("Move to schedule '%s' is not "
                    "result move!") % moveNode.toString()).str());
            }
            if (succeedingTempMove(moveNode) != NULL) {
 
                MoveNode* lastRead =
                    ddg_->lastScheduledRegisterRead(
                        moveNode.move().destination().registerFile(),
                        moveNode.move().destination().index());
                if (lastRead != NULL) {
                    tempRegLimitCycle = lastRead->cycle();
                }
            }
 
            scheduleMove(moveNode, tempRegLimitCycle, true);
            if (!moveNode.isScheduled()) {
                // Result can not be scheduled even when operands were,
                // usually caused by operands too early (data dependencies
                // ok) and result forced to be scheduled much later
                // because of data dependencies (WA{R,W} dependence with
                // target register in most cases)
                return false;
            }
            scheduleResultReadTempMoves(moveNode, moveNode, 0);
            if (!moveNode.isScheduled()) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    (boost::format("Move '%s' did not get scheduled!")
                    % moveNode.toString()).str());
            }
        }
    }
    return true;
}

References __func__, MoveNode::cycle(), ddg_, TTAProgram::Move::destination(), TTAProgram::Terminal::index(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), DataDependenceGraph::lastScheduledRegisterRead(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), TTAProgram::Terminal::registerFile(), scheduleMove(), scheduleResultReadTempMoves(), succeedingTempMove(), and MoveNode::toString().

Referenced by scheduleOperation().

Here is the call graph for this function:

scheduleResultReadTempMoves()

void BasicBlockScheduler::scheduleResultReadTempMoves ( MoveNode &  resultMove, MoveNode &  resultRead, int  lastUse  )

protected

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

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

Parameters

resultMove	A temp move whose successor has to be scheduled.
resultRead	The original move of which temp moves to schedule.
lastUse	Recursive function parameter, it should be set as 0 for the first function call.

Definition at line 1438 of file BasicBlockScheduler.cc.

                                                             {
    /* Because temporary register moves do not have WaR/WaW dependency edges
       between the other possible uses of the same temp register in
       the same operation, we have to limit the scheduling of the new
       temp reg move to the last use of the same temp register so
       we don't overwrite the temp registers of the other operands. */
 
 
    // find all unscheduled succeeding moves of the result read move
    // there should be only only one with the only dependence edge (RaW) to
    // the result move
 
    MoveNode* tempMove1 = succeedingTempMove(resultMove);
    if (tempMove1 == NULL)
        return; // no temp moves found
 
    MoveNode* tempMove2 = succeedingTempMove(*tempMove1);
    if (tempMove2 != NULL) {
        MoveNode* lastRead =
            ddg_->lastScheduledRegisterRead(
                tempMove1->move().destination().registerFile(),
                tempMove1->move().destination().index());
        if (lastRead != NULL)
            lastUse = lastRead->cycle();
    }
 
    scheduleMove(*tempMove1, lastUse, true);
    assert(tempMove1->isScheduled());
    scheduledTempMoves_[&resultRead].insert(tempMove1);
 
    // the temp move should have maximum of one unscheduled
    // succeeding additional reg to reg copy (in case of two temp reg copies),
    // schedule it also if found
    scheduleResultReadTempMoves(*tempMove1, resultRead, lastUse+1);
}

References assert, MoveNode::cycle(), ddg_, TTAProgram::Move::destination(), TTAProgram::Terminal::index(), MoveNode::isScheduled(), DataDependenceGraph::lastScheduledRegisterRead(), MoveNode::move(), TTAProgram::Terminal::registerFile(), scheduledTempMoves_, scheduleMove(), scheduleResultReadTempMoves(), and succeedingTempMove().

Referenced by scheduleResultReads(), scheduleResultReadTempMoves(), and scheduleRRTempMoves().

Here is the call graph for this function:

scheduleRRMove()

void BasicBlockScheduler::scheduleRRMove ( MoveNode &  moveNode )

protected

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

moveNode

R-R Move to schedule.

Definition at line 898 of file BasicBlockScheduler.cc.

                                                      {
#ifdef DEBUG_REG_COPY_ADDER
    ddg_->setCycleGrouping(true);
    ddg_->writeToDotFile(
        (boost::format("%s_before_ddg.dot") % ddg_->name()).str());
#endif
 
    RegisterCopyAdder regCopyAdder(
        DDGPass::interPassData(), *rm_, *selector_);
 
#ifdef DEBUG_REG_COPY_ADDER
    const int tempsAdded =
#endif
 
        regCopyAdder.addRegisterCopiesToRRMove(moveNode, ddg_)
#ifdef DEBUG_REG_COPY_ADDER
        .count_
#endif    
        ;
#ifdef DEBUG_REG_COPY_ADDER
    if (tempsAdded > 0) {
        ddg_->writeToDotFile(
            (boost::format("%s_after_regcopy_ddg.dot") % ddg_->name()).str());
    }
    ddg_->sanityCheck();
#endif
 
    scheduleMove(moveNode, 0, true);
    scheduleRRTempMoves(moveNode, moveNode, 0); //Fabio: 0 or more?!?
}

References RegisterCopyAdder::addRegisterCopiesToRRMove(), RegisterCopyAdder::AddedRegisterCopies::count_, ddg_, SchedulerPass::interPassData(), BoostGraph< GraphNode, GraphEdge >::name(), rm_, DataDependenceGraph::sanityCheck(), scheduleMove(), scheduleRRTempMoves(), selector_, DataDependenceGraph::setCycleGrouping(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by handleDDG(), and handleLoopDDG().

Here is the call graph for this function:

scheduleRRTempMoves()

void BasicBlockScheduler::scheduleRRTempMoves ( MoveNode &  regToRegMove, MoveNode &  firstMove, int  lastUse  )

protected

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

regToRegMove	A temp move whose successor has to be scheduled.
firstMove	The original move of which temp moves to schedule.
lastUse	Recursive function parameter, it should be set as 0 for the first function call.

Definition at line 1293 of file BasicBlockScheduler.cc.

                                                              {
    /* Because temporary register moves do not have WaR/WaW dependency edges
       between the other possible uses of the same temp register in
       the same operation, we have to limit the scheduling of the new
       temp reg move to the last use of the same temp register so
       we don't overwrite the temp registers of the other operands. */
 
    // find all unscheduled succeeding moves of the result read move
    // there should be only only one with the only dependence edge (RaW) to
    // the result move
 
    MoveNode* tempMove1 = succeedingTempMove(regToRegMove);
    if (tempMove1 == NULL)
        return; // no temp moves found
    
    MoveNode* tempMove2 = succeedingTempMove(*tempMove1);
    if (tempMove2 != NULL) {
        MoveNode* lastRead =
            ddg_->lastScheduledRegisterRead(
                tempMove1->move().destination().registerFile(),
                tempMove1->move().destination().index());
        if (lastRead != NULL)
            lastUse = lastRead->cycle();
    }
 
    scheduleMove(*tempMove1, lastUse, true);
    assert(tempMove1->isScheduled());
    scheduledTempMoves_[&firstMove].insert(tempMove1);
 
    // the temp move should have maximum of one unscheduled
    // succeeding additional reg to reg copy (in case of two temp reg copies),
    // schedule it also if found
    scheduleResultReadTempMoves(*tempMove1, firstMove, lastUse+1);
}

References assert, MoveNode::cycle(), ddg_, TTAProgram::Move::destination(), TTAProgram::Terminal::index(), MoveNode::isScheduled(), DataDependenceGraph::lastScheduledRegisterRead(), MoveNode::move(), TTAProgram::Terminal::registerFile(), scheduledTempMoves_, scheduleMove(), scheduleResultReadTempMoves(), and succeedingTempMove().

Referenced by scheduleRRMove().

Here is the call graph for this function:

shortDescription()

std::string BasicBlockScheduler::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.

Reimplemented in BUBasicBlockScheduler.

Definition at line 1570 of file BasicBlockScheduler.cc.

                                            {
    return "Instruction scheduler with a basic block scope.";
}

succeedingTempMove()

MoveNode * BasicBlockScheduler::succeedingTempMove ( MoveNode &  current )

protected

Finds the temp move succeeding the given movenode.

If it does not have one , returns null.

Parameters

current

MoveNode whose tempmoves we are searching

Returns

tempMove succeeding given node, or null if does not exist.

Definition at line 1406 of file BasicBlockScheduler.cc.

                                                         {
 
    DataDependenceGraph::NodeSet succ = ddg_->successors(current);
    MoveNode* result = NULL;
    for (DataDependenceGraph::NodeSet::iterator i = succ.begin();
         i != succ.end(); ++i) {
        MoveNode& m = **i;
        if (m.isScheduled() ||
            !m.move().hasAnnotations(
                TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE))
            continue;
 
        assert(result == NULL &&
               "Multiple candidates for the temp move of result read.");
        result = &m;
    }
    return result;
}

References TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE, assert, ddg_, TTAProgram::AnnotatedInstructionElement::hasAnnotations(), MoveNode::isScheduled(), MoveNode::move(), and BoostGraph< GraphNode, GraphEdge >::successors().

Referenced by BUBasicBlockScheduler::bypassNode(), scheduleResultReads(), BUBasicBlockScheduler::scheduleResultReads(), scheduleResultReadTempMoves(), BUBasicBlockScheduler::scheduleResultReadTempMoves(), scheduleRRTempMoves(), and BUBasicBlockScheduler::scheduleRRTempMoves().

Here is the call graph for this function:

tryToDelayOperands()

void BasicBlockScheduler::tryToDelayOperands ( MoveNodeGroup &  moves )

protected

Definition at line 2017 of file BasicBlockScheduler.cc.

                                                            {
    
    // try to then push non-triggers back
    // to as close as possible to tirggers.
    // this frees up the FU to be used fr other operations before
    // this operation.
    // first search first cycle when this FU is used.
 
    int ec = INT_MAX;
    MoveNode* trigger = NULL;
    for (int i = 0; i < moves.nodeCount(); i++) {
        MoveNode& moveNode = moves.node(i);
        if (!moveNode.isDestinationOperation()) {
            continue;
        }
        if (moveNode.move().isTriggering()) {
            trigger = &moveNode;
        } else {
            int oldCycle = moveNode.cycle();
            if (oldCycle < ec) {
                ec = oldCycle;
            }
        }
    }
 
    int triggerCycle = trigger->cycle();
    
    bool failed = false;
    while (ec < triggerCycle && !failed) {
        for (int i = 0; i < moves.nodeCount(); i++) {
            MoveNode& moveNode = moves.node(i);
            if (!moveNode.isDestinationOperation()) {
                continue;
            }
            if (&moveNode != trigger) {
                int oldCycle = moveNode.cycle();
                if (oldCycle == ec) {
                    int latest = ddg_->latestCycle(moveNode);
                    if (latest > oldCycle) {
                        latest = std::min(latest, triggerCycle);
                        assert(latest >= ec);
                        rm_->unassign(moveNode);
                        int latestrm = rm_->latestCycle(latest, moveNode);
                        if (latestrm == ec) {
                            failed = true;
                        }
                        assert(latestrm >= ec);
                        rm_->assign(latestrm, moveNode);
                    } else {
                        failed = true;
                    }
                }
            }
        }
        ec = INT_MAX;
        // first earliest scheduled operands.
        for (int i = 0; i < moves.nodeCount(); i++) {
            MoveNode& moveNode = moves.node(i);
            if (!moveNode.isDestinationOperation()) {
                continue;
            }
            if (&moveNode != trigger) {
                int oldCycle = moveNode.cycle();
                if (oldCycle < ec) {
                    ec = oldCycle;
                }
            }
        }
    }
}

References assert, SimpleResourceManager::assign(), MoveNode::cycle(), ddg_, MoveNode::isDestinationOperation(), TTAProgram::Move::isTriggering(), DataDependenceGraph::latestCycle(), SimpleResourceManager::latestCycle(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), rm_, and SimpleResourceManager::unassign().

Here is the call graph for this function:

tryToOptimizeWaw()

bool BasicBlockScheduler::tryToOptimizeWaw ( const MoveNode &  moveNode )

protected

Tries to get rid of WaW dependence from unconditional to conditional.

if the conditional move's result is overwritten by the cond for all users, make the unconditional move conditional, with opposite guard.

Definition at line 1916 of file BasicBlockScheduler.cc.

                                                              {
 
    if (ddg_->earliestCycle(moveNode, 0 , false, true) >=
        ddg_->earliestCycle(moveNode)) {
        return false;
    }
    
    MoveNode* wawPred = NULL;
    DataDependenceEdge* wawEdge = NULL;
 
    DataDependenceGraph::EdgeSet inEdges = ddg_->inEdges(moveNode);
    for (DataDependenceGraph::EdgeSet::iterator i = inEdges.begin();
         i != inEdges.end(); i++) {
        DataDependenceEdge* e = *i;
 
        if (e->dependenceType() == DataDependenceEdge::DEP_WAW &&
            e->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
            !e->tailPseudo()) {
            if (wawPred == NULL) {
                wawPred = &ddg_->tailNode(**i);
                wawEdge = e;
            } else {
                return false;
            }
        }
    }
    if (wawPred == NULL) {
        return false;
    }
 
    assert(wawPred->isScheduled());
    int wawPredCycle = wawPred->cycle();
    
    if (!wawPred->move().isUnconditional()) {
        return false;
    }
 
    DataDependenceGraph::NodeSet gdMoves = ddg_->guardDefMoves(moveNode);
    for (DataDependenceGraph::NodeSet::iterator i = gdMoves.begin();
         i != gdMoves.end(); i++) {
        MoveNode& mn = **i;
        assert(mn.isScheduled());
        if (mn.cycle() + moveNode.guardLatency() > wawPredCycle) {
            return false;
        }
    }
 
    // check that no other usage of the data.
    DataDependenceGraph::NodeSet consumers = ddg_->regRawSuccessors(*wawPred);
    DataDependenceGraph::NodeSet consumers2 = ddg_->regRawSuccessors(moveNode);
    for (DataDependenceGraph::NodeSet::iterator i = consumers.begin();
         i != consumers.end(); i++) {
        MoveNode* mn = *i;
        if (consumers2.find(mn) == consumers2.end() &&
            (mn->move().isUnconditional() ||
             !ddg_->exclusingGuards(*mn, moveNode))) {
            return false;
        }
    }
 
    unschedule(*wawPred);
 
    TTAProgram::CodeGenerator cg(*targetMachine_);
    wawPred->move().setGuard(cg.createInverseGuard(moveNode.move().guard()));
 
    ddg_->copyDepsOver(*wawPred, true, false);
    
    ddg_->copyIncomingGuardEdges(moveNode, *wawPred);
    ddg_->copyOutgoingGuardWarEdges(moveNode, *wawPred);
    
    ddg_->removeEdge(*wawEdge);
    
    bool revert = false;
 
    try {
        scheduleMove(*wawPred, wawPredCycle, false);
 
        if (!wawPred->isScheduled()) {
            revert = true;
        }
        if (wawPred->isScheduled() && wawPred->cycle() > wawPredCycle) {
            unschedule(*wawPred);
            revert = true;
        }
    } catch (Exception&e) {
        revert = true;
    }
 
    if (revert) {
        wawPred->move().setGuard(NULL);
        ddg_->removeIncomingGuardEdges(*wawPred);
        ddg_->removeOutgoingGuardWarEdges(*wawPred);
        scheduleMove(*wawPred, wawPredCycle, false);
        ddg_->connectNodes(*wawPred, moveNode, *wawEdge);
        return false;
    }
 
    return true;
}

References assert, BoostGraph< GraphNode, GraphEdge >::connectNodes(), DataDependenceGraph::copyDepsOver(), DataDependenceGraph::copyIncomingGuardEdges(), DataDependenceGraph::copyOutgoingGuardWarEdges(), TTAProgram::CodeGenerator::createInverseGuard(), MoveNode::cycle(), ddg_, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), DataDependenceGraph::earliestCycle(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceGraph::exclusingGuards(), TTAProgram::Move::guard(), DataDependenceGraph::guardDefMoves(), MoveNode::guardLatency(), BoostGraph< GraphNode, GraphEdge >::inEdges(), MoveNode::isScheduled(), TTAProgram::Move::isUnconditional(), MoveNode::move(), DataDependenceGraph::regRawSuccessors(), BoostGraph< GraphNode, GraphEdge >::removeEdge(), DataDependenceGraph::removeIncomingGuardEdges(), DataDependenceGraph::removeOutgoingGuardWarEdges(), scheduleMove(), TTAProgram::Move::setGuard(), BoostGraph< GraphNode, GraphEdge >::tailNode(), DataDependenceEdge::tailPseudo(), targetMachine_, and unschedule().

Referenced by scheduleMove().

Here is the call graph for this function:

tryToSwitchInputs()

bool BasicBlockScheduler::tryToSwitchInputs ( ProgramOperation &  po )

protected

If the operation is commutative, tries to change the operands so that the scheduler can schedule it better.

If the operation is not commutative, does nothing.

Which is better depends lots on the code being compiled and architecture which we are compiling for.

Current implementation tries to make constants triggers, and if there are no constant inputs, try to also change inputs so that last ready operand becomes trigger if it's near, but first ready operand becomes trigger if it's further (allows better bypassing of other operands) This seems to work in practice

Parameters

po	programoperation whose inputs to switch

Returns

true if changed inputs, false if not.

Definition at line 1730 of file BasicBlockScheduler.cc.

                                                           {
    const Operation& op = po.operation();
    if (op.numberOfInputs() == 2 && op.canSwap(1, 2)) {
        
        int triggerOperand = getTriggerOperand(op, *targetMachine_);
 
        if (triggerOperand != 0) {
            MoveNode* latest = NULL;
            int latestMinCycle = -1;
            int firstMinCycle = INT_MAX;
 
            //check all input moves.
            for (int i = 0; i < po.inputMoveCount(); i++) {
                MoveNode& node = po.inputMove(i);
                // always make constants triggers.
                // todo: shoudl do this only with short imms?
                if (node.isSourceConstant()) {
                    int operandIndex = 
                        node.move().destination().operationIndex();
                    if (operandIndex != triggerOperand) {
                        po.switchInputs();
                        return true;
                    } else {
                        return false;
                    }
                }
 
                int minCycle = ddg_->earliestCycle(
                    node, rm_->initiationInterval(), false, false, true, true);
                if (minCycle > latestMinCycle) {
                    latest = &node;
                    latestMinCycle = minCycle;
                }
                if (minCycle < firstMinCycle) {
                    firstMinCycle = minCycle;
                }
            }
 
            int lastOperand = latest->move().destination().operationIndex();
 
            // don't change if min cycles of first and alst are equal.
            if (latestMinCycle == firstMinCycle) {
                return false;
            }
            if (latestMinCycle - firstMinCycle > 1) { // reverse logic if far.
                if (lastOperand == triggerOperand) {
                    po.switchInputs();
                    return true;
                }
            } else {
                if (lastOperand != triggerOperand) {
                    po.switchInputs();
                    return true;
                }
            }
        }
    }
    return false;
}

References Operation::canSwap(), ddg_, TTAProgram::Move::destination(), DataDependenceGraph::earliestCycle(), getTriggerOperand(), SimpleResourceManager::initiationInterval(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isSourceConstant(), MoveNode::move(), Operation::numberOfInputs(), ProgramOperation::operation(), TTAProgram::Terminal::operationIndex(), rm_, ProgramOperation::switchInputs(), and targetMachine_.

Referenced by scheduleOperation().

Here is the call graph for this function:

unschedule()

void BasicBlockScheduler::unschedule ( MoveNode &  moveNode )

protected

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 1484 of file BasicBlockScheduler.cc.

                                                  {
    if (moveNode.isScheduled()) {
        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 BUBasicBlockScheduler::bypassNode(), handleRemovedResultMoves(), scheduleMove(), scheduleOperandWrites(), BUBasicBlockScheduler::scheduleOperandWrites(), scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), BUBasicBlockScheduler::scheduleResultReads(), tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), BUBasicBlockScheduler::undoBypass(), unscheduleAllNodes(), BUBasicBlockScheduler::unscheduleAllNodes(), unscheduleInputOperandTempMoves(), and unscheduleResultReadTempMoves().

Here is the call graph for this function:

unscheduleAllNodes()

void BasicBlockScheduler::unscheduleAllNodes ( )

protected

Calls unschedule() for all ddg nodes, which are scheduled.

Definition at line 1507 of file BasicBlockScheduler.cc.

                                        {
    DataDependenceGraph::NodeSet scheduled = ddg_->scheduledMoves();
    for (DataDependenceGraph::NodeSet::iterator i = scheduled.begin();
         i != scheduled.end(); ++i) {
        if (softwareBypasser_ != NULL) {
            softwareBypasser_->removeBypass(**i, *ddg_, *rm_, false);
        }
        unschedule(**i);
    }
    if (softwareBypasser_ != NULL) {
        softwareBypasser_->clearCaches(*ddg_, false);
    }
}

References SoftwareBypasser::clearCaches(), ddg_, SoftwareBypasser::removeBypass(), rm_, DataDependenceGraph::scheduledMoves(), softwareBypasser_, and unschedule().

Referenced by handleDDG(), handleLoopDDG(), scheduleMove(), scheduleOperandWrites(), and scheduleOperation().

Here is the call graph for this function:

unscheduleInputOperandTempMoves()

void BasicBlockScheduler::unscheduleInputOperandTempMoves ( MoveNode &  operandMove )

protected

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

Parameters

operandMove

The move of which temp moves to unschedule.

Definition at line 1528 of file BasicBlockScheduler.cc.

                                                                          {
 
    if (!MapTools::containsKey(scheduledTempMoves_, &operandMove))
        return; // nothing to unschedule
 
    DataDependenceGraph::NodeSet tempMoves = scheduledTempMoves_[&operandMove];
 
    for (DataDependenceGraph::NodeSet::iterator i = tempMoves.begin();
         i != tempMoves.end(); ++i) {
        unschedule(**i);
    }
    scheduledTempMoves_.erase(&operandMove);
}

References MapTools::containsKey(), scheduledTempMoves_, and unschedule().

Referenced by scheduleOperandWrites(), BUBasicBlockScheduler::scheduleOperandWrites(), scheduleOperation(), and BUBasicBlockScheduler::scheduleOperation().

Here is the call graph for this function:

unscheduleResultReadTempMoves()

void BasicBlockScheduler::unscheduleResultReadTempMoves ( MoveNode &  resultMove )

protected

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

Parameters

resultMove

The move of which temp moves to unschedule.

Definition at line 1549 of file BasicBlockScheduler.cc.

                                                                       {
 
    if (!MapTools::containsKey(scheduledTempMoves_, &resultMove))
        return; // nothing to unschedule
 
    DataDependenceGraph::NodeSet tempMoves = scheduledTempMoves_[&resultMove];
 
    for (DataDependenceGraph::NodeSet::iterator i = tempMoves.begin();
         i != tempMoves.end(); ++i) {
        unschedule(**i);
    }
    scheduledTempMoves_.erase(&resultMove);
}

References MapTools::containsKey(), scheduledTempMoves_, and unschedule().

Referenced by scheduleOperation(), and BUBasicBlockScheduler::scheduleOperation().

Here is the call graph for this function:

Member Data Documentation

bypassedCount_

int BasicBlockScheduler::bypassedCount_

protected

Definition at line 165 of file BasicBlockScheduler.hh.

ddg_

DataDependenceGraph* BasicBlockScheduler::ddg_

protected

DDG of the currently scheduled BB.

Definition at line 149 of file BasicBlockScheduler.hh.

Referenced by BUBasicBlockScheduler::bypassNode(), BUBasicBlockScheduler::clearRemovedNodes(), ddgSnapshot(), BUBasicBlockScheduler::finalizeSchedule(), BUBasicBlockScheduler::findBypassDestinations(), BUBasicBlockScheduler::handleDDG(), handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), handleRemovedResultMoves(), BUBasicBlockScheduler::precedingTempMove(), scheduleInputOperandTempMoves(), BUBasicBlockScheduler::scheduleInputOperandTempMoves(), BUBasicBlockScheduler::scheduleMove(), scheduleMove(), BUBasicBlockScheduler::scheduleOperand(), scheduleOperandWrites(), BUBasicBlockScheduler::scheduleOperandWrites(), scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), scheduleResultReads(), BUBasicBlockScheduler::scheduleResultReads(), scheduleResultReadTempMoves(), BUBasicBlockScheduler::scheduleResultReadTempMoves(), scheduleRRMove(), BUBasicBlockScheduler::scheduleRRMove(), scheduleRRTempMoves(), BUBasicBlockScheduler::scheduleRRTempMoves(), succeedingTempMove(), tryToDelayOperands(), tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), tryToSwitchInputs(), BUBasicBlockScheduler::tryToSwitchInputs(), BUBasicBlockScheduler::undoBypass(), unscheduleAllNodes(), and BUBasicBlockScheduler::unscheduleAllNodes().

deadResults_

int BasicBlockScheduler::deadResults_

protected

Definition at line 166 of file BasicBlockScheduler.hh.

jumpNode_

MoveNode* BasicBlockScheduler::jumpNode_

protected

Definition at line 170 of file BasicBlockScheduler.hh.

Referenced by handleLoopDDG(), and scheduleMove().

minCycle_

int BasicBlockScheduler::minCycle_

protected

The earliest cycle to schedule moves in. Used to leave room for sched_yield() by the sched_yield() emitter.

Definition at line 162 of file BasicBlockScheduler.hh.

Referenced by handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), and scheduleMove().

options_

LLVMTCECmdLineOptions* BasicBlockScheduler::options_

protected

Definition at line 168 of file BasicBlockScheduler.hh.

Referenced by BasicBlockScheduler(), BUBasicBlockScheduler::BUBasicBlockScheduler(), BUBasicBlockScheduler::handleDDG(), handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), and scheduleOperation().

renamer_

RegisterRenamer* BasicBlockScheduler::renamer_

protected

Definition at line 158 of file BasicBlockScheduler.hh.

Referenced by BUBasicBlockScheduler::handleDDG(), handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::scheduleMove(), and scheduleMove().

rm_

SimpleResourceManager* BasicBlockScheduler::rm_

protected

Resource Manager of the currently scheduled BB.

Definition at line 151 of file BasicBlockScheduler.hh.

Referenced by BUBasicBlockScheduler::bypassNode(), BUBasicBlockScheduler::findBypassDestinations(), BUBasicBlockScheduler::handleDDG(), handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), handleRemovedResultMoves(), BUBasicBlockScheduler::scheduleMove(), scheduleMove(), scheduleOperandWrites(), BUBasicBlockScheduler::scheduleOperandWrites(), scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), scheduleRRMove(), BUBasicBlockScheduler::scheduleRRMove(), tryToDelayOperands(), tryToSwitchInputs(), BUBasicBlockScheduler::tryToSwitchInputs(), unschedule(), and unscheduleAllNodes().

scheduledTempMoves_

std::map<const MoveNode*, DataDependenceGraph::NodeSet> BasicBlockScheduler::scheduledTempMoves_

protected

Stores the MoveNodes that were scheduled as temp moves during scheduling of the operand move.

Definition at line 154 of file BasicBlockScheduler.hh.

Referenced by BUBasicBlockScheduler::finalizeSchedule(), handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), notifyScheduled(), scheduleInputOperandTempMoves(), BUBasicBlockScheduler::scheduleInputOperandTempMoves(), scheduleResultReadTempMoves(), BUBasicBlockScheduler::scheduleResultReadTempMoves(), scheduleRRTempMoves(), BUBasicBlockScheduler::scheduleRRTempMoves(), unscheduleInputOperandTempMoves(), and unscheduleResultReadTempMoves().

selector_

MoveNodeSelector* BasicBlockScheduler::selector_

protected

Definition at line 164 of file BasicBlockScheduler.hh.

Referenced by BUBasicBlockScheduler::handleDDG(), handleDDG(), scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), BUBasicBlockScheduler::scheduleResultReadTempMoves(), scheduleRRMove(), BUBasicBlockScheduler::scheduleRRMove(), and BUBasicBlockScheduler::scheduleRRTempMoves().

softwareBypasser_

SoftwareBypasser* BasicBlockScheduler::softwareBypasser_

protected

The software bypasser to use to bypass registers when possible.

Definition at line 156 of file BasicBlockScheduler.hh.

Referenced by handleDDG(), handleLoopDDG(), scheduleOperation(), and unscheduleAllNodes().

targetMachine_

const TTAMachine::Machine* BasicBlockScheduler::targetMachine_

protected

The target machine we are scheduling the program against.

Definition at line 147 of file BasicBlockScheduler.hh.

Referenced by BUBasicBlockScheduler::handleDDG(), handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), BUBasicBlockScheduler::scheduleMove(), scheduleMove(), BUBasicBlockScheduler::scheduleOperandWrites(), scheduleOperation(), BUBasicBlockScheduler::scheduleOperation(), tryToOptimizeWaw(), BUBasicBlockScheduler::tryToOptimizeWaw(), tryToSwitchInputs(), and BUBasicBlockScheduler::tryToSwitchInputs().

tripCount_

int BasicBlockScheduler::tripCount_

protected

Definition at line 172 of file BasicBlockScheduler.hh.

Referenced by handleDDG(), handleLoopDDG(), BUBasicBlockScheduler::handleLoopDDG(), and scheduleMove().

---

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

• BasicBlockScheduler.hh
• BasicBlockScheduler.cc