BF2Scheduler Class Reference

#include <BF2Scheduler.hh>

Inheritance diagram for BF2Scheduler:

Collaboration diagram for BF2Scheduler:

Classes
struct	PreLoopShareInfo
struct	SchedulingLimits

Public Types
enum	LoopSchedulingMode { NO_LOOP_SCHEDULER = 0 }
enum	PreLoopOperandEnum { NO_PORT =0 , SHARED =1 , NOT_SHARED =2 , NO_LOOP_INVARIANT =3 }
enum	SchedulingDirection { EITHER =0 , TOPDOWN =1 , BOTTOMUP =2 , EXACTCYCLE =3 }
typedef std::map< MoveNode *, MoveNode *, MoveNode::Comparator >	MoveNodeMap

Public Member Functions
	BF2Scheduler (InterPassData &ipd, RegisterRenamer *renamer)
	BF2Scheduler (InterPassData &ipd, RegisterRenamer *renamer, bool killDeadResults)
	~BF2Scheduler ()
virtual int	handleDDG (DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine, int minCycle=0, bool testOnly=false)
void	scheduleDDG (DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine)
virtual std::string	shortDescription () const override
virtual int	handleLoopDDG (DataDependenceGraph &, SimpleResourceManager &, const TTAMachine::Machine &, int tripCount, SimpleResourceManager *, bool testOnly) override
DataDependenceGraph &	ddg ()
const DataDependenceGraph &	ddg () const
DataDependenceGraph *	prologDDG ()
SimpleResourceManager &	rm ()
SimpleResourceManager *	prologRM ()
BUMoveNodeSelector &	selector ()
MoveNodeDuplicator &	duplicator ()
bool	killDeadResults () const
void	revertBBLiveRangeBookkeepingForDestination (MoveNode *mn)
void	revertBBLiveRangeBookkeepingForSource (MoveNode *mn)
std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator >	possibleTempRegRFs (const MoveNode &mn, bool tempRegAfter, const TTAMachine::RegisterFile *forbiddenRF=nullptr)
DataDependenceEdge *	findBypassEdge (const MoveNode &mn)
void	nodeKilled (MoveNode &mn)
void	nodeResurrected (MoveNode &mn)
void	nodeAndCopyKilled (MoveNode &mn)
const TTAMachine::Machine &	targetMachine () const
bool	isDeadResult (MoveNode &mn) const
TTAMachine::FUPort *	isPreLoopSharedOperand (MoveNode &mn) const
TTAMachine::Unit *	getDstUnit (MoveNode &mn)
bool	isTrigger (const TTAMachine::Unit &unit, MoveNode &mn)
bool	hasUnscheduledSuccessors (MoveNode &mn) const
int	tripCount ()
int	maximumAllowedCycle () const
BF2ScheduleFront *	currentFront ()
TTAProgram::MoveGuard *	jumpGuard ()
MoveNode *	guardWriteNode ()
MoveNode *	jumpNode ()
MoveNode *	loopLimitNode ()
LoopAnalyzer::LoopAnalysisResult *	getLoopAnalysis ()
void	setLoopLimits (LoopAnalyzer::LoopAnalysisResult *llResult)
bool	mustBeTrigger (const MoveNode &mn, const ProgramOperation &po)
std::list< ProgramOperation * >	loopBufOps ()
void	deletingNode (MoveNode *deletedNode)
void	finalizeSchedule ()
void	unschedule ()
MoveNodeMap	bypassNodes ()
RegisterRenamer *	renamer ()
Public Member Functions inherited from DDGPass
	DDGPass (InterPassData &data)
virtual	~DDGPass ()
Public Member Functions inherited from SchedulerPass
	SchedulerPass (InterPassData &data)
virtual	~SchedulerPass ()
InterPassData &	interPassData ()
virtual std::string	longDescription () const

Static Public Member Functions
static bool	isSourceUniversalReg (const MoveNode &mn)
static bool	isDestinationUniversalReg (const MoveNode &mn)

Static Public Attributes
static const int	PROLOG_CYCLE_BIAS = 1000

Protected Member Functions
int	handleLoopDDG (BUMoveNodeSelector &selector, bool allowPreLoopOpshare)

Private Member Functions
bool	findJump ()
int	scheduleFrontFromMove (MoveNode &mn)
MoveNode *	selectMoveToSchedule ()
void	initializeQueues ()
MoveNodeSet	findSiblings (MoveNode &mn)
bool	isRegCopyBefore (MoveNode &mn)
bool	isRegCopyAfter (MoveNode &mn)
bool	pushAntidepDestsDown (MoveNode &mn, int oldLC, int maxLC)
void	undoPushAntideps (MoveNode &aDepSource)
void	eraseFromMoveNodeUseSet (LiveRangeData::MoveNodeUseMapSet &mnuMap, const TCEString &reg, MoveNode *mn)
int	swapToUntrigger (ProgramOperationPtr po, const Operation &op, int operandIndex, MoveNode &trig)
void	revertTopOpt ()
void	countLoopInvariantValueUsages ()
void	allocateFunctionUnits ()
void	reservePreallocatedFUs ()
void	preAllocateFunctionUnits (ProgramOperationPtr po)
PreLoopShareInfo	preAllocateFunctionUnits (ProgramOperationPtr po, const Operation &op, const TTAMachine::HWOperation &hwop, bool onlySharedWithAnother)
PreLoopShareInfo	preAllocateFunctionUnits (ProgramOperationPtr po, const Operation &op, int operandIndex, const TTAMachine::HWOperation &hwop, bool onlySharedWithAnother)
PreLoopShareInfo	preAllocateFunctionUnitsInner (ProgramOperationPtr po, const Operation &op, bool onlySharedWithAnother)
void	unreservePreallocatedFUs ()
void	releasePortForOp (const Operation &op)

Static Private Member Functions
static void	writeDotWithNameAndNodeID (DataDependenceGraph &ddg, const TCEString &namePrefix, const MoveNode &mn)

Private Attributes
BF2ScheduleFront *	currentFront_
std::vector< BFOptimization * >	scheduledStack_
DataDependenceGraph::NodeSet	dreRemovedMoves_
DataDependenceGraph::NodeSet	removedMoves_
MoveNodeMap	operandShareRemovedMoves_
MoveNodeMap	sharedOperands_
DataDependenceGraph::NodeSet	bypassPredecessors_
	Nodes that may become ready due bypass removing antideps.
DataDependenceGraph::NodeSet	pendingMoves_
DataDependenceGraph *	ddg_
DataDependenceGraph *	prologDDG_
SimpleResourceManager *	rm_
SimpleResourceManager *	prologRM_
int	latestCycle_
const TTAMachine::Machine *	targetMachine_
BUMoveNodeSelector *	selector_
LLVMTCECmdLineOptions *	options_
RegisterRenamer *	renamer_
bool	killDeadResults_
int	tripCount_
MoveNode *	jumpNode_
MoveNode *	jumpGuardWrite_
LoopAnalyzer::LoopAnalysisResult *	llResult_
MoveNodeDuplicator *	duplicator_
std::multimap< TCEString, MoveNode * >	invariants_
std::multimap< int, TCEString >	invariantsOfCount_
std::multimap< TTAMachine::FUPort *, MoveNode * >	preSharedOperandPorts_
std::map< MoveNode *, TTAMachine::FUPort *, MoveNode::Comparator >	preLoopSharedOperands_
std::list< ProgramOperation * >	loopBufOps_

Detailed Description

Definition at line 74 of file BF2Scheduler.hh.

Member Typedef Documentation

MoveNodeMap

typedef std::map<MoveNode*, MoveNode*, MoveNode::Comparator> BF2Scheduler::MoveNodeMap

Definition at line 177 of file BF2Scheduler.hh.

Member Enumeration Documentation

LoopSchedulingMode

enum BF2Scheduler::LoopSchedulingMode

Enumerator
NO_LOOP_SCHEDULER

Definition at line 130 of file BF2Scheduler.hh.

                            {
        // Old version
        NO_LOOP_SCHEDULER = 0,
    };

PreLoopOperandEnum

enum BF2Scheduler::PreLoopOperandEnum

Enumerator
NO_PORT
SHARED
NOT_SHARED
NO_LOOP_INVARIANT

Definition at line 135 of file BF2Scheduler.hh.

                            {
        NO_PORT=0,
        SHARED=1,
        NOT_SHARED=2,
        NO_LOOP_INVARIANT=3
    };

SchedulingDirection

enum BF2Scheduler::SchedulingDirection

Enumerator
EITHER
TOPDOWN
BOTTOMUP
EXACTCYCLE

Definition at line 156 of file BF2Scheduler.hh.

                             {
        EITHER=0,
        TOPDOWN=1,
        BOTTOMUP=2,
        EXACTCYCLE=3
    };

Constructor & Destructor Documentation

BF2Scheduler() [1/2]

BF2Scheduler::BF2Scheduler	(	InterPassData &	ipd,
		RegisterRenamer *	renamer
	)

Definition at line 92 of file BF2Scheduler.cc.

                                                  :
    DDGPass(ipd), ddg_(NULL), prologDDG_(nullptr), rm_(NULL),
    prologRM_(nullptr), latestCycle_(INT_MAX/1024),
    renamer_(renamer),
    killDeadResults_(true),
    jumpNode_(NULL),
    llResult_(NULL),
    duplicator_(NULL) {
    options_ =
        dynamic_cast<LLVMTCECmdLineOptions*>(Application::cmdLineOptions());
    if (options_ != NULL) {
        killDeadResults_ = options_->killDeadResults();
    }
 
}

References Application::cmdLineOptions(), SchedulerCmdLineOptions::killDeadResults(), killDeadResults_, and options_.

Here is the call graph for this function:

BF2Scheduler() [2/2]

BF2Scheduler::BF2Scheduler	(	InterPassData &	ipd,
		RegisterRenamer *	renamer,
		bool	killDeadResults
	)

Definition at line 109 of file BF2Scheduler.cc.

                                                                        :
    DDGPass(ipd), ddg_(NULL), rm_(NULL),
    latestCycle_(INT_MAX/1024),
    renamer_(renamer),
    killDeadResults_(killDeadResults),
    jumpNode_(NULL),
    llResult_(NULL),
    duplicator_(NULL) {
    options_ =
        dynamic_cast<LLVMTCECmdLineOptions*>(Application::cmdLineOptions());
}

References Application::cmdLineOptions(), and options_.

Here is the call graph for this function:

~BF2Scheduler()

BF2Scheduler::~BF2Scheduler

(

)

Definition at line 1638 of file BF2Scheduler.cc.

                            {
    while(!scheduledStack_.empty()) {
        BFOptimization* bfo = scheduledStack_.back();
        scheduledStack_.pop_back();
        delete bfo;
    }
}

References scheduledStack_.

Member Function Documentation

allocateFunctionUnits()

void BF2Scheduler::allocateFunctionUnits ( )

private

Allocate function units for pre-loop operand sharing.

