#include <BF2ScheduleFront.hh>

Inheritance diagram for BF2ScheduleFront:

Collaboration diagram for BF2ScheduleFront:

Public Types
typedef BF2Scheduler::MoveNodeMap	MoveNodeMap

Public Member Functions
	BF2ScheduleFront (BF2Scheduler &sched, MoveNode &mn, int lc)

virtual bool	operator() () override

void	undoOnlyMe () override

MoveNode *	findInducingBypassSource (MoveNode &mn)

void	bypassed (MoveNode &src, MoveNode &dst)

void	undidBypass (MoveNode &, MoveNode &dst)

void	mightBeReady (MoveNode &n) override

void	deletingNode (MoveNode *deletedNode)

void	appendBypassSources (MoveNodeMap &map)

Public Member Functions inherited from BFOptimization
	BFOptimization (BF2Scheduler &sched)

virtual bool	isFinishFront ()

Public Member Functions inherited from Reversible
virtual void	undo ()

virtual	~Reversible ()

void	deleteChildren (std::stack< Reversible * > &children)

int	id ()

	Reversible ()

Static Public Member Functions
static int	prefResultCycle (const MoveNode &mn)

Static Public Member Functions inherited from BFOptimization
static void	clearPrologMoves ()

static MoveNode *	getSisterTrigger (const MoveNode &mn, const TTAMachine::Machine &mach)

Public Attributes
DataDependenceGraph::NodeSet	illegalBypassSources_

DataDependenceGraph::NodeSet	illegalOperandShares_

Protected Member Functions
DataDependenceGraph::NodeSet	allNodesOfSameOperation (MoveNode &mn)

int	scheduleMove (MoveNode &move, BF2Scheduler::SchedulingLimits limits, bool allowEarlyBypass=true, bool allowLateBypass=true, bool allowEarlySharing=true)

bool	scheduleFrontFromMove (MoveNode &mn)

void	requeueOtherMovesOfSameOp (MoveNode &mn)

bool	tryToScheduleMoveOuter (MoveNode &mn, int &latestCycle)

BF2Scheduler::SchedulingLimits	getPreferredLimits (const MoveNode &mn)

MoveNode *	getMoveNodeFromFrontBU ()

void	printFront (const TCEString &prefix)

void	clearSchedulingFront ()

int	latestScheduledOfFrontCycle ()

Protected Member Functions inherited from BFOptimization
DataDependenceGraph &	ddg ()

DataDependenceGraph *	rootDDG ()

const DataDependenceGraph &	ddg () const

DataDependenceGraph *	prologDDG ()

SimpleResourceManager &	rm () const

SimpleResourceManager *	prologRM () const

BUMoveNodeSelector &	selector ()

const TTAMachine::Machine &	targetMachine () const

unsigned int	ii () const

MoveNodeDuplicator &	duplicator () const

virtual bool	assign (int cycle, MoveNode &, const TTAMachine::Bus bus=nullptr, const TTAMachine::FunctionUnit srcFU_=nullptr, const TTAMachine::FunctionUnit dstFU=nullptr, const TTAMachine::Bus prologBus=nullptr, int immWriteCycle=-1, int prologImmWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1, bool ignoreGuardWriteCycle=false)

virtual void	unassign (MoveNode &mn, bool disposePrologCopy=true)

virtual int	rmEC (int cycle, MoveNode &mn, const TTAMachine::Bus bus=nullptr, const TTAMachine::FunctionUnit srcFU=nullptr, const TTAMachine::FunctionUnit dstFU=nullptr, const TTAMachine::Bus prologBus=nullptr, int immWriteCycle=-1, int prologImmWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1)

virtual int	rmLC (int cycle, MoveNode &mn, const TTAMachine::Bus bus=nullptr, const TTAMachine::FunctionUnit srcFU=nullptr, const TTAMachine::FunctionUnit dstFU=nullptr, const TTAMachine::Bus prologBus=nullptr, int immWriteCycle=-1, int prologImmWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1)

virtual bool	canAssign (int cycle, MoveNode &mn, const TTAMachine::Bus bus=nullptr, const TTAMachine::FunctionUnit srcFU=nullptr, const TTAMachine::FunctionUnit dstFU=nullptr, const TTAMachine::Bus prologBus=nullptr, int immWriteCycle=-1, int prologImmWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1, bool ignoreGWN=false)

bool	putAlsoToPrologEpilog (int cycle, MoveNode &mn)

void	setPrologSrcFUAnno (MoveNode &prologMN, MoveNode &loopMN)

void	setPrologDstFUAnno (MoveNode &prologMN, MoveNode &loopMN)

void	setJumpGuard (MoveNode &mn)

void	unsetJumpGuard (MoveNode &mn)

bool	needJumpGuard (const MoveNode &mn, int cycle)

int	jumpGuardAvailableCycle (const MoveNode &mn)

bool	canBeSpeculated (const Operation &op)

bool	canBeSpeculated (const MoveNode &mn)

bool	usePrologMove (const MoveNode &mn)

bool	canBeScheduled (const MoveNode &mn)

