#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) {}

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_