Definition at line 1234 of file BF2Scheduler.cc.

                                         {
 
    countLoopInvariantValueUsages();
 
    preSharedOperandPorts_.clear();
    preLoopSharedOperands_.clear();
 
    for (auto i = invariantsOfCount_.rbegin();
         i != invariantsOfCount_.rend(); i++) {
#ifdef DEBUG_PRE_SHARE
        std::cerr << "got invariant: " << i->second << " with usage count: "
                  << i->first << std::endl;
#endif
        for (auto it = invariants_.lower_bound(i->second),
                 end = invariants_.upper_bound(i->second); it != end; ++it) {
#ifdef DEBUG_PRE_SHARE
            std::cerr << "\tgot MN: " << it->second->toString() << " of PO: "
                      << it->second->destinationOperation().toString()
                      << std::endl;
#endif
            preAllocateFunctionUnits(it->second->destinationOperationPtr());
        }
    }
 
#ifdef DEBUG_PRE_SHARE
    std::cerr << "Operand bindings to ports: " << std::endl;
#endif
    for (auto p : preSharedOperandPorts_) {
        auto fup = p.first;
        if (p.second != NULL) {
            MoveNode* mn = p.second;
            preLoopSharedOperands_[mn] = fup;
#ifdef DEBUG_PRE_SHARE
            TTAMachine::FunctionUnit* fu = fup->parentUnit();
            ProgramOperation& po = p.second->destinationOperation(0);
            std::cerr << "\tPort: " << fu->name() << "." << fup->name() <<
                " move: " << p.second->toString() << " of PO: " <<
                po.toString() << std::endl;
#endif
        } else {
#ifdef DEBUG_PRE_SHARE
            TTAMachine::FunctionUnit* fu = fup->parentUnit();
            std::cerr << "\tPort: " << fu->name() << "." << fup->name() <<
                        " shared with multiple ops" << std::endl;
#endif
        }
    }
}

References countLoopInvariantValueUsages(), invariants_, invariantsOfCount_, TTAMachine::Component::name(), preAllocateFunctionUnits(), preLoopSharedOperands_, preSharedOperandPorts_, and ProgramOperation::toString().

Referenced by handleLoopDDG().

Here is the call graph for this function:

bypassNodes()

BF2Scheduler::MoveNodeMap BF2Scheduler::bypassNodes

(

)

Definition at line 1646 of file BF2Scheduler.cc.

                                                  {
    MoveNodeMap bypasses;
    for (auto o : scheduledStack_) {
    auto f = dynamic_cast<BF2ScheduleFront*>(o);
    if (f != NULL) {
        f->appendBypassSources(bypasses);
    }
    }
    return bypasses;
}

References BF2ScheduleFront::appendBypassSources(), and scheduledStack_.

Here is the call graph for this function:

countLoopInvariantValueUsages()

void BF2Scheduler::countLoopInvariantValueUsages ( )

private

Definition at line 1155 of file BF2Scheduler.cc.

                                                 {
    std::map<TCEString, int> invariantCounts;
    std::map<TCEString, int> variableCounts;
 
    invariants_.clear();
    invariantsOfCount_.clear();
 
    static int iaCounter= 0;
    for (int i = 0; i < ddg().programOperationCount(); i++) {
        ProgramOperation& po = ddg().programOperation(i);
        const Operation& op = po.operation();
        if (op.numberOfInputs() == 1) {
            continue; // must be trigger
        }
        for (int k = 1; k <= op.numberOfInputs(); k++) {
            MoveNodeSet& inputNodeSet = po.inputNode(k);
            assert(inputNodeSet.count() == 1);
            MoveNode& inputNode = inputNodeSet.at(0);
            TCEString inputVal;
            if (mustBeTrigger(inputNode, po)) {
                continue;
            }
 
            if (inputNode.isSourceVariable()) {
                inputVal = DisassemblyRegister::registerName(
                    inputNode.move().source());
            } else {
                if (inputNode.isSourceConstant()) {
                    if (inputNode.move().source().isInstructionAddress()) {
                        inputVal << "IADDR" << iaCounter++;
                    } else {
                        // todo: imms longer than 32 bits?
                        inputVal <<
                            inputNode.move().source().value().intValue();
                    }
                } else {
                    // unknown?
                    return;
                }
            }
            if (ddg().isLoopInvariant(inputNode)) {
                invariantCounts[inputVal]++;
                invariants_.insert(std::make_pair(inputVal, &inputNode));
            } else {
                if (inputVal == "0") {
                    std::cerr << "zero not loop invariant: "
                              << inputNode.toString() << std::endl;
                }
                variableCounts[inputVal]++;
            }
 
        }
    }
 
    for (auto p: invariantCounts) {
#ifdef DEBUG_PRE_SHARE
        std::cerr << "usage count of invariant value: " << p.first
                  << " is " << p.second << std::endl;
#endif
        invariantsOfCount_.insert(std::make_pair(p.second, p.first));
    }
 
#ifdef DEBUG_PRE_SHARE
    for (auto p: invariants_) {
        std::cerr << "Invariant value: " << p.first << " used by mn: "
                  << p.second->toString() << " of po: "
                  << p.second->destinationOperation().toString() << std::endl;
    }
    for (auto i = invariantsOfCount_.rbegin();
         i != invariantsOfCount_.rend(); i++) {
        std::cerr << "Count: " << i->first << " for invariant value: "
                  << i->second << std::endl;
    }
#endif
}

References assert, MoveNodeSet::at(), MoveNodeSet::count(), ddg(), ProgramOperation::inputNode(), SimValue::intValue(), invariants_, invariantsOfCount_, TTAProgram::Terminal::isInstructionAddress(), MoveNode::isSourceConstant(), MoveNode::isSourceVariable(), MoveNode::move(), mustBeTrigger(), Operation::numberOfInputs(), ProgramOperation::operation(), DataDependenceGraph::programOperation(), DataDependenceGraph::programOperationCount(), DisassemblyRegister::registerName(), TTAProgram::Move::source(), MoveNode::toString(), and TTAProgram::Terminal::value().

Referenced by allocateFunctionUnits().

Here is the call graph for this function:

currentFront()

BF2ScheduleFront * BF2Scheduler::currentFront ( )

inline

Definition at line 188 of file BF2Scheduler.hh.

{ return currentFront_; }

References currentFront_.

Referenced by BFOptimization::mightBeReady(), BFRenameLiveRange::notifySelector(), BFEarlyBypasser::operator()(), BFShareOperands::operator()(), BFEarlyBypass::operator()(), and BFEarlyBypass::undoOnlyMe().

ddg() [1/2]

DataDependenceGraph & BF2Scheduler::ddg ( )

inline

Definition at line 100 of file BF2Scheduler.hh.

{ return *ddg_; }

References ddg_.

Referenced by countLoopInvariantValueUsages(), BFOptimization::ddg(), BFOptimization::ddg(), handleDDG(), handleLoopDDG(), preAllocateFunctionUnits(), reservePreallocatedFUs(), revertBBLiveRangeBookkeepingForDestination(), revertBBLiveRangeBookkeepingForSource(), scheduleDDG(), and unreservePreallocatedFUs().

ddg() [2/2]

const DataDependenceGraph & BF2Scheduler::ddg ( ) const

inline

Definition at line 101 of file BF2Scheduler.hh.

{ return *ddg_; }

References ddg_.

deletingNode()

void BF2Scheduler::deletingNode

(

MoveNode *

deletedNode

)

Definition at line 1633 of file BF2Scheduler.cc.

                                                     {
    currentFront_->deletingNode(deletedNode);
}

References currentFront_, and BF2ScheduleFront::deletingNode().

Referenced by BFRegCopy::undoDDG().

Here is the call graph for this function:

duplicator()

MoveNodeDuplicator & BF2Scheduler::duplicator ( )

inline

Definition at line 106 of file BF2Scheduler.hh.

                                     {
        assert(duplicator_!=NULL);
        return *duplicator_;
    }

References assert, and duplicator_.

Referenced by BFOptimization::duplicator(), and finalizeSchedule().

eraseFromMoveNodeUseSet()

void BF2Scheduler::eraseFromMoveNodeUseSet ( LiveRangeData::MoveNodeUseMapSet &  mnuMap, const TCEString &  reg, MoveNode *  mn  )

private

Definition at line 749 of file BF2Scheduler.cc.

                                        {
    LiveRangeData::MoveNodeUseMapSet::iterator s = mnuMap.find(reg);
    if (s != mnuMap.end()) {
        LiveRangeData::MoveNodeUseSet& mnuSet = s->second;
        LiveRangeData::MoveNodeUseSet::iterator i =
            mnuSet.find(MoveNodeUse(*mn));
        if (i!= mnuSet.end()) {
            mnuSet.erase(i);
        }
    }
}

Referenced by revertBBLiveRangeBookkeepingForDestination(), and revertBBLiveRangeBookkeepingForSource().

finalizeSchedule()

void BF2Scheduler::finalizeSchedule

(

)

Definition at line 641 of file BF2Scheduler.cc.

                                    {
    for (auto m: dreRemovedMoves_) {
        if (m->isScheduled()) {
            std::cerr << "cannot kill scheduled move: "
                      << m->toString() << std::endl;
            assert(false);
        }
        if (prologRM_) {
            MoveNode *prologMN = duplicator().getMoveNode(*m);
            if (prologMN) {
                if (prologMN->isScheduled()) {
                    std::cerr << "prolog MN: " << prologMN->toString()
                              << "of MN: " << m->toString()
                              << "  is scheduled!" << std::endl;
                    assert(false);
                }
 
                ddg_->rootGraph()->removeNode(*prologMN);
            }
        }
        ddg_->rootGraph()->removeNode(*m);
    }
    for (auto m: removedMoves_) {
        assert(!m->isScheduled());
        ddg_->rootGraph()->removeNode(*m);
    }
 
    // remove undo information, as cannot be undoed after this
    while(!scheduledStack_.empty()) {
        BFOptimization* bfo = scheduledStack_.back();
        scheduledStack_.pop_back();
        delete bfo;
    }
}

References assert, ddg_, dreRemovedMoves_, duplicator(), MoveNodeDuplicator::getMoveNode(), MoveNode::isScheduled(), prologRM_, removedMoves_, BoostGraph< GraphNode, GraphEdge >::removeNode(), BoostGraph< GraphNode, GraphEdge >::rootGraph(), scheduledStack_, and MoveNode::toString().

Referenced by handleDDG(), and handleLoopDDG().

Here is the call graph for this function:

findBypassEdge()

DataDependenceEdge * BF2Scheduler::findBypassEdge

(

const MoveNode &

mn

)

Finds the source where to bypass from.

Definition at line 838 of file BF2Scheduler.cc.

                                                                   {
 
    DataDependenceGraph::EdgeSet edges = ddg_->inEdges(mn);
    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 NULL;
        }
        edgeIter++;
    }
 
    // if no bypassable edge found, cannot bypass
    if (bypassEdge == NULL) {
        return 0;
    }
 
    if (bypassEdge->isBackEdge()) {
       if (!rm().initiationInterval()) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\tbackedge without without loop sched!!"
                      << " not allowed." << std::endl;
#endif
            return NULL;
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        } else {
            std::cerr << "\t\tback edge bypass ok in loop" << std::endl;
#endif
        }
    }
    return bypassEdge;
}

References ddg_, DataDependenceEdge::DEP_RAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), DataDependenceEdge::guardUse(), DataDependenceEdge::headPseudo(), BoostGraph< GraphNode, GraphEdge >::inEdges(), DataDependenceEdge::isBackEdge(), and rm().

Referenced by BFEarlyBypasser::operator()(), and BFPostpassBypasser::tryBypassNode().

Here is the call graph for this function:

findJump()

bool BF2Scheduler::findJump ( )

private

Finds the jump from the bb.

Returns

if found a guarded jump.

Definition at line 1076 of file BF2Scheduler.cc.

                            {
    for (int i = 0; i < ddg_->nodeCount(); i++) {
        MoveNode& mn = ddg_->node(i);
        if (mn.isMove() && mn.move().isJump()) {
            jumpNode_ = &mn;
            return !mn.move().isUnconditional();
        }
    }
    return false;
}