const TTAMachine::RegisterFile *	RFReadPortCountPreventsScheduling (const MoveNode &mn)

bool	immCountPreventsScheduling (const MoveNode &mn)

Protected Member Functions inherited from Reversible
bool	runPreChild (Reversible *preChild)

bool	runPostChild (Reversible *preChild)

bool	runChild (std::stack< Reversible * > &children, Reversible *child)

bool	runChild (Reversible *child, bool pre)

void	undoAndRemovePreChildren ()

void	undoAndRemovePostChildren ()

void	undoAndRemoveChildren (std::stack< Reversible * > &children)

Private Types
typedef std::map< MoveNode *, int, MoveNode::Comparator >	PathLengthCache

Private Member Functions
bool	tryRevertEarlierBypass (MoveNode &mn)

MoveNode *	findInducingBypassSourceFromOperation (ProgramOperation &po, const DataDependenceGraph::NodeSet &processedNodes, DataDependenceGraph::NodeSet &queue)

Private Attributes
MoveNodeMap	bypassSources_

DataDependenceGraph::NodeSet	schedulingFront_

DataDependenceGraph::NodeSet	nodesToNotify_

MoveNode &	mn_

int	lc_

PathLengthCache	pathLengthCache_

Additional Inherited Members
Protected Attributes inherited from BFOptimization
BF2Scheduler &	sched_

Protected Attributes inherited from Reversible
std::stack< Reversible * >	preChildren_

std::stack< Reversible * >	postChildren_

Static Protected Attributes inherited from BFOptimization
static std::map< MoveNode , MoveNode , MoveNode::Comparator >	prologMoves_

Detailed Description

Definition at line 50 of file BF2ScheduleFront.hh.

Member Typedef Documentation

◆ MoveNodeMap

typedef BF2Scheduler::MoveNodeMap BF2ScheduleFront::MoveNodeMap

Definition at line 82 of file BF2ScheduleFront.hh.

◆ PathLengthCache

typedef std::map<MoveNode*, int, MoveNode::Comparator> BF2ScheduleFront::PathLengthCache

private

Definition at line 132 of file BF2ScheduleFront.hh.

Constructor & Destructor Documentation

◆ BF2ScheduleFront()

BF2ScheduleFront::BF2ScheduleFront	(	BF2Scheduler &	sched,
		MoveNode &	mn,
		int	lc
	)

inline

Definition at line 53 of file BF2ScheduleFront.hh.

54 :

55 BFOptimization(sched), mn_(mn), lc_(lc) {}

BF2ScheduleFront::mn_

MoveNode & mn_

Definition BF2ScheduleFront.hh:129

BF2ScheduleFront::lc_

int lc_

Definition BF2ScheduleFront.hh:130

BFOptimization

Definition BFOptimization.hh:73

Member Function Documentation

◆ allNodesOfSameOperation()

DataDependenceGraph::NodeSet BF2ScheduleFront::allNodesOfSameOperation ( MoveNode & mn )

protected

Definition at line 514 of file BF2ScheduleFront.cc.

                                                      {
 
    DataDependenceGraph::NodeSet queue;
    DataDependenceGraph::NodeSet nodes;
    queue.insert(&mn);
 
    while (!queue.empty()) {
        MoveNode* mn = *queue.begin();
        nodes.insert(mn);
        queue.erase(mn);
        if (mn->isSourceOperation()) {
            BUMoveNodeSelector::queueOperation(
                mn->sourceOperation(), nodes, queue);
        }
 
        if (mn->isGuardOperation()) {
            BUMoveNodeSelector::queueOperation(
                mn->guardOperation(), nodes, queue);
        }
 
        for (unsigned int i = 0; i < mn->destinationOperationCount(); i++) {
            BUMoveNodeSelector::queueOperation(
                mn->destinationOperation(i), nodes, queue);
        }
 
        if (BF2Scheduler::isSourceUniversalReg(*mn)) {
            if (ddg().hasNode(*mn)) {
                MoveNode* bypassSrc =
                    ddg().onlyRegisterRawSource(*mn, false, false);
                if (bypassSrc != NULL) {
                    if (nodes.find(bypassSrc) == nodes.end()) {
                        queue.insert(bypassSrc);
                    }
                } else {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                    std::cerr << "Warning:Cannot find src for forced bypass. "
                          << " Inst. scheduler may fail/deadlock" <<std::endl;
#endif
                }
            }
        }
 
        if (BF2Scheduler::isDestinationUniversalReg(*mn)) {
            if (ddg().hasNode(*mn)) {
                DataDependenceGraph::NodeSet rrDestinations =
                    ddg().onlyRegisterRawDestinations(*mn, false, false);
                for (auto n : rrDestinations) {
                    if (nodes.find(n) == nodes.end()) {
                        queue.insert(n);
                    }
                }
            }
        }
    }
    return nodes;
}

