CycleLookBackSoftwareBypasser Class Reference

#include <CycleLookBackSoftwareBypasser.hh>

Inheritance diagram for CycleLookBackSoftwareBypasser:

Collaboration diagram for CycleLookBackSoftwareBypasser:

Public Member Functions
	CycleLookBackSoftwareBypasser ()
virtual	~CycleLookBackSoftwareBypasser ()
virtual int	bypass (MoveNodeGroup &candidates, DataDependenceGraph &ddg, ResourceManager &rm, bool bypassTrigger)
virtual void	removeBypass (MoveNodeGroup &candidates, DataDependenceGraph &ddg, ResourceManager &rm)
virtual void	removeBypass (MoveNode &moveNode, DataDependenceGraph &ddg, ResourceManager &rm, bool restoreSource=true)
virtual int	removeDeadResults (MoveNodeGroup &candidates, DataDependenceGraph &ddg, ResourceManager &rm, std::set< std::pair< TTAProgram::Move *, int > > &removedMoves)
void	setSelector (MoveNodeSelector *selector)
virtual void	clearCaches (DataDependenceGraph &ddg, bool removeDeadResults)
Public Member Functions inherited from SoftwareBypasser
	SoftwareBypasser ()
virtual	~SoftwareBypasser ()
int	bypassCount ()
int	deadResultCount ()

Static Public Member Functions
static void	printStats ()

Private Member Functions
int	bypassNode (MoveNode &nodeToBypass, int &lastOperandCycle, DataDependenceGraph &ddg, ResourceManager &rm)

Private Attributes
int	cyclesToLookBack_
	count of cycles before the operand write to look for the producer of the read value
int	cyclesToLookBackNoDRE_
	count of cycles before the operand write to look for the producer of the read value when cannot kill result