References ddg_, TTAProgram::Move::isJump(), MoveNode::isMove(), TTAProgram::Move::isUnconditional(), jumpNode_, MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::node(), and BoostGraph< GraphNode, GraphEdge >::nodeCount().

Referenced by handleLoopDDG().

Here is the call graph for this function:

findSiblings()

MoveNodeSet BF2Scheduler::findSiblings ( MoveNode &  mn )

private

getDstUnit()

TTAMachine::Unit * BF2Scheduler::getDstUnit

(

MoveNode &

mn

)

Definition at line 122 of file BF2Scheduler.cc.

                                                     {
    if (mn.isDestinationOperation()) {
        ProgramOperation& po = mn.destinationOperation();
        for (int i = 0; i < po.inputMoveCount(); i++) {
            MoveNode& inputNode = po.inputMove(i);
            assert( inputNode.isDestinationOperation());
            if (inputNode.isScheduled()) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                std::cerr << "\t\tFound scheduled input: "
                          << inputNode.toString() << std::endl;
#endif
                    TTAProgram::Terminal& term =
                        inputNode.move().destination();
                assert(term.isFUPort());
                return term.port().parentUnit();
            }
        }
    }
    return NULL;
}

References assert, TTAProgram::Move::destination(), MoveNode::destinationOperation(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isFUPort(), MoveNode::isScheduled(), MoveNode::move(), TTAMachine::Port::parentUnit(), TTAProgram::Terminal::port(), and MoveNode::toString().

Here is the call graph for this function:

getLoopAnalysis()

LoopAnalyzer::LoopAnalysisResult * BF2Scheduler::getLoopAnalysis ( )

inline

Definition at line 198 of file BF2Scheduler.hh.

                                                      {
        return llResult_;
    }

References llResult_.

guardWriteNode()

MoveNode * BF2Scheduler::guardWriteNode ( )

inline

Definition at line 191 of file BF2Scheduler.hh.

{ return jumpGuardWrite_; }

References jumpGuardWrite_.

Referenced by BFOptimization::jumpGuardAvailableCycle(), BFPushAntidepDown::operator()(), BFPushMoveUp::operator()(), and BFPushMoveUp2::operator()().

handleDDG()

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

virtual

Handles a given DDG.

Parameters

ddg	DDG to handle
rm	Resource manager that is to be used.
machine	The target machine if any. (NullMachine::instance() if target machine is irrelevant).

Exceptions

In	case handling is unsuccesful for any reason (basicBlock might still get modified).

Reimplemented from DDGPass.

Definition at line 244 of file BF2Scheduler.cc.

                                                                {
    loopBufOps_.clear();
 
    scheduleDDG(ddg, rm, targetMachine);
 
    int len = rm_->largestCycle() - rm_->smallestCycle()+1;
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "Handled ddg: " <<ddg_->name() << std::endl;
#endif
 
    if (testOnly) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        ddg_->writeToDotFile("tested_schedule.dot");
#endif
        unschedule();
    } else {
        finalizeSchedule();
    }
    if (duplicator_ != NULL) {
        delete duplicator_; duplicator_ = NULL;
    }
 
    return len;
}

References ddg(), ddg_, duplicator_, finalizeSchedule(), SimpleResourceManager::largestCycle(), loopBufOps_, BoostGraph< GraphNode, GraphEdge >::name(), rm(), rm_, scheduleDDG(), SimpleResourceManager::smallestCycle(), targetMachine(), unschedule(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

handleLoopDDG() [1/2]

int BF2Scheduler::handleLoopDDG ( BUMoveNodeSelector &  selector, bool  allowPreLoopOpshare  )

protected

Definition at line 272 of file BF2Scheduler.cc.

                                                            {
    loopBufOps_.clear();
    if (prologRM_ != NULL) {
        if (allowPreLoopOpshare) {
            allocateFunctionUnits();
            reservePreallocatedFUs();
        }  else {
            // TODO: should these be undone, not just cleared?
            preSharedOperandPorts_.clear();
            preLoopSharedOperands_.clear();
        }
 
        duplicator_ = new MoveNodeDuplicator(*ddg_, *prologDDG_);
        duplicator_->setBBN(ddg_->getBasicBlockNode(ddg_->node(0)));
    } else {
        preSharedOperandPorts_.clear();
        preLoopSharedOperands_.clear();
    }
 
    MoveNodeGroup moves = selector.candidates();
    while (moves.nodeCount() > 0) {
        MoveNode* mn = NULL;
        for (int i = 0; i < moves.nodeCount(); i++) {
            if (!moves.node(i).isScheduled()) {
                if (isDeadResult(moves.node(i))) {
                    if (ddg_->hasNode(moves.node(i))) {
                        ddg_->dropNode(moves.node(i));
                    }
                } else {
                    mn = &moves.node(i);
                }
            }
        }
        if (mn == NULL) {
            moves = selector.candidates();
            continue;
        }
 
        if (!scheduleFrontFromMove(*mn)) {
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
            if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
                if (loopLimitNode() == NULL) {
                    ddg_->writeToDotFile(
                        std::string("ii_fail_") +
                        Conversion::toString(rm_->initiationInterval()) +
                        "icount_" +
                        Conversion::toString(tripCount_) +
                        std::string("ops_") +
                        Conversion::toString(allowPreLoopOpshare) +
                        std::string("_dag.dot"));
                } else {
                    ddg_->writeToDotFile(
                        std::string("ii_fail_") +
                        Conversion::toString(rm_->initiationInterval()) +
                        "llNode" +
                        Conversion::toString(loopLimitNode()->nodeID()) +
                        std::string("ops_") +
                        Conversion::toString(allowPreLoopOpshare) +
                        std::string("_dag.dot"));
                }
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
            }
#endif
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << std::endl << std::endl
                      << "Unscheduling all due scheduling failed at around: "
                      << mn->toString() << std::endl << std::endl;
#endif
            unschedule();
            if (prologRM_ != NULL) {
                preSharedOperandPorts_.clear();
                preLoopSharedOperands_.clear();
                unreservePreallocatedFUs();
            }
            if (duplicator_ != NULL) {
                delete duplicator_; duplicator_ = NULL;
            }
            return -1;
        }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "Whole op scheduled ok? original MN: "
                  << mn->toString() << std::endl;
#endif
        moves = selector.candidates();
    }
 
    // Try to schedule pre-loop operand shared moves. if fail, abort.
    if (prologRM_ && allowPreLoopOpshare) {
        if (false) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "Scheduling pre-loop opshares fail, undoing all"
                      << std::endl;
#endif
            unschedule();
            if (prologRM_ != NULL) {
                preSharedOperandPorts_.clear();
                preLoopSharedOperands_.clear();
                unreservePreallocatedFUs();
            }
            if (Application::verboseLevel() > 1) {
                std::cerr << "Scheduling pre-loop operand shares failed."
                          << std::endl;
            }
            if (duplicator_ != NULL) {
                delete duplicator_; duplicator_ = NULL;
            }
            return -1;
        }
    }
 
    //postpass-bypass.
    auto postBypass = new BFPostpassBypasser(*this);
    if ((*postBypass)()) {
        scheduledStack_.push_back(postBypass);
    } else {
        delete postBypass;
    }
 
    int overlapCount =
        (latestCycle_ - rm_->smallestCycle()) / rm_->initiationInterval();
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "inner handleLoopDDG exiting, overlapcount: "
              << overlapCount << std::endl;
#endif
    return overlapCount;
}

References allocateFunctionUnits(), BUMoveNodeSelector::candidates(), ddg_, BoostGraph< GraphNode, GraphEdge >::dropNode(), LLVMTCECmdLineOptions::dumpDDGsDot(), duplicator_, DataDependenceGraph::getBasicBlockNode(), BoostGraph< GraphNode, GraphEdge >::hasNode(), SimpleResourceManager::initiationInterval(), isDeadResult(), MoveNode::isScheduled(), latestCycle_, loopBufOps_, loopLimitNode(), BoostGraph< GraphNode, GraphEdge >::node(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), options_, preLoopSharedOperands_, preSharedOperandPorts_, prologDDG_, prologRM_, reservePreallocatedFUs(), rm_, scheduledStack_, scheduleFrontFromMove(), selector(), MoveNodeDuplicator::setBBN(), SimpleResourceManager::smallestCycle(), MoveNode::toString(), Conversion::toString(), tripCount_, unreservePreallocatedFUs(), unschedule(), Application::verboseLevel(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

handleLoopDDG() [2/2]

int BF2Scheduler::handleLoopDDG ( DataDependenceGraph &  , SimpleResourceManager &  , const TTAMachine::Machine &  , int  tripCount, SimpleResourceManager *  prologRM, bool  testOnly  )

overridevirtual

For BasicBlockPass to be able to call this method...

Reimplemented from DDGPass.

Definition at line 402 of file BF2Scheduler.cc.

                                                    {
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
    if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
        ddg.writeToDotFile(
            std::string("ii_begin_") +
            Conversion::toString(rm.initiationInterval()) +
            std::string("_dag.dot"));
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
    }
#endif
 
    rm.setDDG(&ddg);
    BFOptimization::clearPrologMoves();
#ifdef ENABLE_DOT_SPAM
    ddg.writeToDotFile(
        std::string("before_loop_ddg.dot"));
#endif
 
    targetMachine_ = &targetMachine;
    tripCount_ = tripCount;
    rm_ = &rm;
    prologRM_ = prologRM;
 
    // scheduling pipeline resources after last cycle may cause problems.
    // make RM to check for those
    latestCycle_ = 2*rm.initiationInterval()-1;
    rm.setMaxCycle(latestCycle_);
 
    if (Application::verboseLevel() > 1) {
        std::cerr << std::endl << "Handling new loop ddg: " << ddg.name()
                  << std::endl;
    }
    ddg_ = &ddg;
    ddg_->setMachine(targetMachine);
 
    if (duplicator_ != NULL) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "Duplicator not null in handleloopddg,"
            " deleting duplicator" << std::endl;
#endif
        delete duplicator_; duplicator_ = NULL;
    }
 
    if (!findJump()) {
        return -1;
    }
 
    jumpGuardWrite_ = ddg_->onlyGuardDefOfMove(*jumpNode_);
    if (jumpGuardWrite_ == NULL) {
        return -1;
    }
 
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "jumpguard write node is: "
              << jumpGuardWrite_->toString() << std::endl;
#endif
 
    if (prologRM != NULL) {
        DataDependenceGraph::NodeSet empty;
        prologDDG_ = static_cast<DataDependenceGraph*>(
            ddg_->parentGraph())->createSubgraph(empty);
        prologDDG_->setMachine(targetMachine);
        // TODO: this is kinda incorrect. should be prolog
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "prolog RM not null, pre-allocating FUs:"
                  << prologRM << std::endl;
#endif
    }
 
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
    if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
        ddg_->writeToDotFile(
            (boost::format("bb_%s_ii_%d_before_scheduling.dot") %
             ddg_->name() % rm.initiationInterval()).str());
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
    }