References BFOptimization::ddg(), MoveNode::destinationOperation(), MoveNode::destinationOperationCount(), MoveNode::guardOperation(), BF2Scheduler::isDestinationUniversalReg(), MoveNode::isGuardOperation(), MoveNode::isSourceOperation(), BF2Scheduler::isSourceUniversalReg(), DataDependenceGraph::onlyRegisterRawDestinations(), DataDependenceGraph::onlyRegisterRawSource(), BUMoveNodeSelector::queueOperation(), and MoveNode::sourceOperation().

Referenced by requeueOtherMovesOfSameOp().

Here is the call graph for this function:

◆ appendBypassSources()

void BF2ScheduleFront::appendBypassSources ( MoveNodeMap & map )

Definition at line 705 of file BF2ScheduleFront.cc.

                                                           {
    AssocTools::append(bypassSources_, map);
}

References AssocTools::append(), and bypassSources_.

Referenced by BF2Scheduler::bypassNodes().

Here is the call graph for this function:

◆ bypassed()

void BF2ScheduleFront::bypassed	(	MoveNode &	src,
		MoveNode &	dst
	)

inline

Definition at line 63 of file BF2ScheduleFront.hh.

                                                {
        bypassSources_[&dst] = &src;
    }

References bypassSources_.

Referenced by BFEarlyBypass::operator()().

◆ clearSchedulingFront()

void BF2ScheduleFront::clearSchedulingFront ( )

protected

Definition at line 595 of file BF2ScheduleFront.cc.

                                            {
    for (auto node : schedulingFront_) {
        node->setIsInFrontier(false);
    }
    schedulingFront_.clear();
}

References schedulingFront_.

Referenced by scheduleFrontFromMove(), and undoOnlyMe().

◆ deletingNode()

void BF2ScheduleFront::deletingNode ( MoveNode * deletedNode )

inline

Definition at line 78 of file BF2ScheduleFront.hh.

                                             {
        nodesToNotify_.erase(deletedNode);
    }

References nodesToNotify_.

Referenced by BF2Scheduler::deletingNode().

◆ findInducingBypassSource()

MoveNode * BF2ScheduleFront::findInducingBypassSource ( MoveNode & mn )

Definition at line 603 of file BF2ScheduleFront.cc.

                                                                 {
    DataDependenceGraph::NodeSet queue;
    DataDependenceGraph::NodeSet processedNodes;
    queue.insert(&mn);
 
    while (!queue.empty()) {
        MoveNode* mn = *queue.begin();
        processedNodes.insert(mn);
        queue.erase(mn);
 
        if (!sched_.isDestinationUniversalReg(*mn)) {
            for (auto i : bypassSources_) {
                if (i.second == mn) {
                    return mn;
                }
            }
        }
 
        if (mn->isSourceOperation()) {
            MoveNode *result =
                findInducingBypassSourceFromOperation(
                    mn->sourceOperation(), processedNodes, queue);
            if (result != NULL) {
                return result;
            }
        }
 
        for (unsigned int i = 0; i < mn->destinationOperationCount(); i++) {
            MoveNode *result =
                findInducingBypassSourceFromOperation(
                    mn->destinationOperation(i), processedNodes, queue);
            if (result != NULL) {
                return result;
            }
        }
    }
    return NULL;
}

References bypassSources_, MoveNode::destinationOperation(), MoveNode::destinationOperationCount(), findInducingBypassSourceFromOperation(), BF2Scheduler::isDestinationUniversalReg(), MoveNode::isSourceOperation(), BFOptimization::sched_, and MoveNode::sourceOperation().

Referenced by tryRevertEarlierBypass().

Here is the call graph for this function:

◆ findInducingBypassSourceFromOperation()

MoveNode * BF2ScheduleFront::findInducingBypassSourceFromOperation	(	ProgramOperation &	po,
		const DataDependenceGraph::NodeSet &	processedNodes,
		DataDependenceGraph::NodeSet &	queue
	)

private

Definition at line 642 of file BF2ScheduleFront.cc.

                                       {
    for (int j = 0; j < po.inputMoveCount(); j++) {
        MoveNode& inputMove = po.inputMove(j);
        // only add if not already added
        if (processedNodes.find(&inputMove) == processedNodes.end()) {
            queue.insert(&inputMove);
        }
    }
 
    for (int j = 0; j < po.outputMoveCount(); j++) {
        MoveNode& outputMove = po.outputMove(j);
        // only add if not already added
        if (processedNodes.find(&outputMove) == processedNodes.end()) {
            if (!sched_.isDestinationUniversalReg(outputMove)) {
                for (auto i : bypassSources_) {
                    if (i.second == &outputMove) {
                        return &outputMove;
                    }
                }
            }
            queue.insert(&outputMove);
        }
    }
    return NULL;
}

References bypassSources_, ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), BF2Scheduler::isDestinationUniversalReg(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), and BFOptimization::sched_.

Referenced by findInducingBypassSource().

Here is the call graph for this function:

◆ getMoveNodeFromFrontBU()

MoveNode * BF2ScheduleFront::getMoveNodeFromFrontBU ( )

protected

