BFScheduleBU Class Reference

#include <BFScheduleBU.hh>

Inheritance diagram for BFScheduleBU:

Collaboration diagram for BFScheduleBU:

Public Member Functions
	BFScheduleBU (BF2Scheduler &sched, MoveNode &mn, int lc, bool allowEarlyBypass, bool allowLateBypass, bool allowEarlySharing)
virtual bool	operator() ()
void	undoOnlyMe ()
Public Member Functions inherited from BFScheduleMove
	BFScheduleMove (BF2Scheduler &sched, MoveNode &mn)
Public Member Functions inherited from BFOptimization
	BFOptimization (BF2Scheduler &sched)
virtual bool	isFinishFront ()
virtual void	mightBeReady (MoveNode &mn)
Public Member Functions inherited from Reversible
virtual void	undo ()
virtual	~Reversible ()
void	deleteChildren (std::stack< Reversible * > &children)
int	id ()
	Reversible ()

Private Attributes
int	lc_
bool	allowEarlyBypass_
bool	allowLateBypass_
bool	allowEarlySharing_
bool	bypasserScheduled_
bool	createdCopy_

Additional Inherited Members
Static Public Member Functions inherited from BFOptimization
static void	clearPrologMoves ()
static MoveNode *	getSisterTrigger (const MoveNode &mn, const TTAMachine::Machine &mach)
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)
Protected Attributes inherited from BFScheduleMove
MoveNode &	mn_
bool	createdPrologMove_
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 45 of file BFScheduleBU.hh.

Constructor & Destructor Documentation

BFScheduleBU()

BFScheduleBU::BFScheduleBU ( BF2Scheduler &  sched, MoveNode &  mn, int  lc, bool  allowEarlyBypass, bool  allowLateBypass, bool  allowEarlySharing  )

inline

Definition at line 48 of file BFScheduleBU.hh.

                                                                         :
        BFScheduleMove(sched, mn), lc_(lc),
        allowEarlyBypass_(allowEarlyBypass),
        allowLateBypass_(allowLateBypass),
        allowEarlySharing_(allowEarlySharing),
        bypasserScheduled_(false),
        createdCopy_(false) {}

Member Function Documentation

operator()()

bool BFScheduleBU::operator() ( )

virtual

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

Another op may not come between these, so if this does not work, try without this

Implements Reversible.