#endif
    BUMoveNodeSelector selector(ddg, targetMachine);
    selector_ = &selector;
    if (renamer_ != NULL) {
        renamer_->setSelector(&selector);
    }
 
    int overlapCount = handleLoopDDG(selector, true);
    if (overlapCount == -1) {
        if (Application::verboseLevel() > 1) {
            std::cerr << "Loop Sched. fail with pre-loop opshare on with II: "
                      << rm.initiationInterval() << std::endl;
        }
        selector.initializeReadylist();
        overlapCount = handleLoopDDG(selector, false);
        if (overlapCount == -1) {
            if (Application::verboseLevel() > 1) {
                std::cerr << "Loop Sched. fail without pre-loop opshare, II: "
                          << rm.initiationInterval() << std::endl;
            }
            if (duplicator_ != NULL) {
                delete duplicator_; duplicator_ = NULL;
            }
            return -1;
        } else {
            if (Application::verboseLevel() > 1) {
                std::cerr << "Loop Sched. ok without pre-loop opshare, II: "
                          << rm.initiationInterval() << std::endl;
            }
        }
    }
 
    if (ddg_->scheduledNodeCount() != ddg_->nodeCount()) {
        ddg_->writeToDotFile(
            (boost::format("%s_unscheduled_nodes_in_ddg.dot") %
             ddg_->name()).str());
 
        assert(false && "unscheduled nodes in ddg after scheduler");
    }
 
    // loop schedulign did not help.
    if (testOnly) {
        if (overlapCount == 0 && Application::verboseLevel() > 1) {
            Application::logStream()
                << "No overlapping instructions, "
                << "Should decrease II"
                << std::endl;
        }
        // this have to be calculated before unscheduling.
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "Unscheduling all due loop sched too slow or testonly"
                  << std::endl;
#endif
 
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
        if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
            ddg_->writeToDotFile(
                std::string("ii_test_or_slow_") +
                Conversion::toString(rm.initiationInterval()) +
                std::string("_dag.dot"));
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
    }
#endif
 
        unschedule();
 
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
        if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
            ddg_->writeToDotFile(
                std::string("ii_unscheduled_slow") +
                Conversion::toString(rm.initiationInterval()) +
                std::string("_dag.dot"));
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
        }
#endif
 
        if (prologRM_ != NULL) {
            preSharedOperandPorts_.clear();
            preLoopSharedOperands_.clear();
            unreservePreallocatedFUs();
        }
        if (duplicator_ != NULL) {
            delete duplicator_; duplicator_ = NULL;
        }
        return overlapCount;
    }
 
    if (loopLimitNode() == NULL && tripCount && overlapCount >= tripCount) {
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
        if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
            ddg_->writeToDotFile(
                std::string("ii_no_overlap") +
                Conversion::toString(rm.initiationInterval()) +
                std::string("_dag.dot"));
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
        }
#endif
        unschedule();
 
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
        if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
            ddg_->writeToDotFile(
                std::string("ii_unscheduled_no_overlap") +
                Conversion::toString(rm.initiationInterval()) +
                std::string("_dag.dot"));
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
        }
#endif
        if (prologRM_ != NULL) {
            preSharedOperandPorts_.clear();
            preLoopSharedOperands_.clear();
            unreservePreallocatedFUs();
        }
 
        if (duplicator_ != NULL) {
            delete duplicator_; duplicator_ = NULL;
        }
        return -1;
    }
 
 
    if (options_ != NULL && options_->dumpDDGsDot()) {
        ddg_->writeToDotFile(
            (boost::format("bb_%s_after_scheduling.dot") %
             ddg_->name()).str());
    }
 
    if (options_ != NULL && options_->dumpDDGsXML()) {
        ddg_->writeToXMLFile(
            (boost::format("bb_%s_after_scheduling.dot") %
             ddg_->name()).str());
    }
 
    finalizeSchedule();
 
    if (Application::verboseLevel() > 1) {
        std::cerr << "Handled loop ddg: " <<ddg_->name() << std::endl;
    }
 
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
    if (options_ != NULL && options_->dumpDDGsDot()) {
#endif
        ddg_->writeToDotFile(
            std::string("ii_ok_") +
            Conversion::toString(rm.initiationInterval()) +
            std::string("iters_") +
            Conversion::toString(tripCount) +
            std::string("_dag.dot"));
#ifndef DEBUG_BUBBLEFISH_SCHEDULER
    }
#endif
    return overlapCount;
}

References assert, BFOptimization::clearPrologMoves(), ddg(), ddg_, LLVMTCECmdLineOptions::dumpDDGsDot(), LLVMTCECmdLineOptions::dumpDDGsXML(), duplicator_, finalizeSchedule(), findJump(), handleLoopDDG(), BUMoveNodeSelector::initializeReadylist(), SimpleResourceManager::initiationInterval(), jumpGuardWrite_, jumpNode_, latestCycle_, Application::logStream(), loopLimitNode(), BoostGraph< GraphNode, GraphEdge >::name(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), DataDependenceGraph::onlyGuardDefOfMove(), options_, BoostGraph< GraphNode, GraphEdge >::parentGraph(), preLoopSharedOperands_, preSharedOperandPorts_, prologDDG_, prologRM(), prologRM_, renamer_, rm(), rm_, DataDependenceGraph::scheduledNodeCount(), selector(), selector_, SimpleResourceManager::setDDG(), DataDependenceGraph::setMachine(), SimpleResourceManager::setMaxCycle(), RegisterRenamer::setSelector(), targetMachine(), targetMachine_, MoveNode::toString(), Conversion::toString(), tripCount(), tripCount_, unreservePreallocatedFUs(), unschedule(), Application::verboseLevel(), GraphBase< GraphNode, GraphEdge >::writeToDotFile(), and DataDependenceGraph::writeToXMLFile().

Referenced by handleLoopDDG().

Here is the call graph for this function:

hasUnscheduledSuccessors()

bool BF2Scheduler::hasUnscheduledSuccessors

(

MoveNode &

mn

)

const

Definition at line 1054 of file BF2Scheduler.cc.

                                                              {
 
    DataDependenceGraph::NodeSet succ = ddg_->successors(mn, true);
    for (auto m: succ) {
        if (!m->isScheduled()) {
            if (!isDeadResult(*m) && m != &mn) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "\t\t\tunsched succ: " << m->toString()
              << std::endl;
#endif
                return true;
            }
        }
    }
    return false;
}

References ddg_, isDeadResult(), and BoostGraph< GraphNode, GraphEdge >::successors().

Referenced by BF2ScheduleFront::getMoveNodeFromFrontBU().

Here is the call graph for this function:

initializeQueues()

void BF2Scheduler::initializeQueues ( )

private

isDeadResult()

bool BF2Scheduler::isDeadResult

(

MoveNode &

mn

)

const

Definition at line 798 of file BF2Scheduler.cc.

                                                  {
    return dreRemovedMoves_.find(&mn) != dreRemovedMoves_.end() ||
        removedMoves_.find(&mn) != removedMoves_.end();
}

References dreRemovedMoves_, and removedMoves_.

Referenced by BFEarlyBypasser::bypassSourceLatestCycle(), BF2ScheduleFront::getMoveNodeFromFrontBU(), handleLoopDDG(), hasUnscheduledSuccessors(), BF2ScheduleFront::printFront(), scheduleDDG(), and BF2ScheduleFront::scheduleFrontFromMove().

isDestinationUniversalReg()

bool BF2Scheduler::isDestinationUniversalReg ( const MoveNode &  mn )

static

Definition at line 773 of file BF2Scheduler.cc.

                                                          {
    if (!mn.isDestinationVariable()) {
        return false;
    }
    return mn.move().destination().isUniversalMachineRegister();
}

References TTAProgram::Move::destination(), MoveNode::isDestinationVariable(), TTAProgram::Terminal::isUniversalMachineRegister(), and MoveNode::move().

Referenced by BF2ScheduleFront::allNodesOfSameOperation(), BF2ScheduleFront::findInducingBypassSource(), BF2ScheduleFront::findInducingBypassSourceFromOperation(), and BF2ScheduleFront::tryRevertEarlierBypass().

Here is the call graph for this function:

isPreLoopSharedOperand()

TTAMachine::FUPort * BF2Scheduler::isPreLoopSharedOperand

(

MoveNode &

mn

)

const

Definition at line 1625 of file BF2Scheduler.cc.

                                                                         {
    auto i = preLoopSharedOperands_.find(&mn);
    if (i == preLoopSharedOperands_.end()) {
        return NULL;
    }
    return i->second;
}

References preLoopSharedOperands_.

Referenced by BFSwapOperands::BFSwapOperands(), BFEarlyBypasser::bypassSourceLatestCycle(), BF2ScheduleFront::getMoveNodeFromFrontBU(), BFDropPreShared::operator()(), reservePreallocatedFUs(), BF2ScheduleFront::scheduleFrontFromMove(), BF2ScheduleFront::scheduleMove(), and BF2ScheduleFront::tryToScheduleMoveOuter().

isRegCopyAfter()

bool BF2Scheduler::isRegCopyAfter ( MoveNode &  mn )

private

isRegCopyBefore()

bool BF2Scheduler::isRegCopyBefore ( MoveNode &  mn )

private

isSourceUniversalReg()

bool BF2Scheduler::isSourceUniversalReg ( const MoveNode &  mn )

static

Definition at line 765 of file BF2Scheduler.cc.

                                                     {
    if (!mn.isSourceVariable()) {
        return false;
    }
    return mn.move().source().isUniversalMachineRegister();
}

References MoveNode::isSourceVariable(), TTAProgram::Terminal::isUniversalMachineRegister(), MoveNode::move(), and TTAProgram::Move::source().

Referenced by BF2ScheduleFront::allNodesOfSameOperation(), and BFScheduleBU::operator()().

Here is the call graph for this function:

isTrigger()

bool BF2Scheduler::isTrigger	(	const TTAMachine::Unit &	unit,
		MoveNode &	mn
	)

Checks whether given movenode is a trigger in given FU

Definition at line 819 of file BF2Scheduler.cc.

                                                                     {
    const TTAMachine::FunctionUnit& fu =
        dynamic_cast<const TTAMachine::FunctionUnit&>(unit);
 
    TTAProgram::Terminal& term = mn.move().destination();
    int operandNum =  term.operationIndex();
 
    const Operation& op = mn.destinationOperation().operation();
 
    const TTAMachine::HWOperation* hwop =
        fu.operation(op.name());
 
    const TTAMachine::FUPort* port = hwop->port(operandNum);
    return port->isTriggering();
}

References TTAProgram::Move::destination(), MoveNode::destinationOperation(), TTAMachine::FUPort::isTriggering(), MoveNode::move(), Operation::name(), ProgramOperation::operation(), TTAMachine::FunctionUnit::operation(), TTAProgram::Terminal::operationIndex(), and TTAMachine::HWOperation::port().

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

Here is the call graph for this function:

jumpGuard()

TTAProgram::MoveGuard * BF2Scheduler::jumpGuard

(

)

Definition at line 1087 of file BF2Scheduler.cc.

                                             {
    if (jumpNode_->move().isUnconditional()) {
        std::cerr << "jump is unconditional: " << jumpNode_->toString()
                  << std::endl;
    }
    assert (!jumpNode_->move().isUnconditional());
    return &jumpNode_->move().guard();
}

References assert, TTAProgram::Move::guard(), TTAProgram::Move::isUnconditional(), jumpNode_, MoveNode::move(), and MoveNode::toString().

Referenced by BFOptimization::setJumpGuard().

Here is the call graph for this function:

jumpNode()

MoveNode * BF2Scheduler::jumpNode ( )

inline

Definition at line 192 of file BF2Scheduler.hh.

{ return jumpNode_; }

References jumpNode_.

Referenced by BFOptimization::jumpGuardAvailableCycle().

killDeadResults()

bool BF2Scheduler::killDeadResults ( ) const

inline

Definition at line 110 of file BF2Scheduler.hh.

{ return killDeadResults_; }

References killDeadResults_.

Referenced by BFDREEarly::operator()(), BFDRELate::operator()(), BFDRELoop::operator()(), BFPostpassDRE::operator()(), and BFPostpassLoopDRE::operator()().