Definition at line 339 of file BF2ScheduleFront.cc.

                                                   {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\tGetting moveNode from front" << std::endl;
#endif
    int sd = -2;
    MoveNode* selectedMN = NULL;
    for (auto mn: schedulingFront_) {
 
        if (mn->isScheduled() || sched_.isDeadResult(*mn)) {
            continue;
        }
 
        int cursd;
        auto j = pathLengthCache_.find(mn);
        if (j != pathLengthCache_.end()) {
            cursd = j->second;
        } else {
            cursd = ddg().maxSourceDistance(*mn);
            pathLengthCache_[mn] = cursd;
        }
 
        // weight more last moves of unready ops
        if (mn->isDestinationOperation()) {
            if (mn->isLastUnscheduledMoveOfDstOp()) {
                cursd += 10000;
            }
        }
 
        if (cursd > sd &&
            !sched_.hasUnscheduledSuccessors(*mn)) {
            selectedMN = mn;
            sd = cursd;
        }
    }
 
    if (selectedMN != NULL && !sched_.isPreLoopSharedOperand(*selectedMN)) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\t\tSelected:" << selectedMN->toString() << std::endl;
#endif
        MoveNode* trigger = getSisterTrigger(*selectedMN, targetMachine());
        if (trigger != NULL && !trigger->isScheduled() &&
            !sched_.hasUnscheduledSuccessors(*trigger)) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\t\tReturning trigger instead:"
                      << trigger->toString() << std::endl;
#endif
 
            BFSwapOperands* bfswo = new BFSwapOperands(sched_, *trigger);
            if (runPreChild(bfswo)) {
                return bfswo->switchedMNs().second;
            } else {
                return trigger;
            }
        }
    }
    if (selectedMN != NULL) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\tSelected MN: " << selectedMN->toString() << std::endl;
#endif
    } else {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "Front empty, returning NULL" << std::endl;
#endif
    }
    return selectedMN;
}

References BFOptimization::ddg(), BFOptimization::getSisterTrigger(), BF2Scheduler::hasUnscheduledSuccessors(), BF2Scheduler::isDeadResult(), BF2Scheduler::isPreLoopSharedOperand(), MoveNode::isScheduled(), BoostGraph< GraphNode, GraphEdge >::maxSourceDistance(), pathLengthCache_, Reversible::runPreChild(), BFOptimization::sched_, schedulingFront_, BFSwapOperands::switchedMNs(), BFOptimization::targetMachine(), and MoveNode::toString().

Referenced by operator()(), and scheduleFrontFromMove().

Here is the call graph for this function:

◆ getPreferredLimits()

BF2Scheduler::SchedulingLimits BF2ScheduleFront::getPreferredLimits ( const MoveNode & mn )

protected

Definition at line 441 of file BF2ScheduleFront.cc.

                        {
    BF2Scheduler::SchedulingLimits limits;
    int prefCycle = prefResultCycle(mn);
 
    if (prefCycle != INT_MAX) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "Schedulong TOP-DOWN(TD)" << mn.toString() << std::endl;
        std::cerr << "Setting earl. limit to pref:" << prefCycle << std::endl;
#endif
        limits.earliestCycle = prefCycle;
        limits.direction = BF2Scheduler::TOPDOWN;
    }
    if (mn.move().isControlFlowMove() &&
        getSisterTrigger(mn, targetMachine()) == &mn) {
        prefCycle = lc_- targetMachine().controlUnit()->delaySlots();
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "Control flow move requires exact cycle: "
                  << prefCycle << std::endl;
#endif
        limits.earliestCycle = limits.latestCycle = prefCycle;
        limits.direction = BF2Scheduler::EXACTCYCLE;
    }
    return limits;
}

References TTAMachine::Machine::controlUnit(), TTAMachine::ControlUnit::delaySlots(), BF2Scheduler::SchedulingLimits::direction, BF2Scheduler::SchedulingLimits::earliestCycle, BF2Scheduler::EXACTCYCLE, BFOptimization::getSisterTrigger(), TTAProgram::Move::isControlFlowMove(), BF2Scheduler::SchedulingLimits::latestCycle, lc_, MoveNode::move(), prefResultCycle(), BFOptimization::targetMachine(), BF2Scheduler::TOPDOWN, and MoveNode::toString().

Referenced by tryToScheduleMoveOuter().

Here is the call graph for this function:

◆ latestScheduledOfFrontCycle()

int BF2ScheduleFront::latestScheduledOfFrontCycle ( )

protected

Definition at line 327 of file BF2ScheduleFront.cc.

                                                  {
    int lc = -1;
    for (auto mn : schedulingFront_) {
        if (mn->isScheduled() && mn->cycle() > lc) {
            lc = mn->cycle();
        }
    }
    return lc;
}

References schedulingFront_.

Referenced by tryToScheduleMoveOuter().

◆ mightBeReady()

void BF2ScheduleFront::mightBeReady ( MoveNode & n )

overridevirtual

Reimplemented from BFOptimization.

Definition at line 701 of file BF2ScheduleFront.cc.

                                               {
    nodesToNotify_.insert(&n);
}

References nodesToNotify_.

Referenced by BFOptimization::mightBeReady(), and BFRenameLiveRange::notifySelector().