bool	killDeadResults_
bool	bypassFromRegs_
bool	bypassToRegs_
std::map< MoveNode *, MoveNode *, MoveNode::Comparator >	storedSources_
	Stores sources and bypassed moves in case they have to be unassigned (case when operands are scheduled and bypassed but result can not be scheduled with such operands.
std::map< MoveNode *, int >	sourceCycles_
std::map< MoveNode *, const TTAMachine::Bus * >	sourceBuses_
std::map< MoveNode *, MoveNode *, MoveNode::Comparator >	removedStoredSources_
DataDependenceGraph::NodeSet	removedNodes_
MoveNodeSelector *	selector_

Static Private Attributes
static int	bypassCount_ = 0
static int	deadResultCount_ = 0
static int	triggerAbortCount_ = 0

Additional Inherited Members
Protected Attributes inherited from SoftwareBypasser
int	bypassCount_
int	deadResultCount_

Detailed Description

A simple implementation of software bypassing that reschedules operand writes as bypassed moves in case the result has been produced in n previous cycles.

Definition at line 52 of file CycleLookBackSoftwareBypasser.hh.

Constructor & Destructor Documentation

CycleLookBackSoftwareBypasser()

CycleLookBackSoftwareBypasser::CycleLookBackSoftwareBypasser

(

)

Constructor.

Definition at line 62 of file CycleLookBackSoftwareBypasser.cc.

                                                             :
    cyclesToLookBack_(5), cyclesToLookBackNoDRE_(1),
    killDeadResults_(true), bypassFromRegs_(true), bypassToRegs_(true), 
    selector_(NULL) {
 
    SchedulerCmdLineOptions* opts = 
        dynamic_cast<SchedulerCmdLineOptions*>(Application::cmdLineOptions());
    if (opts != NULL) {
        if (opts->bypassDistance() > -1) {
            cyclesToLookBack_ = opts->bypassDistance();
        }
        if (opts->noDreBypassDistance() > -1) {
            cyclesToLookBackNoDRE_ = opts->noDreBypassDistance();
        }
        killDeadResults_ = opts->killDeadResults();
    }
}

References SchedulerCmdLineOptions::bypassDistance(), Application::cmdLineOptions(), cyclesToLookBack_, cyclesToLookBackNoDRE_, SchedulerCmdLineOptions::killDeadResults(), killDeadResults_, and SchedulerCmdLineOptions::noDreBypassDistance().

Here is the call graph for this function:

~CycleLookBackSoftwareBypasser()

CycleLookBackSoftwareBypasser::~CycleLookBackSoftwareBypasser ( )

virtual

Empty destructor.

Definition at line 83 of file CycleLookBackSoftwareBypasser.cc.

                                                              {
}

Member Function Documentation

bypass()

int CycleLookBackSoftwareBypasser::bypass ( MoveNodeGroup &  candidates, DataDependenceGraph &  ddg, ResourceManager &  rm, bool  bypassTrigger  )

virtual

Apply software bypassing to as many moves in the given MoveNodeGroup as possible.

This implementation works only if all operand writes have been scheduled. It tries to bypass all the operand write moves.

Parameters

candidates	The moves to which apply software bypassing, if possible.
ddg	The data dependence graph in which the movenodes belong to.
rm	The resource manager which is used to check for resource availability.

Returns

The count of bypassed moves.

Implements SoftwareBypasser.

Definition at line 353 of file CycleLookBackSoftwareBypasser.cc.

                        {
 
    // bypassing disabled with 0
    if (cyclesToLookBack_ <= 0) {
        return 0;
    }
#ifdef MOVE_BYPASSER
    cyclesToLookBack_ = 1;
#endif
    int bypassCounter = 0;
 
    MoveNode* trigger = NULL;
    int lastOperandCycle = 0;
 
    for (int i = 0; i < candidates.nodeCount(); i++) {
        MoveNode& moveNode = candidates.node(i);
 
        // result value or already bypassed - don't bypass this
        if (moveNode.isSourceOperation()) {
            continue;
        }
 
        // find the trigger, will try to bypass it as the last one
        if (moveNode.move().isTriggering()) {
            trigger = &moveNode;
            continue;
        }
 
        // bypass this node.
        int rv = bypassNode(moveNode, lastOperandCycle, ddg, rm);
        if (rv == -1) {
            return -1; // failed, need cleanup
        }  else {
            bypassCounter += rv;
        }
    }
    // Try to bypass triggering move, if possible ok, if not
    // it will be rescheduled at the end after all not bypassed
    // moves are tried to be rescheduled
    bool triggerWasBypassed = false;
    if (trigger != NULL && !trigger->move().isControlFlowMove() &&
        !trigger->isSourceOperation() && bypassTrigger) {
        int rv = bypassNode(*trigger, lastOperandCycle, ddg, rm);
        if (rv == -1) {
            return -1; // failed, need cleanup
        }  else {
            bypassCounter += rv;
            if (rv == 1) {
                triggerWasBypassed = true;
            }
        }
    }
    // at this point the schedule might be broken in case we
    // managed to bypass the trigger and it got pushed above
    // an operand move
 
    // try to reschedule the moves that were not bypassed because
    // earlier operand moves might allow scheduling also the trigger
    // earlier thus shorten the schedule
 
    // this might fix the schedule in case the previous loop
    // managed to push trigger above an operand move
    // if not, the last loop fixes the situation
 
    for (int i = 0; i < candidates.nodeCount(); i++) {
        MoveNode& moveNode = candidates.node(i);
        if (!moveNode.isDestinationOperation() ||
            moveNode.move().isControlFlowMove()) {
            continue;
        }
        // Bypassed moves and bypassed trigger are not rescheduled here
        if (moveNode.isBypass() ||
            (trigger == &moveNode && triggerWasBypassed)) {
            lastOperandCycle =
                std::max(lastOperandCycle, moveNode.cycle());
            continue;
        }
        int oldCycle = moveNode.cycle();
        int earliestCycleDDG = ddg.earliestCycle(moveNode);
 
        if (earliestCycleDDG >= oldCycle) {
            continue;
        }
        rm.unassign(moveNode);
        int earliestCycle = earliestCycleDDG;
 
        if (!moveNode.move().isUnconditional()) {
            earliestCycle = 
                std::max(earliestCycleDDG, moveNode.guardLatency() - 1);
        }
        earliestCycle = rm.earliestCycle(earliestCycle, moveNode);
        if ((oldCycle > earliestCycle && earliestCycle != -1) ||
            (trigger == &moveNode && earliestCycle != -1)){
            try {
                rm.assign(earliestCycle, moveNode);
            } catch (const Exception& e) {
                throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
                    e.errorMessageStack());
            }
        } else {
            try {
                if (!rm.canAssign(oldCycle, moveNode)) {
                    return -1;
                }
                rm.assign(oldCycle, moveNode);
            } catch (const Exception& e) {
                throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
                    e.errorMessageStack());
            }
        }
        lastOperandCycle =
            std::max(lastOperandCycle, moveNode.cycle());
        if (!moveNode.isScheduled()){
            throw InvalidData(
                __FILE__, __LINE__, __func__, "Move assignment failed");
        }
 
    }
    // Traditional test if trigger is not earlier then some operand,
    // could happen due to bypass of trigger
    // todo: this could be optimized by trying to uxchange cycles of
    // trigger and operand in this case.
    if (trigger != NULL) {
        try{
        if (trigger->cycle() < lastOperandCycle) {
            rm.unassign(*trigger);
            int newCycle = rm.earliestCycle(lastOperandCycle, *trigger);
            int latestDDG = ddg.latestCycle(*trigger);
            if (newCycle == -1 || newCycle > latestDDG) {
                triggerAbortCount_++;
                // BBScheduler will call removeBypass
                return -1;
            }
            rm.assign(newCycle, *trigger);
            if (!trigger->isScheduled()){
                throw InvalidData(
                    __FILE__, __LINE__, __func__,"Trigger assignment failed");
            }
        }
        } catch (const Exception& e) {
            throw ModuleRunTimeError(
                __FILE__, __LINE__, __func__,e.errorMessageStack());
        }
    }
    return bypassCounter;
}