Definition at line 66 of file BFScheduleBU.cc.

                         {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\tPerforming BFSchduleBU for: " << mn_.toString() <<
        " lc limit: " << lc_ << std::endl;
#endif
    assert(!mn_.isScheduled());
    if (&mn_.move().bus() != &UniversalMachine::instance().universalBus()) {
        mn_.move().setBus(UniversalMachine::instance().universalBus());
    }
    // TODO: what about constants!
 
    if (mn_.isDestinationOperation() && mn_.isSourceVariable() &&
        allowEarlySharing_) {
    /* this does not yet work, leads to schduler deadlock.
       so commented out.
    if (BF2ScheduleFront::getSisterTrigger(mn_, targetMachine()) == &mn_) {
        ProgramOperationPtr poPtr = mn_.destinationOperationPtr();
        for (int i = 0; i < poPtr->inputMoveCount(); i++) {
        MoveNode& operand = poPtr->inputMove(i);
        if (&operand != &mn_) {
            if (!operand.isScheduled() && !sched_.isDeadResult(operand)) {
 
            BFShareOperands* shareOpers = new BFShareOperands(sched_, operand, lc_);
            if ((*shareOpers)()) {
                //            if (shareOpers->removedNode()) {
                //                return true;
                //            }
                preChildren_.push(shareOpers);
            } else {
                delete shareOpers;
            }
            }
 
        }
        }
    }
    */
        /** Another op may not come between these, so if this does
            not work, try without this */
        BFShareOperands* shareOpers = new BFShareOperands(sched_, mn_, lc_);
        runPreChild(shareOpers);
    }
 
    if (mn_.isSourceVariable()) {
        bool forceBypass = BF2Scheduler::isSourceUniversalReg(mn_);
        if (forceBypass && !allowEarlyBypass_) {
            return false;
        }
        if (allowEarlyBypass_) {
            BFEarlyBypasser* ebp = new BFEarlyBypasser(sched_, mn_);
            if (!runPreChild(ebp)) {
                if (forceBypass) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                    std::cerr << "\t\tForced bypass failed" << std::endl;
                    ddg().writeToDotFile("forced_bypass_fail.dot");
#endif
                    return false;
                }
            }
            if (mn_.isScheduled()) {
                bypasserScheduled_ = true;
                return true;
            }
        }
    }
 
    if (mn_.isDestinationVariable() && allowLateBypass_) {
        BFLateBypasses* lbp = new BFLateBypasses(sched_, mn_, lc_);
        if (runPreChild(lbp)) {
            if (lbp->removedSource()) {
                return true;
            } else {
                // late bypass without DRE .. we may want to do TD instead?
                int prefCycle = BF2ScheduleFront::prefResultCycle(mn_);
                if (prefCycle != INT_MAX) {
                    BFScheduleTD* td =
                        new BFScheduleTD(sched_, mn_, prefCycle, false);
                    if (runPostChild(td)) {
                        return true;
                    }
                }
            }
        }
    }
 
    BFRegCopy* regCopy = NULL;
    BFRegCopy* regCopyBefore = NULL;
    BFRegCopy* regCopyAfter = NULL;
    if (!canBeScheduled(mn_)) {
 
        // can this be solved by dropping guard?
        if (!runPreChild(new BFTryRemoveGuard(sched_, mn_))) {
 
            // no. need to add a regcopy.
            if (mn_.isSourceOperation()) {
                regCopy = regCopyAfter = new BFRegCopyAfter(sched_,mn_, lc_);
            } else {
                // check that we have copy op with suitable connectivity.
                auto copyFUs =
                    MachineConnectivityCheck::copyOpFUs(targetMachine(), mn_);
                if (!copyFUs.empty()) {
                    regCopy = regCopyBefore =
                        new BFCopyRegWithOp(sched_, mn_, lc_, copyFUs);
                } else { // source not op, dest not reg(is op)
                    BFRenameSource* renSrc =
                        new BFRenameSource(sched_, mn_, lc_, lc_);
                    if (runPreChild(renSrc)) {
                        auto forbiddenRF =
                            RFReadPortCountPreventsScheduling(mn_);
                        if (forbiddenRF) {
                            renSrc->undo();
                            preChildren_.pop();
                            forbiddenRF =
                                RFReadPortCountPreventsScheduling(mn_);
                            regCopy = regCopyBefore =
                                new BFRegCopyBefore(sched_, mn_, lc_, forbiddenRF);
                        }
                    } else {
                        // could not use renaming to get rid of regcopy.
                        auto forbiddenRF =
                            RFReadPortCountPreventsScheduling(mn_);
                        regCopy = regCopyBefore =
                            new BFRegCopyBefore(sched_, mn_, lc_,forbiddenRF);
                    }
                }
            }
            if (regCopy && !runPreChild(regCopy)) {
                undoAndRemovePreChildren();
                return false;
            }
        }
    }
    // ignore unsched successors
    int ddglc = std::min(lc_,ddg().latestCycle(mn_, ii(), false, true));
    int ddgec = ddg().earliestCycle(mn_, ii(), false, false);
    int rmlc = rmLC(ddglc, mn_);
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\t\tddg lc: " << ddglc << std::endl;
    std::cerr << "\t\tddg ec: " << ddgec << std::endl;
#endif
 
    int latestIfRenamed =
    std::min(lc_,
         ddg().latestCycle(mn_, ii(), true, false));