loopBufOps()

std::list< ProgramOperation * > BF2Scheduler::loopBufOps

(

)

loopLimitNode()

MoveNode * BF2Scheduler::loopLimitNode ( )

inline

Definition at line 194 of file BF2Scheduler.hh.

                              {
        return llResult_ == 0 ? NULL : llResult_->counterValueNode;
    }

References LoopAnalyzer::LoopAnalysisResult::counterValueNode, and llResult_.

Referenced by handleLoopDDG(), and handleLoopDDG().

maximumAllowedCycle()

int BF2Scheduler::maximumAllowedCycle ( ) const

inline

Definition at line 186 of file BF2Scheduler.hh.

{ return latestCycle_; }

References latestCycle_.

Referenced by BFPushAntidepDown::operator()(), and BFScheduleTD::operator()().

mustBeTrigger()

bool BF2Scheduler::mustBeTrigger	(	const MoveNode &	mn,
		const ProgramOperation &	po
	)

Definition at line 1123 of file BF2Scheduler.cc.

                                                    {
    const Operation& op = po.operation();
    int inputCount = op.numberOfInputs();
    if (inputCount < 2) {
        return true;
    }
    MoveNode* trig =
        BasicBlockScheduler::findTrigger(po, *targetMachine_);
    if (trig != &mn) {
        return false;
    }
    int myIdx = mn.move().destination().operationIndex();
    for (int i = 1; i <= inputCount; i++) {
        if (i != myIdx && op.canSwap(myIdx, i)) {
            return false;
        }
    }
    return true;
}

References Operation::canSwap(), TTAProgram::Move::destination(), BasicBlockScheduler::findTrigger(), MoveNode::move(), Operation::numberOfInputs(), ProgramOperation::operation(), TTAProgram::Terminal::operationIndex(), and targetMachine_.

Referenced by countLoopInvariantValueUsages().

Here is the call graph for this function:

nodeAndCopyKilled()

void BF2Scheduler::nodeAndCopyKilled

(

MoveNode &

mn

)

Definition at line 803 of file BF2Scheduler.cc.

                                                 {
    dreRemovedMoves_.insert(&mn);
}

References dreRemovedMoves_.

Referenced by BFDREEarly::operator()(), BFDRELate::operator()(), BFShareOperandLate::operator()(), BFShareOperandWithScheduled::operator()(), and BFPostpassDRE::operator()().

nodeKilled()

void BF2Scheduler::nodeKilled

(

MoveNode &

mn

)

Definition at line 807 of file BF2Scheduler.cc.

                                          {
    removedMoves_.insert(&mn);
}

References removedMoves_.

Referenced by BFDRELoop::operator()(), BFDropPreShared::operator()(), BFKillNode::operator()(), and BFPostpassLoopDRE::operator()().

nodeResurrected()

void BF2Scheduler::nodeResurrected

(

MoveNode &

mn

)

Definition at line 811 of file BF2Scheduler.cc.

                                               {
    removedMoves_.erase(&mn);
    dreRemovedMoves_.erase(&mn);
}

References dreRemovedMoves_, and removedMoves_.

Referenced by BFShareOperandWithScheduled::operator()(), BFShareOperandLate::revert(), BFDropPreShared::undoOnlyMe(), BFKillNode::undoOnlyMe(), BFShareOperandWithScheduled::undoOnlyMe(), and BFPostpassLoopDRE::undoOnlyMe().

possibleTempRegRFs()

std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator > BF2Scheduler::possibleTempRegRFs	(	const MoveNode &	mn,
		bool	tempRegAfter,
		const TTAMachine::RegisterFile *	forbiddenRF = nullptr
	)

Find possible temp reg RF's for connectivity of given register.

This only gives the register files that for the "next register in the temp reg chain", not the whole chain