◆ operator()()

bool BF2ScheduleFront::operator() ( )

overridevirtual

This performs the operation. Returns true if success, false if fail.

Implements Reversible.

Definition at line 61 of file BF2ScheduleFront.cc.

                             {
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << std::endl << "Got: " << mn_.toString()
              << " to schedule(1)" << std::endl;
#endif
    requeueOtherMovesOfSameOp(mn_);
    MoveNode* mn2 = getMoveNodeFromFrontBU();
    assert(mn2 != NULL);
 
    bool ok = scheduleFrontFromMove(*mn2);
    // Do not waste memory by keeping it in the stack of performed
    // operations.
    // Not needed anymore. Can calculate again for next front.
    // Consider sharing between different fronts if still too slow.
    pathLengthCache_.clear();
    return ok;
}

References assert, getMoveNodeFromFrontBU(), mn_, pathLengthCache_, requeueOtherMovesOfSameOp(), scheduleFrontFromMove(), and MoveNode::toString().

Here is the call graph for this function:

◆ prefResultCycle()

int BF2ScheduleFront::prefResultCycle ( const MoveNode & mn )

static

Definition at line 406 of file BF2ScheduleFront.cc.

                                                        {
    int prefCycle = INT_MAX;
    if (mn.isSourceOperation()) {
        if (!mn.isDestinationOperation()) {
            const ProgramOperation& sop = mn.sourceOperation();
            for (int i = 0; i < sop.outputMoveCount(); i++) {
                const MoveNode& outNode = sop.outputMove(i);
                if (!outNode.isScheduled()) {
                    continue;
                }
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "\t\tOut node: " << outNode.toString()
                          << " is scheduled!" << std::endl;
#endif
                const TTAMachine::HWOperation& hwop =
                    *sop.hwopFromOutMove(outNode);
                // find the OSAL id of the operand of the output being tested
                const int outNodeOutputIndex =
                    sop.outputIndexOfMove(outNode);
                int onLatency = hwop.latency(outNodeOutputIndex);
                int latestTrigger = outNode.cycle() - onLatency;
                const int myOutIndex = mn.move().source().operationIndex();
                int myLatency = hwop.latency(myOutIndex);
                int myPreferredCycle = latestTrigger + myLatency;
                if (myPreferredCycle < prefCycle) {
                    prefCycle = myPreferredCycle;
                }
            }
        }
    }
    return prefCycle;
}

References MoveNode::cycle(), ProgramOperation::hwopFromOutMove(), MoveNode::isDestinationOperation(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), TTAMachine::HWOperation::latency(), MoveNode::move(), TTAProgram::Terminal::operationIndex(), ProgramOperation::outputIndexOfMove(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), TTAProgram::Move::source(), MoveNode::sourceOperation(), and MoveNode::toString().

Referenced by getPreferredLimits(), and BFScheduleBU::operator()().

Here is the call graph for this function:

◆ printFront()

void BF2ScheduleFront::printFront ( const TCEString & prefix )

protected

Definition at line 572 of file BF2ScheduleFront.cc.

                                                         {
    for (auto node : schedulingFront_) {
        if (sched_.isDeadResult(*node)) {
            std::cerr << "DEAD ";
        }
        std::cerr << prefix << node->toString() << std::endl;
    }
}

References BF2Scheduler::isDeadResult(), BFOptimization::sched_, and schedulingFront_.

Referenced by scheduleFrontFromMove(), and undoOnlyMe().

Here is the call graph for this function:

◆ requeueOtherMovesOfSameOp()

void BF2ScheduleFront::requeueOtherMovesOfSameOp ( MoveNode & mn )

protected

Definition at line 502 of file BF2ScheduleFront.cc.

                                                             {
    DataDependenceGraph::NodeSet moves =
        allNodesOfSameOperation(mn);
    for (auto mn : moves) {
        if (!mn->isFinalized()) { // && !sched_.isPreLoopSharedOperand(*mn)) {
            mn->setIsInFrontier(true);
            schedulingFront_.insert(mn);
        }
    }
}

References allNodesOfSameOperation(), MoveNode::isFinalized(), schedulingFront_, and MoveNode::setIsInFrontier().

Referenced by operator()(), and scheduleFrontFromMove().

Here is the call graph for this function:

◆ scheduleFrontFromMove()

bool BF2ScheduleFront::scheduleFrontFromMove ( MoveNode & mn )

protected