References __func__, ResourceManager::assign(), bypassNode(), ResourceManager::canAssign(), MoveNode::cycle(), cyclesToLookBack_, DataDependenceGraph::earliestCycle(), ResourceManager::earliestCycle(), Exception::errorMessageStack(), MoveNode::guardLatency(), MoveNode::isBypass(), TTAProgram::Move::isControlFlowMove(), MoveNode::isDestinationOperation(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), TTAProgram::Move::isTriggering(), TTAProgram::Move::isUnconditional(), DataDependenceGraph::latestCycle(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), triggerAbortCount_, and ResourceManager::unassign().

Here is the call graph for this function:

bypassNode()

int CycleLookBackSoftwareBypasser::bypassNode ( MoveNode &  moveNode, int &  lastOperandCycle, DataDependenceGraph &  ddg, ResourceManager &  rm  )

privatevirtual

Tries to bypass a MoveNode.

Parameters

moveNode	MoveNode to bypass.
lastOperandCycle	in which contains last cycle of operands of the operation
ddg	The data dependence graph in which the movenodes belong to.
rm	The resource manager which is used to check for resource availability.

Returns

-1 if failed and need fixup, 1 is succeeded, 0 if did not bypass.

Implements SoftwareBypasser.

Definition at line 98 of file CycleLookBackSoftwareBypasser.cc.

                         {
 
    int cyclesToLookBack = cyclesToLookBack_;
    if (moveNode.isDestinationVariable() && !bypassToRegs_) {
        return 0;
    }
    
    int originalCycle = moveNode.cycle();
    int latestCycle = originalCycle;
    
    DataDependenceGraph::EdgeSet edges = ddg.inEdges(moveNode);
    DataDependenceGraph::EdgeSet::iterator edgeIter = edges.begin();
    DataDependenceEdge* bypassEdge = NULL;
 
    // find one incoming raw edge. if multiple, cannot bypass.
    while (edgeIter != edges.end()) {
 
        DataDependenceEdge& edge = *(*edgeIter);
        // if the edge is not a real reg/ra raw edge, skip to next edge
        if (edge.edgeReason() != DataDependenceEdge::EDGE_REGISTER ||
            edge.dependenceType() != DataDependenceEdge::DEP_RAW ||
            edge.guardUse() || edge.headPseudo()) {
            edgeIter++;
            continue;
        }
 
        if (bypassEdge == NULL) {
            bypassEdge = &edge;
        } else {
            // cannot bypass if multiple inputs
            return 0;
        }
        edgeIter++;
    }
 
    // if no bypassable edge found, cannot bypass
    if (bypassEdge == NULL || bypassEdge->isBackEdge()) {
        return 0;
    }
 
    MoveNode& source = ddg.tailNode(*bypassEdge);
 
    if (!source.isScheduled()) {
        return 0;
    }
 
    // don't bypass from incoming tempregcopies of immediates
    if (source.isSourceConstant() &&
        source.move().hasAnnotations(
            TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE)) {
        return 0;
    }
 
    // if cannot kill dead result, divide bypass dist by 2
    if (source.isSourceOperation() &&
        moveNode.isDestinationOperation() &&
        cyclesToLookBack != INT_MAX && 
        cyclesToLookBack > cyclesToLookBackNoDRE_ &&
        (ddg.regRawSuccessorCount(source, true) > 1 ||
         ddg.regRawSuccessorCount(source, false) < 
         static_cast<DataDependenceGraph*>(ddg.rootGraph())->
         regRawSuccessorCount(source, false))) {
        cyclesToLookBack = cyclesToLookBackNoDRE_;
    }
 
    // source node is too far for our purposes
    // do not bypass this operand
    if (cyclesToLookBack != INT_MAX &&
        source.cycle() + cyclesToLookBack < moveNode.cycle()) {
        return 0;
    }
 
    if (!ddg.guardsAllowBypass(source, moveNode)) {
        return 0;
    }
 
    // if dest register, only allow input from reg or imm.
    // and limit the read to same as original read
    // in order to not make live ranges longer, limiting schdule
    if (!moveNode.isDestinationOperation()) {
        latestCycle = source.cycle();
    }
    if (!(source.isSourceOperation() || source.isSourceConstant())) {
        if (!bypassFromRegs_) {
            return 0;
        }
        // handle antidependencies from reg-reg moves.
        DataDependenceGraph::NodeSet warSuccs =
            ddg.regWarSuccessors(source);
        for (DataDependenceGraph::NodeSet::iterator i = warSuccs.begin();
             i != warSuccs.end();i++) {
            MoveNode& mn = **i;
            if (mn.isScheduled()) {
                if (mn.cycle() < latestCycle) {
                    latestCycle = std::min(latestCycle, mn.cycle());
                }
            } 
        }
        
        // redundant latest check to prevent loops in ddg.
        for (edgeIter = edges.begin(); edgeIter != edges.end(); edgeIter++) {
            DataDependenceEdge& edge = **edgeIter;
            if (&edge != bypassEdge) {
                MoveNode& tail = ddg.tailNode(edge);
                if (!tail.isScheduled()) {
                    return 0;
                }
                if (edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
                    if (tail.cycle() > latestCycle) {
                        return 0;
                    }
                } else {
                    if (tail.cycle() > latestCycle-1) {
                        return 0;
                    }
                }
            }
        }
    } 
    rm.unassign(moveNode);
    storedSources_.insert(
        std::pair<MoveNode*, MoveNode*>(&moveNode, &source));
    
    // if mergeandkeep fails, undo bypass and return 0
    if (!ddg.mergeAndKeepUser(source, moveNode)) {
        rm.assign(originalCycle, moveNode);
        assert(moveNode.isScheduled());
        storedSources_.erase(&moveNode);
        return 0;
    }
 
    if (moveNode.move().source().isImmediateRegister()) {
        moveNode.move().setSource(
            static_cast<SimpleResourceManager&>(rm).immediateValue(source)->copy());
    }
 
    // then try to assign the bypassed node..
    int ddgCycle = ddg.earliestCycle(moveNode);
    if (!moveNode.move().isUnconditional()) {
        ddgCycle = std::max(ddgCycle, moveNode.guardLatency() - 1);
    }
    if (ddgCycle != INT_MAX) {
#ifdef MOVE_BYPASSER
        ddgCycle = originalCycle;
#endif
        // remove dead results now?
        int sourceCycle = source.cycle();
        bool sourceRemoved = false;
        // Check if machine is forcing disabling DRE,
        // if so disable when first move is bypassed.
        if (killDeadResults_ && 
            source.move().bus().machine()->alwaysWriteResults()) {
            killDeadResults_ = false;
        }
        // disable DRE if ii != 0
        // only kill if dest is op
 
        // >8058 fails
        // >8059 works
        if (killDeadResults_ && !ddg.resultUsed(source)) { // && source.nodeID() > 8058) {
            // if restoring lated
            sourceCycles_[&source] = sourceCycle;
            sourceRemoved = true;
            // results that has no "use" later and are overwritten are
            // dead if there are some other edges we don't do anything
            // Resuls is positively death
            // we need to properly get rid of it
            sourceBuses_[&source] = &source.move().bus();
            rm.unassign(source);
        }
 
        int cycle = rm.earliestCycle(ddgCycle, moveNode);
        if (cycle != -1 && cycle <= latestCycle) {
            rm.assign(cycle, moveNode);
            if (!moveNode.isScheduled()){
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    "Move assignment failed");
            }
            lastOperandCycle = std::max(lastOperandCycle, cycle);
            // only one bypass per operand is possible, no point to
            // test other edges of same moveNode
            if (sourceRemoved) {
                ddg.copyDepsOver(source, true, false);
            }
            bypassCount_++;
            return 1;
        } else {
            // undo only this bypass.
            // allow other moves of same po to be bypassed.
            ddg.unMergeUser(source, moveNode);
            if (!rm.canAssign(originalCycle, moveNode)) {
                // Cannot return to original position. getting problematic.
                // return source to it's position
                if (sourceRemoved) {
                    assert(sourceBuses_[&source] != NULL);
                    source.move().setBus(*sourceBuses_[&source]);
                    assert(rm.canAssign(sourceCycle, source));
                    rm.assign(sourceCycle, source);
                    sourceCycles_.erase(&source);
                    sourceBuses_.erase(&source);
                }
                // Try if we can assign it to some earlier place.
                ddgCycle = ddg.earliestCycle(moveNode);
                if (!moveNode.move().isUnconditional()) {
                    ddgCycle = std::max(ddgCycle, moveNode.guardLatency()-1);
                }
                int ec = rm.earliestCycle(ddgCycle, moveNode);
                if (ec != -1 && ec < originalCycle) {
                    rm.assign(ec, moveNode);
                    return 0;
                } else {
                    // Need to abort bypassing.
                    return -1;
                }
            }
            rm.assign(originalCycle, moveNode);
            assert(moveNode.isScheduled());
            storedSources_.erase(&moveNode);
 
            // return source to it's position
            if (sourceRemoved) {
                assert(sourceBuses_[&source] != NULL);
                source.move().setBus(*sourceBuses_[&source]);
                assert(rm.canAssign(sourceCycle, source));
                rm.assign(sourceCycle, source);
                sourceCycles_.erase(&source);
                sourceBuses_.erase(&source);
            }
            return 0;
        }
    }
    // if node could not be bypassed, we return -1 and let
    // BBScheduler call removeBypass
    return -1;
}