Definition at line 899 of file BF2Scheduler.cc.

                                               {
 
    std::set<const TTAMachine::RegisterFile*,
        TTAMachine::MachinePart::Comparator>
        result;
 
    std::map<int, int> rfDistanceFromSource;
    std::map<int, int> rfDistanceFromDestination;
 
    typedef SimpleInterPassDatum<
    std::vector<std::pair<const TTAMachine::RegisterFile*, int> > >
        TempRegData;
 
    std::string srDatumName = "SCRATCH_REGISTERS";
    if (!DDGPass::interPassData().hasDatum(srDatumName) ||
        (dynamic_cast<TempRegData&>(
             DDGPass::interPassData().datum(srDatumName))).size() == 0) {
        TCEString msg("No scratch registers available for "
                      "temporary moves for move: ");
        msg << mn.toString();
        throw IllegalProgram(__FILE__, __LINE__, __func__, msg);
    }
    const TempRegData& tempRegs =
        dynamic_cast<TempRegData&>(
            DDGPass::interPassData().datum(srDatumName));
 
 
    for (unsigned int i = 0; i < tempRegs.size(); i++) {
        rfDistanceFromSource[i] = INT_MAX;
        rfDistanceFromDestination[i] = INT_MAX;
    }
 
 
    for (unsigned int i = 0; i < tempRegs.size(); i++) {
        const TTAMachine::RegisterFile* rf = tempRegs[i].first;
        MachineConnectivityCheck::PortSet readPorts =
            MachineConnectivityCheck::findReadPorts(*rf);
        MachineConnectivityCheck::PortSet writePorts =
            MachineConnectivityCheck::findWritePorts(*rf);
        bool srcOk = false;
 
        if (rf == forbiddenRF) {
            continue;
        }
 
        if (MachineConnectivityCheck::canSourceWriteToAnyDestinationPort(
                mn, writePorts)) {
            rfDistanceFromSource[i] = 1;
            srcOk = true;
        }
 
        if (MachineConnectivityCheck::canAnyPortWriteToDestination(
                readPorts, mn)) {
            rfDistanceFromDestination[i] = 1;
            if (srcOk) {
                // this RF does it!
                result.insert(rf);
            }
        }
    }
 
    // modified check to avoid 4ever loop in case of broken machine
    bool modified = true;
    if (!tempRegAfter) {
    while (result.empty() && modified) {
        int shortest = INT_MAX;
        modified = false;
        for (unsigned int i = 0; i < tempRegs.size(); i++) {
            int srcDist = rfDistanceFromSource[i];
            if (srcDist != INT_MAX) {
                const TTAMachine::RegisterFile* rfSrc = tempRegs[i].first;
                for (unsigned int j = 0; j < tempRegs.size(); j++) {
                    if (rfDistanceFromSource[j] > srcDist + 1) {
                        const TTAMachine::RegisterFile* rfDest =
                            tempRegs[j].first;
                        // ignore rf's which are not wide enough
                        if (MachineConnectivityCheck::isConnected(
                                *rfSrc, *rfDest,
                                (mn.move().isUnconditional() ? NULL :
                                 &mn.move().guard().guard()))) {
                            rfDistanceFromSource[j] = srcDist + 1;
                            modified = true;
                            if (rfDistanceFromDestination[j] == 1) {
                                int dist = srcDist + 2;
                                if (dist < shortest) {
                                    result.clear();
                                    shortest = dist;
                                }
                                if (dist == shortest) {
                                    result.insert(rfDest);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return result;
    } else {
        while (result.empty() && modified) {
        int shortest = INT_MAX;
        modified = false;
        for (unsigned int i = 0; i < tempRegs.size(); i++) {
            int dstDist = rfDistanceFromDestination[i];
            if (dstDist != INT_MAX) {
                const TTAMachine::RegisterFile* rfDst = tempRegs[i].first;
                for (unsigned int j = 0; j < tempRegs.size(); j++) {
                    if (rfDistanceFromDestination[j] > dstDist + 1) {
                        const TTAMachine::RegisterFile* rfSrc =
                            tempRegs[j].first;
                        if (MachineConnectivityCheck::isConnected(
                                *rfDst, *rfSrc,
                                (mn.move().isUnconditional() ? NULL :
                                 &mn.move().guard().guard()))) {
                            rfDistanceFromDestination[j] = dstDist + 1;
                            modified = true;
                            if (rfDistanceFromSource[j] == 1) {
                                int dst = dstDist + 2;
                                if (dst < shortest) {
                                    result.clear();
                                    shortest = dst;
                                }
                                if (dst == shortest) {
                                    result.insert(rfSrc);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return result;
    }
}

References __func__, MachineConnectivityCheck::canAnyPortWriteToDestination(), MachineConnectivityCheck::canSourceWriteToAnyDestinationPort(), InterPassData::datum(), MachineConnectivityCheck::findReadPorts(), MachineConnectivityCheck::findWritePorts(), TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), SchedulerPass::interPassData(), MachineConnectivityCheck::isConnected(), TTAProgram::Move::isUnconditional(), MoveNode::move(), and MoveNode::toString().

Referenced by BFRegCopyAfter::splitMove(), and BFRegCopyBefore::splitMove().

Here is the call graph for this function:

preAllocateFunctionUnits() [1/3]

void BF2Scheduler::preAllocateFunctionUnits ( ProgramOperationPtr  po )

private

Definition at line 1283 of file BF2Scheduler.cc.

                                                                  {
    const Operation& op = po->operation();
#ifdef DEBUG_PRE_SHARE
    std::cerr << "Trying to preallocate for: " << po->toString()
              << std::endl;
#endif
 
    // first phase only share port which is already
    // shared with same value.
    PreLoopShareInfo rv = preAllocateFunctionUnitsInner(po, op, true);
    if (rv.state_ == NOT_SHARED) {
#ifdef DEBUG_PRE_SHARE
        std::cerr << "\t\tDid not find pre-shared, trying again.."
                  << std::endl;
#endif
        // second phase, can reserve a new port.
        rv = preAllocateFunctionUnitsInner(po, op, false);
    }
 
    // could not allocate even with shared ones. must steal from someone
    // just take first FU capable of executing the op.
    // find the port with least use.
    if (rv.state_ == NO_PORT) {
        releasePortForOp(op);
    }
}

References NO_PORT, NOT_SHARED, preAllocateFunctionUnitsInner(), releasePortForOp(), and BF2Scheduler::PreLoopShareInfo::state_.

Referenced by allocateFunctionUnits(), preAllocateFunctionUnits(), and preAllocateFunctionUnitsInner().

Here is the call graph for this function:

preAllocateFunctionUnits() [2/3]

BF2Scheduler::PreLoopShareInfo BF2Scheduler::preAllocateFunctionUnits ( ProgramOperationPtr  po, const Operation &  op, const TTAMachine::HWOperation &  hwop, bool  onlySharedWithAnother  )

private

Definition at line 1405 of file BF2Scheduler.cc.

                                                                   {
 
    bool hasLoopInvariant = false;
    for (int k = 1; k <= op.numberOfInputs(); k++) {
        MoveNodeSet& inputNodeSet = po->inputNode(k);
        assert(inputNodeSet.count() == 1);
        MoveNode& inputNode = inputNodeSet.at(0);
        if (!ddg().isLoopInvariant(inputNode)) {
            // still need to check if the port is free,
            // to not use all FU ports for shared operands.
            TTAMachine::FUPort* port = hwop.port(k);
            std::multimap<TTAMachine::FUPort*, MoveNode*>::iterator pi=
                preSharedOperandPorts_.find(port);
            if (pi != preSharedOperandPorts_.end() && pi->second != NULL) {
                return PreLoopShareInfo(NO_PORT);
            }
            continue;
        }
 
        // we have a loop invariant.
        hasLoopInvariant = true;
        PreLoopShareInfo rv = preAllocateFunctionUnits(
            po, op, k, hwop, onlySharedWithAnother);
        if (rv.state_ == SHARED) {
            // Allocated to this FU now.
#ifdef DEBUG_PRE_SHARE
            std::cerr << "Allocating port for pre-loop opshare: "
                      << rv.sharedPort_->parentUnit()->name() << "."
                      << rv.sharedPort_->name() << " move: "
                      << rv.sharedMN_->toString() << " of po: "
                      << rv.sharedMN_->destinationOperation().toString()
                      << std::endl;
#endif
            preSharedOperandPorts_.insert(
                std::make_pair(rv.sharedPort_,rv.sharedMN_));
            return rv;
        }
        if (rv.state_ == NO_PORT) {
            // cannot allocate this op to this FU
            return rv;
        }
    }
    return hasLoopInvariant ?
        PreLoopShareInfo(NOT_SHARED) :
        PreLoopShareInfo(NO_LOOP_INVARIANT);
 
}

References assert, MoveNodeSet::at(), MoveNodeSet::count(), ddg(), MoveNode::destinationOperation(), TTAMachine::Component::name(), TTAMachine::Port::name(), NO_LOOP_INVARIANT, NO_PORT, NOT_SHARED, Operation::numberOfInputs(), TTAMachine::BaseFUPort::parentUnit(), TTAMachine::HWOperation::port(), preAllocateFunctionUnits(), preSharedOperandPorts_, SHARED, BF2Scheduler::PreLoopShareInfo::sharedMN_, BF2Scheduler::PreLoopShareInfo::sharedPort_, BF2Scheduler::PreLoopShareInfo::state_, MoveNode::toString(), and ProgramOperation::toString().

Here is the call graph for this function:

preAllocateFunctionUnits() [3/3]

BF2Scheduler::PreLoopShareInfo BF2Scheduler::preAllocateFunctionUnits ( ProgramOperationPtr  po, const Operation &  op, int  operandIndex, const TTAMachine::HWOperation &  hwop, bool  onlySharedWithAnother  )

private

Definition at line 1455 of file BF2Scheduler.cc.

                                {
 
    MoveNodeSet& inputNodeSet = po->inputNode(operandIndex);
    assert(inputNodeSet.count() == 1);
    MoveNode& inputNode = inputNodeSet.at(0);
 
    TTAMachine::FUPort* port = hwop.port(operandIndex);
    bool isTrigger = port->isTriggering();
    int swappedOperandIndex = 0;
    if (isTrigger) {
        swappedOperandIndex = swapToUntrigger(po, op, operandIndex,inputNode);
        // still trigger? then try another FU?
        if (swappedOperandIndex) {
            port = hwop.port(swappedOperandIndex);
        } else {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "\t\tswap failed" << std::endl;
#endif
            return PreLoopShareInfo(NOT_SHARED);
        }
    }
 
    std::map<TTAMachine::FUPort*, MoveNode*>::iterator pi=
        preSharedOperandPorts_.find(port);
    if (pi == preSharedOperandPorts_.end()) {
        // if need to share with another use, do not allow reserving new
        // port.
        if (onlySharedWithAnother) {
            if (swappedOperandIndex) {
                revertTopOpt();
            }
            return PreLoopShareInfo(NOT_SHARED);
        } else {
            // create new sharing, use first free
            assert(!port->isTriggering());
            return PreLoopShareInfo(inputNode, *port);
        }
    } else {
        MoveNode* prev = pi->second;
        if (prev == NULL) {
            // NULL means reserved for everybody. cannot own it.
            if (swappedOperandIndex) {
                revertTopOpt();
            }
            return PreLoopShareInfo(NOT_SHARED);
        }
        // port already used for some operand share..
        // but is it same?
        if (prev->move().source().equals(
                inputNode.move().source())) {
            assert(!port->isTriggering());
            return PreLoopShareInfo(inputNode, *port);
        } else {
            // different input value than previous, cannot share or use this fu
            if (swappedOperandIndex) {
                revertTopOpt();
            }
#ifdef DEBUG_PRE_SHARE
            std::cerr << "\t\t\tport used by another sharing, cannot use"
                      << std::endl;
#endif
            return PreLoopShareInfo(NO_PORT);
        }
    }
}

References assert, MoveNodeSet::at(), MoveNodeSet::count(), TTAProgram::Terminal::equals(), isTrigger(), TTAMachine::FUPort::isTriggering(), MoveNode::move(), NO_PORT, NOT_SHARED, TTAMachine::HWOperation::port(), preSharedOperandPorts_, revertTopOpt(), TTAProgram::Move::source(), and swapToUntrigger().

Here is the call graph for this function:

preAllocateFunctionUnitsInner()

BF2Scheduler::PreLoopShareInfo BF2Scheduler::preAllocateFunctionUnitsInner ( ProgramOperationPtr  po, const Operation &  op, bool  onlySharedWithAnother  )

private

Definition at line 1364 of file BF2Scheduler.cc.

                                {
 
    TCEString opName = op.name();
    TTAMachine::Machine::FunctionUnitNavigator fuNav =
        targetMachine().functionUnitNavigator();
 
    bool fuFound = false;
    // we have a loop invariant.
    // Check which FUs can execute this operation.
    for (int j = 0; j < fuNav.count(); j++) {
        const TTAMachine::FunctionUnit& fu = *(fuNav.item(j));
        if (!fu.hasOperation(opName)) {
            continue;
        }
        const TTAMachine::HWOperation& hwop = *fu.operation(opName);
        PreLoopShareInfo rv = preAllocateFunctionUnits(
            po, op, hwop, onlySharedWithAnother);
        switch(rv.state_) {
        case SHARED:
        case NO_LOOP_INVARIANT:
            return rv;
        case NOT_SHARED:
#ifdef DEBUG_PRE_SHARE
            std::cerr << "\t\tfu found but cannot share: " << fu.name()
                      << std::endl;
#endif
            fuFound = true;
        default:
            break;
        }
    }
    if (targetMachine().controlUnit()->hasOperation(opName)) {
        fuFound = true;
    }
    return fuFound ?
        PreLoopShareInfo(NOT_SHARED) :
        PreLoopShareInfo(NO_PORT);
}

References TTAMachine::Machine::Navigator< ComponentType >::count(), TTAMachine::Machine::functionUnitNavigator(), TTAMachine::FunctionUnit::hasOperation(), TTAMachine::Machine::Navigator< ComponentType >::item(), TTAMachine::Component::name(), Operation::name(), NO_LOOP_INVARIANT, NO_PORT, NOT_SHARED, TTAMachine::FunctionUnit::operation(), preAllocateFunctionUnits(), SHARED, BF2Scheduler::PreLoopShareInfo::state_, and targetMachine().

Referenced by preAllocateFunctionUnits().

Here is the call graph for this function:

prologDDG()

DataDependenceGraph * BF2Scheduler::prologDDG ( )

inline

Definition at line 102 of file BF2Scheduler.hh.

{ return prologDDG_; }

References prologDDG_.

Referenced by BFOptimization::prologDDG().

prologRM()

SimpleResourceManager * BF2Scheduler::prologRM ( )

inline

Definition at line 104 of file BF2Scheduler.hh.

{ return prologRM_; }

References prologRM_.

Referenced by handleLoopDDG(), and BFOptimization::prologRM().

pushAntidepDestsDown()

bool BF2Scheduler::pushAntidepDestsDown ( MoveNode &  mn, int  oldLC, int  maxLC  )

private

releasePortForOp()

void BF2Scheduler::releasePortForOp ( const Operation &  op )

private

Definition at line 1310 of file BF2Scheduler.cc.

                                                       {
#ifdef DEBUG_PRE_SHARE
    std::cerr << "\tNo free fu for op: " << op.name() <<
            " have to revert earlier share" << std::endl;
#endif
    TTAMachine::Machine::FunctionUnitNavigator fuNav =
        targetMachine().functionUnitNavigator();
    TCEString opName = op.name();
    TTAMachine::FUPort* bestPort = NULL;
 
    int shareOpCount = INT_MAX;
    for (int j = 0; j < fuNav.count(); j++) {
        const TTAMachine::FunctionUnit& fu = *(fuNav.item(j));
        if (!fu.hasOperation(opName)) {
            continue;
        }
        const TTAMachine::HWOperation& hwop = *fu.operation(opName);
        for (int k = 1; k <= op.numberOfInputs(); k++) {
            TTAMachine::FUPort* port = hwop.port(k);
            if (port->isTriggering()) {
                continue;
            } else {
                std::map<TTAMachine::FUPort*, MoveNode*>::iterator i =
                    preSharedOperandPorts_.find(port);
                if (i != preSharedOperandPorts_.end() && i->second != NULL) {
                    int destOpCount = preSharedOperandPorts_.count(port);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
                    std::cerr << "\t\t\tReserved port: " <<
                        port->parentUnit()->name() << "." <<
                        port->name() << " has  " << destOpCount <<
                        " shared operations using it" << std::endl;
#endif
                    if (destOpCount < shareOpCount) {
                        bestPort = port;
                        shareOpCount = destOpCount;
                    }
                }
            }
        }
    }
 
    assert(bestPort != NULL);
#ifdef DEBUG_PRE_SHARE
    std::cerr << "\t\tPass 3: UnReserved port: " <<
        bestPort->parentUnit()->name() << "." <<
        bestPort->name() << " because of " <<
        op.name() << std::endl;
#endif
    preSharedOperandPorts_.erase(bestPort);
    preSharedOperandPorts_.insert(std::make_pair(bestPort, (MoveNode*)NULL));
}

References assert, TTAMachine::Machine::Navigator< ComponentType >::count(), TTAMachine::Machine::functionUnitNavigator(), TTAMachine::FunctionUnit::hasOperation(), TTAMachine::FUPort::isTriggering(), TTAMachine::Machine::Navigator< ComponentType >::item(), TTAMachine::Component::name(), TTAMachine::Port::name(), Operation::name(), Operation::numberOfInputs(), TTAMachine::FunctionUnit::operation(), TTAMachine::BaseFUPort::parentUnit(), TTAMachine::HWOperation::port(), preSharedOperandPorts_, and targetMachine().

Referenced by preAllocateFunctionUnits().

Here is the call graph for this function:

renamer()

RegisterRenamer * BF2Scheduler::renamer ( )

inline

Definition at line 221 of file BF2Scheduler.hh.

{ return renamer_; }

References renamer_.

Referenced by BFRenameLiveRange::operator()(), BFRenameSource::operator()(), BFRenameLiveRange::renameLiveRange(), and BFRenameLiveRange::undoOnlyMe().

reservePreallocatedFUs()

void BF2Scheduler::reservePreallocatedFUs ( )

private

Definition at line 1546 of file BF2Scheduler.cc.

                                          {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << "Reserving preallocated fus" << std::endl;
#endif
    for (int i = 0; i < ddg().programOperationCount(); i++) {
        ProgramOperation& po = ddg().programOperation(i);
        const Operation& op = po.operation();
        TCEString opName = op.name();
 
        const TTAMachine::FunctionUnit* preAllocatedFU = NULL;
        for (int j = 1; j <= op.numberOfInputs(); j++) {
            MoveNodeSet& inputNodes = po.inputNode(j);
            if (inputNodes.count() != 1) {
                assert(0);
            }
            MoveNode& inputNode = inputNodes.at(0);
            TTAMachine::FUPort* fup = isPreLoopSharedOperand(inputNode);
            if (fup) {
                preAllocatedFU = fup->parentUnit();
                break;
            }
        }
        if (preAllocatedFU) {
            std::string fuName = preAllocatedFU->name();
            annotateAllInputs(
                po,
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST,
                fuName);
 
            annotateAllOutputs(po,
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC,
                fuName);
        } else {
            const TTAMachine::FunctionUnit* prevFU = nullptr;
            for (auto p: preSharedOperandPorts_) {
                if (p.second == NULL) {
                    continue;
                }
                const TTAMachine::FunctionUnit* fu = p.first->parentUnit();
                if (fu == prevFU) {
                    continue;
                }
                prevFU = fu;
                std::string fuName= fu->name();
 
                annotateAllInputs(po,
                    TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST,
                    fuName);
 
                annotateAllOutputs(po,
                    TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC,
                    fuName);
            }
        }
    }
}

References TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST, TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC, TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST, TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC, annotateAllInputs(), annotateAllOutputs(), assert, MoveNodeSet::at(), MoveNodeSet::count(), ddg(), ProgramOperation::inputNode(), isPreLoopSharedOperand(), TTAMachine::Component::name(), Operation::name(), Operation::numberOfInputs(), ProgramOperation::operation(), TTAMachine::BaseFUPort::parentUnit(), preSharedOperandPorts_, DataDependenceGraph::programOperation(), and DataDependenceGraph::programOperationCount().

Referenced by handleLoopDDG().

Here is the call graph for this function:

revertBBLiveRangeBookkeepingForDestination()

void BF2Scheduler::revertBBLiveRangeBookkeepingForDestination

(

MoveNode *

mn

)

Definition at line 703 of file BF2Scheduler.cc.

                                                                          {
    BasicBlockNode& bbn = ddg_->getBasicBlockNode(*mn);
    TTAProgram::Terminal& dest = mn->move().destination();
    if (!dest.isGPR()) {
        ddg().writeToDotFile("cannot_revert.dot");
        std::cerr << "Cannot revert bb live range bookkeeping as "
                  << " dest not gpr: " << mn->toString() << std::endl;
        std::cerr << "This might be caused by broken connectivity in the ADF."
                  << std::endl;
 
    }
    assert(dest.isGPR());
    int index = dest.index();
    const TTAMachine::RegisterFile& rf = dest.registerFile();
    TCEString reg = DisassemblyRegister::registerName(rf, index);
 
    eraseFromMoveNodeUseSet(
        bbn.basicBlock().liveRangeData_->regDefines_, reg, mn);
 
    eraseFromMoveNodeUseSet(
        bbn.basicBlock().liveRangeData_->regFirstDefines_, reg, mn);
}

References assert, BasicBlockNode::basicBlock(), ddg(), ddg_, TTAProgram::Move::destination(), eraseFromMoveNodeUseSet(), DataDependenceGraph::getBasicBlockNode(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::BasicBlock::liveRangeData_, MoveNode::move(), LiveRangeData::regDefines_, LiveRangeData::regFirstDefines_, TTAProgram::Terminal::registerFile(), DisassemblyRegister::registerName(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

revertBBLiveRangeBookkeepingForSource()

void BF2Scheduler::revertBBLiveRangeBookkeepingForSource

(

MoveNode *

mn

)

Definition at line 726 of file BF2Scheduler.cc.

                                                                     {
    BasicBlockNode& bbn = ddg_->getBasicBlockNode(*mn);
    TTAProgram::Terminal& src = mn->move().source();
    if (!src.isGPR()) {
        ddg().writeToDotFile("cannot_revert.dot");
        std::cerr << "Cannot revert bb live range bookkeeping as "
                  << " src not gpr: " << mn->toString() << std::endl;
        std::cerr << "This might be caused by broken connectivity in the ADF."
                  << std::endl;
    }
    assert(src.isGPR());
    int index = src.index();
    const TTAMachine::RegisterFile& rf = src.registerFile();
    TCEString reg = DisassemblyRegister::registerName(rf, index);
 
    eraseFromMoveNodeUseSet(
        bbn.basicBlock().liveRangeData_->regLastUses_, reg, mn);
 
    eraseFromMoveNodeUseSet(
        bbn.basicBlock().liveRangeData_->regFirstUses_, reg, mn);
}

References assert, BasicBlockNode::basicBlock(), ddg(), ddg_, eraseFromMoveNodeUseSet(), DataDependenceGraph::getBasicBlockNode(), TTAProgram::Terminal::index(), TTAProgram::Terminal::isGPR(), TTAProgram::BasicBlock::liveRangeData_, MoveNode::move(), LiveRangeData::regFirstUses_, TTAProgram::Terminal::registerFile(), DisassemblyRegister::registerName(), LiveRangeData::regLastUses_, TTAProgram::Move::source(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

revertTopOpt()

void BF2Scheduler::revertTopOpt ( )

private

Revert last optimization from the optimization stack.

Definition at line 1147 of file BF2Scheduler.cc.

                                {
    assert(!scheduledStack_.empty());
    BFOptimization* bfo = scheduledStack_.back();
    scheduledStack_.pop_back();
    bfo->undo();
    delete bfo;
}

References assert, scheduledStack_, and Reversible::undo().

Referenced by preAllocateFunctionUnits().

Here is the call graph for this function:

rm()

SimpleResourceManager & BF2Scheduler::rm ( )

inline

Definition at line 103 of file BF2Scheduler.hh.

{ return *rm_; }

References rm_.

Referenced by findBypassEdge(), handleDDG(), handleLoopDDG(), BFOptimization::rm(), and scheduleDDG().

scheduleDDG()

void BF2Scheduler::scheduleDDG	(	DataDependenceGraph &	ddg,
		SimpleResourceManager &	rm,
		const TTAMachine::Machine &	targetMachine
	)

Definition at line 143 of file BF2Scheduler.cc.

                                            {
 
    jumpGuardWrite_ = NULL;
 
    BFOptimization::clearPrologMoves();
    prologRM_ = NULL;
    preLoopSharedOperands_.clear();
 
    // scheduling pipeline resources after last cycle may cause problems.
    // make RM to check for those
    latestCycle_ = (INT_MAX/1024);
    rm.setMaxCycle(latestCycle_);
 
    targetMachine_ = &targetMachine;
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
    std::cerr << std::endl << "Handling new ddg: " << ddg.name() << std::endl;
#endif
    ddg_ = &ddg;
    ddg_->setMachine(targetMachine);
    if (duplicator_ != NULL) {
        delete duplicator_; duplicator_ = NULL;
    }
 
    BUMoveNodeSelector selector(ddg, targetMachine);
    selector_ = &selector;
    if (renamer_ != NULL) {
        renamer_->initialize(ddg);
        renamer_->setSelector(&selector);
    }
 
    rm_ = &rm;
 
    if (options_ != NULL && options_->dumpDDGsDot()) {
        ddg_->writeToDotFile(
            (boost::format("bb_%s_before_scheduling.dot") %
             ddg_->name()).str());
    }
 
    MoveNodeGroup moves = selector.candidates();
    while (moves.nodeCount() > 0) {
        MoveNode* mn = NULL;
        for (int i = 0; i < moves.nodeCount(); i++) {
            if (!moves.node(i).isScheduled()) {
                if (isDeadResult(moves.node(i))) {
                    if (ddg_->hasNode(moves.node(i))) {
                        ddg_->dropNode(moves.node(i));
                    }
                } else {
                    mn = &moves.node(i);
                }
            }
        }
        if (mn == NULL) {
            moves = selector.candidates();
            continue;
        }
 
        if (!scheduleFrontFromMove(*mn)) {
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
            std::cerr << "Scheduling of front failed! Inducing move: "
                      << mn->toString() << std::endl;
#endif
            ddg_->writeToDotFile(
                (boost::format("%s_failed_ddg.dot") %
                 ddg_->name()).str());
            throw CompileError(__FILE__, __LINE__, __func__,
                               "Bubblefish scheduler failed"
                               "retry count exceeded. Propably broken ADF");
        }
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "Whole op scheduled ok? original MN: "
                  << mn->toString() << std::endl;
#endif
        moves = selector.candidates();
    }
 
    if (ddg_->scheduledNodeCount() != ddg_->nodeCount()) {
        ddg_->writeToDotFile(
                (boost::format("%s_unscheduled_nodes_in_ddg.dot") %
                 ddg_->name()).str());
 
        assert(false && "unscheduled nodes in ddg after scheduler");
    }
 
    if (options_ != NULL && options_->dumpDDGsDot()) {
        ddg_->writeToDotFile(
            (boost::format("bb_%s_after_scheduler_ddg.dot") %
             ddg_->name()).str());
    }
 
    if (options_ != NULL && options_->dumpDDGsXML()) {
        ddg_->writeToXMLFile(
            (boost::format("bb_%s_after_scheduler_ddg.dot") %
             ddg_->name()).str());
    }
}

References __func__, assert, BUMoveNodeSelector::candidates(), SimpleResourceManager::clear(), BFOptimization::clearPrologMoves(), ddg(), ddg_, BoostGraph< GraphNode, GraphEdge >::dropNode(), LLVMTCECmdLineOptions::dumpDDGsDot(), LLVMTCECmdLineOptions::dumpDDGsXML(), duplicator_, BoostGraph< GraphNode, GraphEdge >::hasNode(), RegisterRenamer::initialize(), isDeadResult(), MoveNode::isScheduled(), jumpGuardWrite_, latestCycle_, BoostGraph< GraphNode, GraphEdge >::name(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), options_, preLoopSharedOperands_, prologRM_, renamer_, rm(), rm_, DataDependenceGraph::scheduledNodeCount(), scheduleFrontFromMove(), selector(), selector_, DataDependenceGraph::setMachine(), SimpleResourceManager::setMaxCycle(), RegisterRenamer::setSelector(), targetMachine(), targetMachine_, MoveNode::toString(), GraphBase< GraphNode, GraphEdge >::writeToDotFile(), and DataDependenceGraph::writeToXMLFile().

Referenced by handleDDG().

Here is the call graph for this function:

scheduleFrontFromMove()

int BF2Scheduler::scheduleFrontFromMove ( MoveNode &  mn )

private

Definition at line 1038 of file BF2Scheduler.cc.

                                                    {
    BF2ScheduleFront* bfsf = new BF2ScheduleFront(*this, mn, latestCycle_);
    currentFront_ = bfsf;
    if ((*bfsf)()) {
        scheduledStack_.push_back(bfsf);
        currentFront_ = NULL;
        return true;
    } else {
        delete bfsf;
        currentFront_ = NULL;
        return false;
    }
}

References currentFront_, latestCycle_, and scheduledStack_.

Referenced by handleLoopDDG(), and scheduleDDG().

selectMoveToSchedule()

MoveNode * BF2Scheduler::selectMoveToSchedule ( )

private

selector()

BUMoveNodeSelector & BF2Scheduler::selector ( )

inline

Definition at line 105 of file BF2Scheduler.hh.

{ return *selector_; }

References selector_.

Referenced by handleLoopDDG(), handleLoopDDG(), scheduleDDG(), and BFOptimization::selector().

setLoopLimits()

void BF2Scheduler::setLoopLimits ( LoopAnalyzer::LoopAnalysisResult *  llResult )

inline

Definition at line 202 of file BF2Scheduler.hh.

                                                                 {
        llResult_ = llResult;
    }

References llResult_.

shortDescription()

std::string BF2Scheduler::shortDescription ( ) const

overridevirtual

A short description of the pass, usually the optimization name, such as "basic block scheduler".

Returns

The description as a string.

Implements SchedulerPass.

Definition at line 887 of file BF2Scheduler.cc.

                                               {
    return "BubbleFish instruction Scheduler";
}

swapToUntrigger()

int BF2Scheduler::swapToUntrigger ( ProgramOperationPtr  po, const Operation &  op, int  operandIndex, MoveNode &  trig  )

private

Returns

new operand index of the operand. 0 if not swapped.

Definition at line 1099 of file BF2Scheduler.cc.

                                      {
    for (int i = 1; i <= op.numberOfInputs(); i++) {
        if (i == operandIndex) continue;
        if (op.canSwap(i, operandIndex)) {
            MoveNodeSet& inputNodeSet = po->inputNode(i);
            if (inputNodeSet.count() == 1) {
                BFSwapOperands* swapper =
                    new BFSwapOperands(*this, po, trig,
                                       inputNodeSet.at(0));
                if ((*swapper)()) {
                    scheduledStack_.push_back(swapper);
                    return i;
                    break;
                } else {
                    delete swapper;
                }
            }
        }
    }
    return 0;
}

References MoveNodeSet::at(), Operation::canSwap(), MoveNodeSet::count(), Operation::numberOfInputs(), and scheduledStack_.

Referenced by preAllocateFunctionUnits().

Here is the call graph for this function:

targetMachine()

const TTAMachine::Machine & BF2Scheduler::targetMachine ( ) const

inline

Definition at line 127 of file BF2Scheduler.hh.

{ return *targetMachine_; }

References targetMachine_.

Referenced by handleDDG(), handleLoopDDG(), BFEarlyBypasser::operator()(), preAllocateFunctionUnitsInner(), releasePortForOp(), scheduleDDG(), and BFOptimization::targetMachine().

tripCount()

int BF2Scheduler::tripCount ( )

inline

Definition at line 184 of file BF2Scheduler.hh.

{ return tripCount_; }

References tripCount_.

Referenced by handleLoopDDG().

undoPushAntideps()

void BF2Scheduler::undoPushAntideps ( MoveNode &  aDepSource )

private

unreservePreallocatedFUs()

void BF2Scheduler::unreservePreallocatedFUs ( )

private

Definition at line 1603 of file BF2Scheduler.cc.

                                            {
    for (int i = 0; i < ddg().nodeCount(); i++) {
        MoveNode& mn = ddg().node(i);
        TTAProgram::Move& m = mn.move();
 
        if (m.hasAnnotations(
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC) ||
            m.hasAnnotations(
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST)) {
 
            m.removeAnnotations(
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC);
            m.removeAnnotations(
                TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST);
        }
        m.removeAnnotations(
            TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC);
        m.removeAnnotations(
            TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST);
    }
}

References TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST, TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC, TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST, TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC, ddg(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), and TTAProgram::AnnotatedInstructionElement::removeAnnotations().

Referenced by handleLoopDDG(), and handleLoopDDG().

Here is the call graph for this function:

unschedule()

void BF2Scheduler::unschedule

(

)

Definition at line 780 of file BF2Scheduler.cc.

                              {
    while(!scheduledStack_.empty()) {
        BFOptimization* bfo = scheduledStack_.back();
        scheduledStack_.pop_back();
        currentFront_ = dynamic_cast<BF2ScheduleFront*>(bfo);
#ifdef DEBUG_BUBBLEFISH_SCHEDULER
        std::cerr << "unscheduling front @ " << bfo
                  << " in unschedule" << std::endl;
#endif
        bfo->undo();
        currentFront_ = NULL;
        delete bfo;
    }
}

References currentFront_, scheduledStack_, and Reversible::undo().

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

Here is the call graph for this function:

writeDotWithNameAndNodeID()

void BF2Scheduler::writeDotWithNameAndNodeID ( DataDependenceGraph &  ddg, const TCEString &  namePrefix, const MoveNode &  mn  )

staticprivate

Definition at line 696 of file BF2Scheduler.cc.

                                                             {
}

Member Data Documentation

bypassPredecessors_

DataDependenceGraph::NodeSet BF2Scheduler::bypassPredecessors_

private

Nodes that may become ready due bypass removing antideps.

Definition at line 244 of file BF2Scheduler.hh.

currentFront_

BF2ScheduleFront* BF2Scheduler::currentFront_

private

Definition at line 230 of file BF2Scheduler.hh.

Referenced by currentFront(), deletingNode(), scheduleFrontFromMove(), and unschedule().

ddg_

DataDependenceGraph* BF2Scheduler::ddg_

private

Definition at line 297 of file BF2Scheduler.hh.

Referenced by ddg(), ddg(), finalizeSchedule(), findBypassEdge(), findJump(), handleDDG(), handleLoopDDG(), handleLoopDDG(), hasUnscheduledSuccessors(), revertBBLiveRangeBookkeepingForDestination(), revertBBLiveRangeBookkeepingForSource(), and scheduleDDG().

dreRemovedMoves_

DataDependenceGraph::NodeSet BF2Scheduler::dreRemovedMoves_

private

Definition at line 236 of file BF2Scheduler.hh.

Referenced by finalizeSchedule(), isDeadResult(), nodeAndCopyKilled(), and nodeResurrected().

duplicator_

MoveNodeDuplicator* BF2Scheduler::duplicator_

private

Definition at line 315 of file BF2Scheduler.hh.

Referenced by duplicator(), handleDDG(), handleLoopDDG(), handleLoopDDG(), and scheduleDDG().

invariants_

std::multimap<TCEString, MoveNode*> BF2Scheduler::invariants_

private

Definition at line 317 of file BF2Scheduler.hh.

Referenced by allocateFunctionUnits(), and countLoopInvariantValueUsages().

invariantsOfCount_

std::multimap<int, TCEString> BF2Scheduler::invariantsOfCount_

private

Definition at line 318 of file BF2Scheduler.hh.

Referenced by allocateFunctionUnits(), and countLoopInvariantValueUsages().

jumpGuardWrite_

MoveNode* BF2Scheduler::jumpGuardWrite_

private

Definition at line 312 of file BF2Scheduler.hh.

Referenced by guardWriteNode(), handleLoopDDG(), and scheduleDDG().

jumpNode_

MoveNode* BF2Scheduler::jumpNode_

private

Definition at line 311 of file BF2Scheduler.hh.

Referenced by findJump(), handleLoopDDG(), jumpGuard(), and jumpNode().

killDeadResults_

bool BF2Scheduler::killDeadResults_

private

Definition at line 309 of file BF2Scheduler.hh.

Referenced by BF2Scheduler(), and killDeadResults().

latestCycle_

int BF2Scheduler::latestCycle_

private

Definition at line 302 of file BF2Scheduler.hh.

Referenced by handleLoopDDG(), handleLoopDDG(), maximumAllowedCycle(), scheduleDDG(), and scheduleFrontFromMove().

llResult_

LoopAnalyzer::LoopAnalysisResult* BF2Scheduler::llResult_

private

Definition at line 313 of file BF2Scheduler.hh.

Referenced by getLoopAnalysis(), loopLimitNode(), and setLoopLimits().

loopBufOps_

std::list<ProgramOperation*> BF2Scheduler::loopBufOps_

private

Definition at line 327 of file BF2Scheduler.hh.

Referenced by handleDDG(), and handleLoopDDG().

operandShareRemovedMoves_

MoveNodeMap BF2Scheduler::operandShareRemovedMoves_

private

Definition at line 240 of file BF2Scheduler.hh.

options_

LLVMTCECmdLineOptions* BF2Scheduler::options_

private

Definition at line 306 of file BF2Scheduler.hh.

Referenced by BF2Scheduler(), BF2Scheduler(), handleLoopDDG(), handleLoopDDG(), and scheduleDDG().

pendingMoves_

DataDependenceGraph::NodeSet BF2Scheduler::pendingMoves_

private

Definition at line 246 of file BF2Scheduler.hh.

preLoopSharedOperands_

std::map<MoveNode*, TTAMachine::FUPort*, MoveNode::Comparator> BF2Scheduler::preLoopSharedOperands_

private

Definition at line 325 of file BF2Scheduler.hh.

Referenced by allocateFunctionUnits(), handleLoopDDG(), handleLoopDDG(), isPreLoopSharedOperand(), and scheduleDDG().

preSharedOperandPorts_

std::multimap<TTAMachine::FUPort*, MoveNode*> BF2Scheduler::preSharedOperandPorts_

private

Definition at line 321 of file BF2Scheduler.hh.

Referenced by allocateFunctionUnits(), handleLoopDDG(), handleLoopDDG(), preAllocateFunctionUnits(), preAllocateFunctionUnits(), releasePortForOp(), and reservePreallocatedFUs().

PROLOG_CYCLE_BIAS

const int BF2Scheduler::PROLOG_CYCLE_BIAS = 1000

static

Definition at line 209 of file BF2Scheduler.hh.

Referenced by LoopPrologAndEpilogBuilder::addEpilogFromRM(), LoopPrologAndEpilogBuilder::addPrologFromRM(), BFOptimization::assignCopyToPrologEpilog(), BFOptimization::canAssign(), BFDRELoop::operator()(), BFSchedulePreLoopShared::operator()(), BFPostpassLoopDRE::operator()(), BFOptimization::rmEC(), and BFOptimization::rmLC().

prologDDG_

DataDependenceGraph* BF2Scheduler::prologDDG_

private

Definition at line 298 of file BF2Scheduler.hh.

Referenced by handleLoopDDG(), handleLoopDDG(), and prologDDG().

prologRM_

SimpleResourceManager* BF2Scheduler::prologRM_

private

Definition at line 300 of file BF2Scheduler.hh.

Referenced by finalizeSchedule(), handleLoopDDG(), handleLoopDDG(), prologRM(), and scheduleDDG().

removedMoves_

DataDependenceGraph::NodeSet BF2Scheduler::removedMoves_

private

Definition at line 238 of file BF2Scheduler.hh.

Referenced by finalizeSchedule(), isDeadResult(), nodeKilled(), and nodeResurrected().

renamer_

RegisterRenamer* BF2Scheduler::renamer_

private

Definition at line 307 of file BF2Scheduler.hh.

Referenced by handleLoopDDG(), renamer(), and scheduleDDG().

rm_

SimpleResourceManager* BF2Scheduler::rm_

private

Definition at line 299 of file BF2Scheduler.hh.

Referenced by handleDDG(), handleLoopDDG(), handleLoopDDG(), rm(), and scheduleDDG().

scheduledStack_

std::vector<BFOptimization*> BF2Scheduler::scheduledStack_

private

Definition at line 233 of file BF2Scheduler.hh.

Referenced by bypassNodes(), finalizeSchedule(), handleLoopDDG(), revertTopOpt(), scheduleFrontFromMove(), swapToUntrigger(), unschedule(), and ~BF2Scheduler().

selector_

BUMoveNodeSelector* BF2Scheduler::selector_

private

Definition at line 305 of file BF2Scheduler.hh.

Referenced by handleLoopDDG(), scheduleDDG(), and selector().

sharedOperands_

MoveNodeMap BF2Scheduler::sharedOperands_

private

Definition at line 241 of file BF2Scheduler.hh.

targetMachine_

const TTAMachine::Machine* BF2Scheduler::targetMachine_

private

Definition at line 304 of file BF2Scheduler.hh.

Referenced by handleLoopDDG(), mustBeTrigger(), scheduleDDG(), and targetMachine().

tripCount_

int BF2Scheduler::tripCount_

private

Definition at line 310 of file BF2Scheduler.hh.

Referenced by handleLoopDDG(), handleLoopDDG(), and tripCount().

---

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

• BF2Scheduler.hh
• BF2Scheduler.cc