Definition at line 81 of file BF2ScheduleFront.cc.

                                                         {
    MoveNode* mn2 = &mn;
    int latest = lc_;
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "ScheduleFrontFromMove called: " <<mn.toString()<< std::endl;
#endif
    while (mn2 != NULL) {
        if (mn2->move().isControlFlowMove()) {
            latest = std::min(
                latest,
                lc_- targetMachine().controlUnit()->delaySlots());
        }
 
        if (!tryToScheduleMoveOuter(*mn2, latest)) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "TryToScheduleMoveOuter " << mn2->toString() <<
        " failed!, latest now" << latest << std::endl;
#endif
            undo();
            int smallestRMCycle = rm().smallestCycle();
            if (smallestRMCycle == INT_MAX) {
                smallestRMCycle = lc_;
            }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "Latest after outer fail: " << latest << std::endl;
            std::cerr << "smallest rm cycle: " << smallestRMCycle <<
                " max latency+1: " << targetMachine().maximumLatency()+1
                      << std::endl;
#endif
            if (latest < 0 || latest <
                (smallestRMCycle - (targetMachine().maximumLatency()+1))) {
                if (Application::verboseLevel() > 1 ||
                    rm().initiationInterval() == 0) {
                    std::cerr << "Retry to too early cycle. cannot schedule: "
                              << mn2->toString()
                              << std::endl;
                    ddg().writeToDotFile("fail.dot");
                }
                return false;
            } else {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "OK or retry at earlier cycle.." << std::endl;
#endif
        }
        }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "TryToScheduleMoveOuter ok: " << mn2->toString() <<std::endl;
#endif
        clearSchedulingFront();
        requeueOtherMovesOfSameOp(mn);
        mn2 = getMoveNodeFromFrontBU();
    }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "Schedulingfront scheduled ok!: " << this << std::endl;
    printFront("\t");
#endif
    for (auto i : schedulingFront_) {
        if (!i->isScheduled()) {
            if (!sched_.isDeadResult(*i) &&
                !sched_.isPreLoopSharedOperand(*i)) {
                std::cerr << "Front Has unscheduled move: "
                          << (*i).toString() << std::endl;
                ddg().writeToDotFile("front_unscheduled_move.dot");
                assert(0);
            }
        } else {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tNotifying scheduled: " << (*i).toString()
                      << std::endl;
#endif
            selector().notifyScheduled(*i);
 
        }
    }
 
    for (auto n: nodesToNotify_) {
        if (!sched_.isDeadResult(*n) && !n->isScheduled()) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tMight be ready: " << n->toString() << std::endl;
#endif
            selector().mightBeReady(*n);
        }
    }
    clearSchedulingFront();
    return true;
}

References assert, clearSchedulingFront(), BFOptimization::ddg(), getMoveNodeFromFrontBU(), TTAProgram::Move::isControlFlowMove(), BF2Scheduler::isDeadResult(), BF2Scheduler::isPreLoopSharedOperand(), lc_, TTAMachine::Machine::maximumLatency(), BUMoveNodeSelector::mightBeReady(), MoveNode::move(), nodesToNotify_, BUMoveNodeSelector::notifyScheduled(), printFront(), requeueOtherMovesOfSameOp(), BFOptimization::rm(), BFOptimization::sched_, schedulingFront_, BFOptimization::selector(), SimpleResourceManager::smallestCycle(), BFOptimization::targetMachine(), MoveNode::toString(), tryToScheduleMoveOuter(), Reversible::undo(), Application::verboseLevel(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by operator()().

Here is the call graph for this function:

◆ scheduleMove()

int BF2ScheduleFront::scheduleMove	(	MoveNode &	move,
		BF2Scheduler::SchedulingLimits	limits,
		bool	allowEarlyBypass = `true`,
		bool	allowLateBypass = `true`,
		bool	allowEarlySharing = `true`
	)

protected

Definition at line 468 of file BF2ScheduleFront.cc.

                                                                         {
 
    BFOptimization* sched;
    switch (limits.direction) {
    case BF2Scheduler::BOTTOMUP:
        if (!sched_.isPreLoopSharedOperand(mn)) {
            sched = new BFScheduleBU(
                sched_, mn, limits.latestCycle, allowEarlyBypass,
                allowLateBypass, allowEarlySharing);
            break;
        } else {
            std::cerr << "Is pre loop shared oper, sch to prolog instead: " <<
                mn.toString() << std::endl;
            assert(false);
            break;
        }
    case BF2Scheduler::TOPDOWN:
        sched = new BFScheduleTD(
        sched_, mn, limits.earliestCycle, allowLateBypass);
        break;
    case BF2Scheduler::EXACTCYCLE:
        assert(limits.earliestCycle == limits.latestCycle);
        sched = new BFScheduleExact(
        sched_,mn,limits.earliestCycle);
        break;
    default:
        return -1;
    }
    return runPreChild(sched) ? 1 : -1;
}

References assert, BF2Scheduler::BOTTOMUP, BF2Scheduler::SchedulingLimits::direction, BF2Scheduler::SchedulingLimits::earliestCycle, BF2Scheduler::EXACTCYCLE, BF2Scheduler::isPreLoopSharedOperand(), BF2Scheduler::SchedulingLimits::latestCycle, Reversible::runPreChild(), BFOptimization::sched_, BF2Scheduler::TOPDOWN, and MoveNode::toString().

Referenced by tryToScheduleMoveOuter().

Here is the call graph for this function:

◆ tryRevertEarlierBypass()

bool BF2ScheduleFront::tryRevertEarlierBypass ( MoveNode & mn )

private

Definition at line 671 of file BF2ScheduleFront.cc.

                                                          {
 
    MoveNode* inducingBypass = findInducingBypassSource(mn);
    while (inducingBypass != NULL &&
       sched_.isDestinationUniversalReg(*inducingBypass)) {
        for (auto i : bypassSources_) {
            if (i.second == inducingBypass) {
                inducingBypass = findInducingBypassSource(*(i.first));
                break;
            }
        }
    }
    if (inducingBypass == NULL) {
        return false;
    } else {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\t\tMaking illegal bypas of src: "
                  << inducingBypass->toString() << std::endl;
#endif
        if (illegalBypassSources_.count(inducingBypass)) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\t\tIs already illegal bypass! " << std::endl;
#endif
            return false;
        }
        illegalBypassSources_.insert(inducingBypass);
        return true;
    }
}