References __func__, TTAMachine::Machine::alwaysWriteResults(), TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE, assert, ResourceManager::assign(), TTAProgram::Move::bus(), bypassCount_, bypassFromRegs_, bypassToRegs_, ResourceManager::canAssign(), DataDependenceGraph::copyDepsOver(), MoveNode::cycle(), cyclesToLookBack_, cyclesToLookBackNoDRE_, DataDependenceEdge::DEP_RAW, DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), DataDependenceGraph::earliestCycle(), ResourceManager::earliestCycle(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), MoveNode::guardLatency(), DataDependenceGraph::guardsAllowBypass(), DataDependenceEdge::guardUse(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), DataDependenceEdge::headPseudo(), BoostGraph< GraphNode, GraphEdge >::inEdges(), DataDependenceEdge::isBackEdge(), MoveNode::isDestinationOperation(), MoveNode::isDestinationVariable(), TTAProgram::Terminal::isImmediateRegister(), MoveNode::isScheduled(), MoveNode::isSourceConstant(), MoveNode::isSourceOperation(), TTAProgram::Move::isUnconditional(), killDeadResults_, TTAMachine::Component::machine(), DataDependenceGraph::mergeAndKeepUser(), MoveNode::move(), DataDependenceGraph::regRawSuccessorCount(), DataDependenceGraph::regWarSuccessors(), DataDependenceGraph::resultUsed(), BoostGraph< GraphNode, GraphEdge >::rootGraph(), TTAProgram::Move::setBus(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), sourceBuses_, sourceCycles_, storedSources_, BoostGraph< GraphNode, GraphEdge >::tailNode(), ResourceManager::unassign(), and DataDependenceGraph::unMergeUser().