//    ddgReplyLimit = std::min(latestIfRenamed+3, ddgReplyLimit);
    if (latestIfRenamed > ddglc && !mn_.move().isControlFlowMove()) {
        latestIfRenamed = rmLC(latestIfRenamed, mn_);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\t\tRenaming could benefit move: " << mn_.toString() <<
            " lc: " << ddglc << " renamed lc: " << latestIfRenamed
                  << std::endl;
#endif
        BFOptimization* adepPush = new BFPushAntidepsDown(
            sched_, mn_, ddglc, latestIfRenamed);
        if (runPreChild(adepPush)) {
            ddglc = std::min(
                lc_, ddg().latestCycle(mn_, ii(), false, false));
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\t\tPushed antidep dests down, new lc: "
                      << ddglc << std::endl;
#endif
 
            latestIfRenamed = std::min(lc_,
                                       ddg().latestCycle(
                                           mn_, ii(), true, false));
            latestIfRenamed = rmLC(latestIfRenamed, mn_);
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        } else {
 
            std::cerr << "\t\tCould not push antidep dests down" << std::endl;
#endif
        }
        rmlc = rmLC(ddglc, mn_);
 
        if (latestIfRenamed > ddglc &&
            !mn_.move().isControlFlowMove() &&
            mn_.isSourceVariable()) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "Antideps still limit scheduling of: "
                      << mn_.toString() << " even after pushing? them down!"
                      << std::endl;
#endif
            BFOptimization* renameSrc =
                new BFRenameSource(sched_, mn_, ddglc, latestIfRenamed);
            if (runPreChild(renameSrc)) {
                int renamedDDGLC =
                    std::min(
                        lc_, ddg().latestCycle(mn_, ii(), false, false));
 
                int renamedRMLC = rmLC(renamedDDGLC, mn_);
                if (renamedRMLC <= rmlc) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                    std::cerr << "\t\tRenaming did not help rmlc, undoing"
                              << std::endl;
#endif
                    preChildren_.pop();
                    renameSrc->undo();
                } else {
                    ddglc = renamedDDGLC;
                    rmlc = renamedRMLC;
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "\t\tRenamed Source Reg, new lc: "
                          << ddglc << std::endl;
#endif
                }
            }
        }
    }
 
    if ((ddglc < ddgec || rmlc < ddgec) && ddglc >=0 && ii()) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\t\tPushing up deps could benefit move: "
                  << mn_.toString() << " lc: " << ddglc
                  << " ec: " << ddgec << std::endl;
#endif
        if (runPreChild(new BFPushDepsUp(sched_, mn_, ddglc))) {
            ddgec = ddg().earliestCycle(mn_, ii(), false, false);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "pushed antidep something up, ec now: "
                      << ddgec << std::endl;
#endif
        }
    }
 
 
    if (mn_.move().destination().isGPR() &&
        mn_.move().destination().registerFile().width() == 1) {
        int latestNoGuard =
            std::min(lc_,
                     ddg().latestCycle(mn_, ii(), false, false, true));
        if (latestNoGuard > ddglc) {
            BFOptimization* removeGuardsFromSuccs =
                new BFRemoveGuardsFromSuccs(sched_, mn_, ddglc,latestNoGuard);
            if (runPreChild(removeGuardsFromSuccs)) {
                ddglc = std::min(lc_,
                                 ddg().latestCycle(mn_, ii(), false, false));
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "\t\tRemoved guards from dests, new lc: "
                          << ddglc << std::endl;
#endif
            } else {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "\t\tCould not remove guards from dests"
                          << std::endl;
#endif
            }
        }
    }
 
    rmlc = rmLC(ddglc, mn_);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\t\tbfschdbu: rmlc: " << rmlc << std::endl;
#endif
 
    if (rmlc < ddgec && ii() != 0) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\t\t\tDDG ec " << ddgec << " on loop(II:"
                  << ii() << ") limits scheudling of: " << mn_.toString();
#endif
        if (ddg().earliestCycle(mn_, INT_MAX/2, false, false) < rmlc) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "Limiter is a loop edge" << std::endl;
            std::cerr << "\t\t\t\tddgec was: " << ddgec << " ddglc was: "
                      << ddgec << " rmlc was: " << rmlc << std::endl;
#endif
            BFOptimization* loopDepPush = new BFPushDepsUp(sched_, mn_, rmlc);
            if (runPreChild(loopDepPush)) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "Pushed loop deps up." << std::endl;
#endif
                ddglc = std::min(lc_,ddg().latestCycle(mn_, ii(), false, false));
                ddgec = ddg().earliestCycle(mn_, ii(), false, false);
                rmlc = rmLC(ddglc, mn_);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "\t\t\t\tddgec now: " << ddgec << "ddglc now: "
                          << ddgec << "rmlc now: " << rmlc << std::endl;
#endif
            } else {
                //                delete loopDepPush;
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "loop dep psuh failed." << std::endl;
#endif
            }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        } else {
            std::cerr << "Limiter not a loop edge." << std::endl;
#endif
        }
    }
    rmlc = rmLC(ddglc, mn_);
    if (rmlc >= ddgec && rmlc != INT_MAX) {
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\t\tassigning to: " << rmlc << std::endl;
#endif
 
        createdCopy_ = assign(rmlc, mn_);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\t\tAssigned ok:" << mn_.toString()
                  << " bus: " << mn_.move().bus().name() << std::endl;
#endif
        if (regCopyBefore != NULL) {
            MoveNode* regCopy = regCopyBefore->getRegCopy();
            BFScheduleBU* regCopySched =
                new BFScheduleBU(sched_, *regCopy, lc_, false, false, false);
            if (!runPostChild(regCopySched)) {
                undo();
                return false;
            }
        }
 
        BFShareOperandsLate* sol = new BFShareOperandsLate(sched_, mn_);
        runPostChild(sol);
 
#if 0
        if (mn_.move().destination().isFUPort() &&
            mn_.move().destination().isTriggering()) {
            runPostChild(new BFRescheduleResultsClose(
                             sched_, mn_.destinationOperation()));
        }
#endif
        return true;
    } else {
        undoAndRemovePreChildren();
        return false;
    }
}