References bypassSources_, findInducingBypassSource(), illegalBypassSources_, BF2Scheduler::isDestinationUniversalReg(), BFOptimization::sched_, and MoveNode::toString().

Referenced by tryToScheduleMoveOuter().

Here is the call graph for this function:

◆ tryToScheduleMoveOuter()

bool BF2ScheduleFront::tryToScheduleMoveOuter	(	MoveNode &	mn,
		int &	latestCycle
	)

protected

Definition at line 170 of file BF2ScheduleFront.cc.

                                                                           {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << std::endl << "\tGot: " << mn.toString() << " to schedule(2)"
              << std::endl;
#endif
    while(true) {
        if (sched_.isPreLoopSharedOperand(mn)) {
            assert(prologRM() != NULL);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tShould scheudule pre-opshare to prefix: "
                      << mn.toString() << std::endl;
#endif
            BFOptimization* sbu = new BFDropPreShared(sched_, mn);
            bool ok = runPreChild(sbu);
            if (!ok) {
                int lcFront = latestScheduledOfFrontCycle();
                if (lcFront != -1 && lcFront <= latestCycle) {
                    latestCycle = lcFront -1;
                } else{
                    latestCycle--;
                }
                return false;
            } else {
                return true;
            }
        }
 
        // Kill (result) moves that write to values that are
        // never used(even when not bypassing).
        if (mn.isDestinationVariable()) {
            BFOptimization* dre = new BFDREEarly(sched_, mn);
            if (runPreChild(dre)) {
                return true;
            }
        }
 
        BF2Scheduler::SchedulingLimits limits = getPreferredLimits(mn);
        if (limits.direction == BF2Scheduler::EXACTCYCLE &&
            latestCycle < limits.latestCycle) {
            latestCycle = INT_MIN;
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tlatestCycle later than exact limit. failing."
                      << std::endl;
#endif
            return false;
        }
 
        limits.latestCycle = std::min(limits.latestCycle, latestCycle);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\tFirst all optimizations on" << std::endl;
#endif
        int schedRes = scheduleMove(mn, limits, true, true, true);
        if (schedRes >= 0) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tScheduling of: " << mn.toString() << " ok "
                      << std::endl;
#endif
            return true;
        }
 
        if (limits.direction == BF2Scheduler::TOPDOWN) {
            limits.direction = BF2Scheduler::BOTTOMUP;
            limits.earliestCycle = 0;
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tTOPDOWN failed, trying bottomup" << std::endl;
#endif
            if (scheduleMove(mn, limits) >= 0) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "\ttopdown back to bottomup ok" << std::endl;
#endif
                return true;
            }
        }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\tTrying without early sharing" << std::endl;
#endif
        // disable early sharing;
        if (scheduleMove(mn, limits, true, true, false) >=0) {
            return true;
        }
 
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\tTrying without early BP" << std::endl;
#endif
        // disable early bypass;
        if (scheduleMove(mn, limits, false, true) >=0) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tok without early BP" << std::endl;
#endif
            return true;
        }
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\tTrying without early BP and without early sharing"
                  << std::endl;
#endif
        if (scheduleMove(mn, limits, false, true, false) >= 0) {
            return true;
        }
 
        if (tryRevertEarlierBypass(mn)) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tTrying to Revert earlier bypass.."
                      << std::endl;
#endif
        // do not make cycle go earlier, but forbid some bypass.
            return false;
        }
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\tTrying without late BP" << std::endl;
#endif
        // disable late bypass
        if (scheduleMove(mn, limits, true, false) >=0) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tok without late BP" << std::endl;
#endif
            return true;
        }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\tTrying without any BP" << std::endl;
#endif
        // disable both bypasses
        if (scheduleMove(mn, limits, false, false) >=0) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tok without any BP" << std::endl;
#endif
            return true;
        }
 
        if (mn.destinationOperationCount() > 1) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "forbidding operand share: " << mn.toString()
                      << std::endl;
#endif
            illegalOperandShares_.insert(&mn);
            return true;
        }
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\tScheduleMove failing, need to tr earlier cycle"
                  << std::endl;
#endif
 
        int lcFront = latestScheduledOfFrontCycle();
        if (lcFront != -1 && lcFront <= latestCycle) {
            latestCycle = lcFront -1;
        } else{
            latestCycle--;
        }
        return false;
    }
    std::cerr << "end of schduleMoveOuter, should not be here!" << std::endl;
    return true;
}