Referenced by bypass().

Here is the call graph for this function:

clearCaches()

void CycleLookBackSoftwareBypasser::clearCaches ( DataDependenceGraph &  ddg, bool  removeDeletedResults  )

virtual

Clears the storedSources data structure, when the old values in it are not needed anymore, allowing them to be deleted by the objects who own them.

Delete node from sourceCycles structure, as thesse are not deleted elsewhere.

Implements SoftwareBypasser.

Definition at line 769 of file CycleLookBackSoftwareBypasser.cc.

                               {
    storedSources_.clear();
    sourceBuses_.clear();
    if (removeDeletedResults) {
        // TODO: somebody should also delete these
        for (DataDependenceGraph::NodeSet::iterator i = removedNodes_.begin();
             i != removedNodes_.end(); i++) {
            if (ddg.rootGraph() != &ddg) {
                ddg.rootGraph()->removeNode(**i);
            }
            delete *i;
        }
    }
    removedNodes_.clear();
    removedStoredSources_.clear();
}

References removedNodes_, removedStoredSources_, BoostGraph< GraphNode, GraphEdge >::removeNode(), BoostGraph< GraphNode, GraphEdge >::rootGraph(), sourceBuses_, and storedSources_.

Here is the call graph for this function:

printStats()

void CycleLookBackSoftwareBypasser::printStats ( )

static

Definition at line 788 of file CycleLookBackSoftwareBypasser.cc.

                                          {
    std::cerr << "Bypasser statistics: " << std::endl
              << "\tBypasses: " << bypassCount_ << std::endl
              << "\tKilled results: " << deadResultCount_ << std::endl
              << "\tTrigger too early aborts: " << triggerAbortCount_ << std::endl;
}

References bypassCount_, deadResultCount_, and triggerAbortCount_.

removeBypass() [1/2]

void CycleLookBackSoftwareBypasser::removeBypass ( MoveNode &  moveNode, DataDependenceGraph &  ddg, ResourceManager &  rm, bool  restoreSource = true  )