References allowEarlyBypass_, allowEarlySharing_, allowLateBypass_, assert, BFOptimization::assign(), TTAProgram::Move::bus(), bypasserScheduled_, BFOptimization::canBeScheduled(), MachineConnectivityCheck::copyOpFUs(), createdCopy_, BFOptimization::ddg(), TTAProgram::Move::destination(), MoveNode::destinationOperation(), DataDependenceGraph::earliestCycle(), BFRegCopy::getRegCopy(), BFOptimization::ii(), UniversalMachine::instance(), TTAProgram::Move::isControlFlowMove(), MoveNode::isDestinationOperation(), MoveNode::isDestinationVariable(), TTAProgram::Terminal::isFUPort(), TTAProgram::Terminal::isGPR(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), BF2Scheduler::isSourceUniversalReg(), MoveNode::isSourceVariable(), TTAProgram::Terminal::isTriggering(), lc_, BFScheduleMove::mn_, MoveNode::move(), TTAMachine::Component::name(), Reversible::preChildren_, BF2ScheduleFront::prefResultCycle(), TTAProgram::Terminal::registerFile(), BFLateBypasses::removedSource(), BFOptimization::RFReadPortCountPreventsScheduling(), BFOptimization::rmLC(), Reversible::runPostChild(), Reversible::runPreChild(), BFOptimization::sched_, TTAProgram::Move::setBus(), BFOptimization::targetMachine(), MoveNode::toString(), Reversible::undo(), Reversible::undoAndRemovePreChildren(), UniversalMachine::universalBus(), TTAMachine::BaseRegisterFile::width(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

undoOnlyMe()

void BFScheduleBU::undoOnlyMe ( )

virtual

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

Reimplemented from BFScheduleMove.

Definition at line 397 of file BFScheduleBU.cc.

                         {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "\t\tUndoing BU schedule of: " << mn_.toString() <<std::endl;
#endif
 
    if (!bypasserScheduled_) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\t\t\tunassigning here." << std::endl;
#endif
        if (mn_.isScheduled()) {
            unassign(mn_, createdCopy_);
        }
        if (&mn_.move().bus() !=
            &UniversalMachine::instance().universalBus()) {
            mn_.move().setBus(UniversalMachine::instance().universalBus());
        }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    } else {
        std::cerr << "\t\t\tbypasser scheduled this, no need to undo here"
                  << std::endl;
#endif
    }
}

References TTAProgram::Move::bus(), bypasserScheduled_, createdCopy_, UniversalMachine::instance(), MoveNode::isScheduled(), BFScheduleMove::mn_, MoveNode::move(), TTAProgram::Move::setBus(), MoveNode::toString(), BFOptimization::unassign(), and UniversalMachine::universalBus().

Here is the call graph for this function:

Member Data Documentation

allowEarlyBypass_

bool BFScheduleBU::allowEarlyBypass_

private

Definition at line 62 of file BFScheduleBU.hh.

Referenced by operator()().

allowEarlySharing_

bool BFScheduleBU::allowEarlySharing_

private

Definition at line 64 of file BFScheduleBU.hh.

Referenced by operator()().

allowLateBypass_

bool BFScheduleBU::allowLateBypass_

private

Definition at line 63 of file BFScheduleBU.hh.

Referenced by operator()().

bypasserScheduled_

bool BFScheduleBU::bypasserScheduled_

private

Definition at line 65 of file BFScheduleBU.hh.

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

createdCopy_

bool BFScheduleBU::createdCopy_

private

Definition at line 66 of file BFScheduleBU.hh.

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

lc_

int BFScheduleBU::lc_

private

Definition at line 61 of file BFScheduleBU.hh.

Referenced by operator()().

---

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

• BFScheduleBU.hh
• BFScheduleBU.cc