References assert, BF2Scheduler::BOTTOMUP, MoveNode::destinationOperationCount(), BF2Scheduler::SchedulingLimits::direction, BF2Scheduler::SchedulingLimits::earliestCycle, BF2Scheduler::EXACTCYCLE, getPreferredLimits(), illegalOperandShares_, MoveNode::isDestinationVariable(), BF2Scheduler::isPreLoopSharedOperand(), BF2Scheduler::SchedulingLimits::latestCycle, latestScheduledOfFrontCycle(), BFOptimization::prologRM(), Reversible::runPreChild(), BFOptimization::sched_, scheduleMove(), BF2Scheduler::TOPDOWN, MoveNode::toString(), and tryRevertEarlierBypass().

Referenced by scheduleFrontFromMove().

Here is the call graph for this function:

◆ undidBypass()

void BF2ScheduleFront::undidBypass	(	MoveNode &	,
		MoveNode &	dst
	)

inline

Definition at line 67 of file BF2ScheduleFront.hh.

                                               {
        bypassSources_.erase(&dst);
    }

References bypassSources_.

Referenced by BFEarlyBypass::undoOnlyMe().

◆ undoOnlyMe()

void BF2ScheduleFront::undoOnlyMe ( )

overridevirtual

Undoes the operations done by this class but not children. This method should be overloaded by most derived classes.

Reimplemented from Reversible.

Definition at line 582 of file BF2ScheduleFront.cc.

                                  {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "should undo front. printing front:" << std::endl;
    printFront("\t");
#endif
    clearSchedulingFront();
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "should have cleared. printing front:" << std::endl;
    printFront("\t");
#endif
}

References clearSchedulingFront(), and printFront().

Here is the call graph for this function:

Member Data Documentation

◆ bypassSources_

MoveNodeMap BF2ScheduleFront::bypassSources_

private

Definition at line 118 of file BF2ScheduleFront.hh.

Referenced by appendBypassSources(), bypassed(), findInducingBypassSource(), findInducingBypassSourceFromOperation(), tryRevertEarlierBypass(), and undidBypass().

◆ illegalBypassSources_

DataDependenceGraph::NodeSet BF2ScheduleFront::illegalBypassSources_

Definition at line 71 of file BF2ScheduleFront.hh.

Referenced by BFEarlyBypasser::operator()(), and tryRevertEarlierBypass().

◆ illegalOperandShares_

DataDependenceGraph::NodeSet BF2ScheduleFront::illegalOperandShares_

Definition at line 72 of file BF2ScheduleFront.hh.

Referenced by BFShareOperands::operator()(), and tryToScheduleMoveOuter().

◆ lc_

int BF2ScheduleFront::lc_

private

Definition at line 130 of file BF2ScheduleFront.hh.

Referenced by getPreferredLimits(), and scheduleFrontFromMove().

◆ mn_

MoveNode& BF2ScheduleFront::mn_

private

Definition at line 129 of file BF2ScheduleFront.hh.

Referenced by operator()().

◆ nodesToNotify_

DataDependenceGraph::NodeSet BF2ScheduleFront::nodesToNotify_

private

Definition at line 127 of file BF2ScheduleFront.hh.

Referenced by deletingNode(), mightBeReady(), and scheduleFrontFromMove().

◆ pathLengthCache_

PathLengthCache BF2ScheduleFront::pathLengthCache_

private

Definition at line 133 of file BF2ScheduleFront.hh.

Referenced by getMoveNodeFromFrontBU(), and operator()().

◆ schedulingFront_

DataDependenceGraph::NodeSet BF2ScheduleFront::schedulingFront_

private

Definition at line 125 of file BF2ScheduleFront.hh.

Referenced by clearSchedulingFront(), getMoveNodeFromFrontBU(), latestScheduledOfFrontCycle(), printFront(), requeueOtherMovesOfSameOp(), and scheduleFrontFromMove().

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

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ MoveNodeMap

◆ PathLengthCache

Constructor & Destructor Documentation

◆ BF2ScheduleFront()

Member Function Documentation

◆ allNodesOfSameOperation()

◆ appendBypassSources()

◆ bypassed()

◆ clearSchedulingFront()

◆ deletingNode()

◆ findInducingBypassSource()

◆ findInducingBypassSourceFromOperation()

◆ getMoveNodeFromFrontBU()

◆ getPreferredLimits()

◆ latestScheduledOfFrontCycle()

◆ mightBeReady()

◆ operator()()

◆ prefResultCycle()

◆ printFront()

◆ requeueOtherMovesOfSameOp()

◆ scheduleFrontFromMove()

◆ scheduleMove()

◆ tryRevertEarlierBypass()

◆ tryToScheduleMoveOuter()

◆ undidBypass()

◆ undoOnlyMe()

Member Data Documentation

◆ bypassSources_

◆ illegalBypassSources_

◆ illegalOperandShares_

◆ lc_

◆ mn_

◆ nodesToNotify_

◆ pathLengthCache_

◆ schedulingFront_