virtual

Implements SoftwareBypasser.

Definition at line 543 of file CycleLookBackSoftwareBypasser.cc.

                                             {
    
    // bypassing disabled
    if (cyclesToLookBack_ <= 0) {
        return;
    }
    
    if (MapTools::containsKey(storedSources_, &moveNode)) {
        // if node was bypassed, find a original source
        // and restore it, also unassign if bypass was
        // assigned
        MoveNode* tempSource =
            MapTools::valueForKey<MoveNode*>(storedSources_, &moveNode);
        assert(tempSource != NULL);
        storedSources_.erase(&moveNode);
        // if it was bypass and was scheduled we
        // need to unassign and restore, should allways be a case
        if (moveNode.isScheduled()) {
            rm.unassign(moveNode);
        }
 
        // if we unassigned the source of the bypass, restore it.
        if (!tempSource->isScheduled()) {
            std::map<MoveNode*, int>::iterator cycleIter = 
                sourceCycles_.find(tempSource);
            if (cycleIter != sourceCycles_.end()) {
                if (restoreSource) {
                    assert(sourceBuses_[tempSource] != NULL);
                    tempSource->move().setBus(*sourceBuses_[tempSource]);
                    assert(rm.canAssign(cycleIter->second, *tempSource));
                    rm.assign(cycleIter->second, *tempSource); // fails here. somebody else uses the bus?
                }
                sourceCycles_.erase(cycleIter);
                sourceBuses_.erase(tempSource);
            }
        }
        ddg.unMergeUser(*tempSource, moveNode);
        bypassCount_--;
    }
    // this is only for afterwards cleanup.
    if (MapTools::containsKey(removedStoredSources_, &moveNode)) {
        MoveNode* tempSource =
            MapTools::valueForKey<MoveNode*>(removedStoredSources_, &moveNode);
        assert(tempSource != NULL);
        removedStoredSources_.erase(&moveNode);
 
        if (moveNode.isScheduled()) {
            rm.unassign(moveNode);
        }
        ddg.unMergeUser(*tempSource, moveNode);
    }
}

References assert, ResourceManager::assign(), bypassCount_, ResourceManager::canAssign(), MapTools::containsKey(), cyclesToLookBack_, MoveNode::isScheduled(), MapTools::keyForValue(), MoveNode::move(), removedStoredSources_, TTAProgram::Move::setBus(), sourceBuses_, sourceCycles_, storedSources_, ResourceManager::unassign(), and DataDependenceGraph::unMergeUser().

Here is the call graph for this function:

removeBypass() [2/2]

void CycleLookBackSoftwareBypasser::removeBypass ( MoveNodeGroup &  candidates, DataDependenceGraph &  ddg, ResourceManager &  rm  )

virtual

Remove software bypassing from all moves in the given MoveNodeGroup if possible.

Parameters

candidates	The moves from which to remove software bypassing, if possible.
ddg	The data dependence grap in which the movenodes belong to.
rm	The resource manager which is used to check for resource availability.

Implements SoftwareBypasser.

Definition at line 515 of file CycleLookBackSoftwareBypasser.cc.

                         {
 
    // bypassing disabled
    if (cyclesToLookBack_ <= 0) {
        return;
    }
 
    // Some of operand bypassing attempts failed
    // Unschedule all operands, unassign them also since in BBSched
    // this is followed by another attempt to schedule operands
 
    for (int i = 0; i < candidates.nodeCount(); i++) {
        MoveNode& moveNode = candidates.node(i);
        if (moveNode.isScheduled()) {
            rm.unassign(moveNode);
        }
    }
 
    for (int k = 0; k < candidates.nodeCount(); k++) {
        MoveNode& moveNode = candidates.node(k);
        removeBypass(moveNode, ddg, rm);
    }
}

References cyclesToLookBack_, MoveNode::isScheduled(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), removeBypass(), and ResourceManager::unassign().

Referenced by removeBypass().

Here is the call graph for this function:

removeDeadResults()

int CycleLookBackSoftwareBypasser::removeDeadResults ( MoveNodeGroup &  candidates, DataDependenceGraph &  ddg, ResourceManager &  rm, std::set< std::pair< TTAProgram::Move *, int > > &  removedMoves  )

virtual

Remove dead result moves for each bypassed move of given MoveNodeGroup if possible. That is, no other result reads of result exists. This assumes that result moves in MoveNodeGroup are also scheduled.

Parameters

candidates	The moves for which remove dead result writes
ddg	The data dependence grap in which the movenodes belong to.
rm	The resource manager which is used to check for resource availability.
removedMoves	The dead result eliminated moves and their original cycles, to allow rescheduling of moves that were previously resource (RF write port usually) constrained by the removed moves.

Returns

number of dead results killed

Implements SoftwareBypasser.

Definition at line 600 of file CycleLookBackSoftwareBypasser.cc.

                                                          {
 
    for (int i = 0; i < candidates.nodeCount(); i++) {
        // For now, this version is called after operands AND results
        // were scheduled
        if (!candidates.node(i).isScheduled()) {
            return 0;
        }
    }
 
    // For each of bypassed moves, look for its original source and
    // if that one has no more outgoing RAW edges and will be
    // overwritten in same basic block (WAW edge) remove it
 
    int resultsRemoved = 0;
    for (int i = 0; i < candidates.nodeCount(); i++) {
        MoveNode& moveNode = candidates.node(i);
        // Results in candidates are freshly scheduled so they have no
        // bypasses so far
        if (!MapTools::containsKey(storedSources_, &moveNode)) {
            // In case the result was already removed by other move from same
            // candidates set (both operands were bypassed from same result
            // move) we continue
            continue;
        }
 
        // the original result move for the bypassed move
        MoveNode& resultMove = 
            *MapTools::valueForKey<MoveNode*>(storedSources_, &moveNode);
 
        // if killed this one, finish the kill
 
        // try to get the original cycle of the result move
        std::map<MoveNode*, int>::iterator srcIter = 
            sourceCycles_.find(&resultMove);
        if (srcIter != sourceCycles_.end()) {
 
            // we lose edges so our notifyScheduled does not notify
            // some antidependencies, store them for notification.
            DataDependenceGraph::NodeSet successors =
                ddg.successors(resultMove);
 
            successors.erase(&resultMove); // if WaW to itself, remove it.
 
            ddg.dropNode(resultMove);
            removedNodes_.insert(&resultMove);
 
            // remove dead result also from map of sources and bypassed
            // moves, it should not by tried to get removed second time
            // by some other bypassed move from same candidate set
            for (std::map<MoveNode*, MoveNode*, MoveNode::Comparator>::
                     iterator j = storedSources_.begin(); 
                 j != storedSources_.end();) {
                if (j->second == &resultMove) {
                    removedStoredSources_[j->first] = &resultMove;
                    storedSources_.erase(j++);
                } else {
                    j++;
                }
            }
 
            removedMoves.insert(
                std::make_pair(&resultMove.move(), (*srcIter).second));
 
            sourceCycles_.erase(srcIter);
            resultsRemoved++;
            deadResultCount_++;
        
            // we lost edges so our notifyScheduled does not notify
            // some antidependencies. notify them.
            if (selector_ != NULL) {
                for (DataDependenceGraph::NodeSet::iterator iter =
                         successors.begin();
                     iter != successors.end(); iter++) {
                    // don't notify other dead results
                    if (sourceCycles_.find(*iter) == sourceCycles_.end()) {
                        selector_->mightBeReady(**iter);
                    }
                }
            }
        } else {
            // we might have some orhpan nodes because some antideps have moved
            // from user node to source node,
            // so make sure notify the scheduler about them.
            if (ddg.hasNode(resultMove)) {
                DataDependenceGraph::NodeSet successors =
                    ddg.regWawSuccessors(resultMove);
                if (selector_ != NULL) {
                    for (DataDependenceGraph::NodeSet::iterator iter =
                             successors.begin();
                         iter != successors.end(); iter++) {
                        // don't notify other dead results
                        if (sourceCycles_.find(*iter) == sourceCycles_.end()) {
                            selector_->mightBeReady(**iter);
                        }
                    }
                }
            }
        }
 
        // also remove dummy move to itself moves, as the bypassed move.
        if (moveNode.move().source().equals(
                moveNode.move().destination())) {
 
            // we lost edges so our notifyScheduled does not notify
            // some antidependencies. store them for notification.
            DataDependenceGraph::NodeSet successors =
                ddg.successors(moveNode);
            
            successors.erase(&moveNode); // if WaW to itself, rremove it.
 
            rm.unassign(moveNode);
 
            // this may lead to extra raw edges.
            static_cast<DataDependenceGraph*>(ddg.rootGraph())->
                copyDepsOver(moveNode, true, true);
 
            ddg.dropNode(moveNode);
            removedNodes_.insert(&moveNode);
 
            // we lost edges so our notifyScheduled does not notify
            // some antidependencies. notify them.
            if (selector_ != NULL) {
                for (DataDependenceGraph::NodeSet::iterator iter =
                         successors.begin();
                     iter != successors.end(); iter++) {
                    // don't notify other dead results
                    if (sourceCycles_.find(*iter) == sourceCycles_.end()) {
                        selector_->mightBeReady(**iter);
                    }
                }
            }
        }
    }
 
 
    assert(sourceCycles_.empty());
 
    return resultsRemoved;
}

References assert, MapTools::containsKey(), deadResultCount_, TTAProgram::Move::destination(), BoostGraph< GraphNode, GraphEdge >::dropNode(), TTAProgram::Terminal::equals(), BoostGraph< GraphNode, GraphEdge >::hasNode(), MoveNode::isScheduled(), MapTools::keyForValue(), MoveNodeSelector::mightBeReady(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), DataDependenceGraph::regWawSuccessors(), removedNodes_, removedStoredSources_, BoostGraph< GraphNode, GraphEdge >::rootGraph(), selector_, TTAProgram::Move::source(), sourceCycles_, storedSources_, BoostGraph< GraphNode, GraphEdge >::successors(), and ResourceManager::unassign().

Here is the call graph for this function:

setSelector()

void CycleLookBackSoftwareBypasser::setSelector ( MoveNodeSelector *  selector )

virtual

Reimplemented from SoftwareBypasser.

Definition at line 756 of file CycleLookBackSoftwareBypasser.cc.

                                                                     {
    selector_ = selector;
}

References selector_.

Member Data Documentation

bypassCount_

int CycleLookBackSoftwareBypasser::bypassCount_ = 0

staticprivate

Definition at line 125 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode(), printStats(), and removeBypass().

bypassFromRegs_

bool CycleLookBackSoftwareBypasser::bypassFromRegs_

private

Definition at line 96 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode().

bypassToRegs_

bool CycleLookBackSoftwareBypasser::bypassToRegs_

private

Definition at line 99 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode().

cyclesToLookBack_

int CycleLookBackSoftwareBypasser::cyclesToLookBack_

private

count of cycles before the operand write to look for the producer of the read value

Definition at line 86 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypass(), bypassNode(), CycleLookBackSoftwareBypasser(), removeBypass(), and removeBypass().

cyclesToLookBackNoDRE_

int CycleLookBackSoftwareBypasser::cyclesToLookBackNoDRE_

private

count of cycles before the operand write to look for the producer of the read value when cannot kill result

Definition at line 90 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode(), and CycleLookBackSoftwareBypasser().

deadResultCount_

int CycleLookBackSoftwareBypasser::deadResultCount_ = 0

staticprivate

Definition at line 126 of file CycleLookBackSoftwareBypasser.hh.

Referenced by printStats(), and removeDeadResults().

killDeadResults_

bool CycleLookBackSoftwareBypasser::killDeadResults_

private

Definition at line 93 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode(), and CycleLookBackSoftwareBypasser().

removedNodes_

DataDependenceGraph::NodeSet CycleLookBackSoftwareBypasser::removedNodes_

private

Definition at line 121 of file CycleLookBackSoftwareBypasser.hh.

Referenced by clearCaches(), and removeDeadResults().

removedStoredSources_

std::map<MoveNode*, MoveNode*, MoveNode::Comparator> CycleLookBackSoftwareBypasser::removedStoredSources_

private

Definition at line 117 of file CycleLookBackSoftwareBypasser.hh.

Referenced by clearCaches(), removeBypass(), and removeDeadResults().

selector_

MoveNodeSelector* CycleLookBackSoftwareBypasser::selector_

private

Definition at line 123 of file CycleLookBackSoftwareBypasser.hh.

Referenced by removeDeadResults(), and setSelector().

sourceBuses_

std::map<MoveNode*, const TTAMachine::Bus*> CycleLookBackSoftwareBypasser::sourceBuses_

private

Definition at line 115 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode(), clearCaches(), and removeBypass().

sourceCycles_

std::map<MoveNode*, int> CycleLookBackSoftwareBypasser::sourceCycles_

private

Definition at line 114 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode(), removeBypass(), and removeDeadResults().

storedSources_

std::map<MoveNode*, MoveNode*, MoveNode::Comparator> CycleLookBackSoftwareBypasser::storedSources_

private

Stores sources and bypassed moves in case they have to be unassigned (case when operands are scheduled and bypassed but result can not be scheduled with such operands.

Definition at line 111 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypassNode(), clearCaches(), removeBypass(), and removeDeadResults().

triggerAbortCount_

int CycleLookBackSoftwareBypasser::triggerAbortCount_ = 0

staticprivate

Definition at line 127 of file CycleLookBackSoftwareBypasser.hh.

Referenced by bypass(), and printStats().

---

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

• CycleLookBackSoftwareBypasser.hh
• CycleLookBackSoftwareBypasser.cc