OpenASIP  2.0
Classes | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | List of all members
BUBasicBlockScheduler Class Reference

#include <BUBasicBlockScheduler.hh>

Inheritance diagram for BUBasicBlockScheduler:
Inheritance graph
Collaboration diagram for BUBasicBlockScheduler:
Collaboration graph

Classes

struct  ltstr
 

Public Member Functions

 BUBasicBlockScheduler (InterPassData &data, SoftwareBypasser *bypasser=NULL, RegisterRenamer *registerRenamer=NULL)
 
virtual ~BUBasicBlockScheduler ()
 
virtual int handleDDG (DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine, int minCycle=0, bool testOnly=false)
 
virtual int handleLoopDDG (DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine, int tripCount, SimpleResourceManager *prologRM=NULL, bool testOnly=false)
 
virtual std::string shortDescription () const
 
virtual std::string longDescription () const
 
virtual DataDependenceGraphBuilderddgBuilder ()
 
- Public Member Functions inherited from BasicBlockScheduler
 BasicBlockScheduler (InterPassData &data, SoftwareBypasser *bypasser=NULL, RegisterRenamer *renamer=NULL)
 
virtual ~BasicBlockScheduler ()
 
virtual void printStats () const
 
virtual DataDependenceGraphBuilderddgBuilder ()
 
- Public Member Functions inherited from DDGPass
 DDGPass (InterPassData &data)
 
virtual ~DDGPass ()
 
- Public Member Functions inherited from SchedulerPass
 SchedulerPass (InterPassData &data)
 
virtual ~SchedulerPass ()
 
InterPassDatainterPassData ()
 
- Public Member Functions inherited from BasicBlockPass
 BasicBlockPass (InterPassData &data)
 
virtual ~BasicBlockPass ()
 
virtual void handleBasicBlock (TTAProgram::BasicBlock &basicBlock, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, BasicBlockNode *bbn=NULL)
 
virtual void executeDDGPass (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)
 
virtual bool executeLoopPass (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)
 
virtual DataDependenceGraphBuilderddgBuilder ()
 

Protected Types

typedef std::set< MoveNode *, ltstrOrderedSet
 

Protected Member Functions

void scheduleRRMove (MoveNode &moveNode)
 
void scheduleOperation (MoveNodeGroup &moves, BUMoveNodeSelector &selector)
 
bool scheduleOperandWrites (MoveNodeGroup &moves, int cycle)
 
int scheduleResultReads (MoveNodeGroup &moves, int cycle, bool bypass=false, bool bypassLate=false)
 
void scheduleMove (MoveNode &move, int cycle, bool allowPredicationandRenaming)
 
void scheduleResultReadTempMoves (MoveNode &resultMove, MoveNode &resultRead, int lastUse)
 
void scheduleInputOperandTempMoves (MoveNode &resultMove, MoveNode &resultRead)
 
void scheduleRRTempMoves (MoveNode &regToRegMove, MoveNode &firstMove, int lastUse)
 
bool scheduleOperand (MoveNode &, int cycle)
 
bool tryToSwitchInputs (ProgramOperation &op)
 
bool tryToOptimizeWaw (const MoveNode &moveNode)
 
MoveNodeprecedingTempMove (MoveNode &current)
 
OrderedSet findBypassDestinations (MoveNode &node)
 
void undoBypass (MoveNode &node, MoveNode *single=NULL, int originalCycle=-1)
 
bool bypassNode (MoveNode &node, int &maxResultCycle)
 
void finalizeSchedule (MoveNode &node, BUMoveNodeSelector &selector)
 
void unscheduleAllNodes ()
 
void clearRemovedNodes ()
 
- Protected Member Functions inherited from BasicBlockScheduler
void scheduleRRMove (MoveNode &moveNode)
 
void scheduleOperation (MoveNodeGroup &moves)
 
int scheduleOperandWrites (int &cycle, MoveNodeGroup &moves)
 
bool scheduleResultReads (MoveNodeGroup &moves)
 
void scheduleMove (MoveNode &move, int earliestCycle, bool allowPredicationAndRenaming)
 
void scheduleRRTempMoves (MoveNode &regToRegMove, MoveNode &firstMove, int lastUse)
 
void scheduleInputOperandTempMoves (MoveNode &operandMove, MoveNode &operandWrite)
 
void unschedule (MoveNode &moveNode)
 
void unscheduleAllNodes ()
 
void unscheduleInputOperandTempMoves (MoveNode &operandMove)
 
void scheduleResultReadTempMoves (MoveNode &resultMove, MoveNode &resultRead, int lastUse)
 
void unscheduleResultReadTempMoves (MoveNode &resultMove)
 
void notifyScheduled (MoveNodeGroup &moves, MoveNodeSelector &selector)
 
void ddgSnapshot (DataDependenceGraph &ddg, const std::string &name, DataDependenceGraph::DumpFileFormat format, bool final, bool resetCounter=false) const
 
MoveNodesucceedingTempMove (MoveNode &current)
 
int getTriggerOperand (const Operation &operation, const TTAMachine::Machine &machine)
 
bool tryToSwitchInputs (ProgramOperation &op)
 
void handleRemovedResultMoves (std::set< std::pair< TTAProgram::Move *, int > > removedMoves)
 
bool tryToOptimizeWaw (const MoveNode &moveNode)
 
void tryToDelayOperands (MoveNodeGroup &moves)
 
- Protected Member Functions inherited from BasicBlockPass
void ddgSnapshot (DataDependenceGraph *ddg, std::string &name, DataDependenceGraph::DumpFileFormat format, bool final)
 
virtual DataDependenceGraphcreateDDGFromBB (TTAProgram::BasicBlock &bb, const TTAMachine::Machine &mach)
 

Protected Attributes

MoveNodejumpMove_
 
std::map< MoveNode *, std::vector< MoveNode * >, MoveNode::ComparatorbypassDestinations_
 
std::map< MoveNode *, std::vector< int >, MoveNode::ComparatorbypassDestinationsCycle_
 
std::map< MoveNode *, std::vector< const TTAMachine::Bus * >, MoveNode::ComparatorbypassDestinationsBus_
 
std::set< MoveNode * > droppedNodes_
 
unsigned int endCycle_
 
bool bypass_
 
bool dre_
 
int bypassDistance_
 
- Protected Attributes inherited from BasicBlockScheduler
const TTAMachine::MachinetargetMachine_
 The target machine we are scheduling the program against. More...
 
DataDependenceGraphddg_
 DDG of the currently scheduled BB. More...
 
SimpleResourceManagerrm_
 Resource Manager of the currently scheduled BB. More...
 
std::map< const MoveNode *, DataDependenceGraph::NodeSetscheduledTempMoves_
 Stores the MoveNodes that were scheduled as temp moves during scheduling of the operand move. More...
 
SoftwareBypassersoftwareBypasser_
 The software bypasser to use to bypass registers when possible. More...
 
RegisterRenamerrenamer_
 
int minCycle_
 The earliest cycle to schedule moves in. Used to leave room for sched_yield() by the sched_yield() emitter. More...
 
MoveNodeSelectorselector_
 
boost::timer schedulingTime_
 Time for getting the scheduling time for current basic block. More...
 
int bypassedCount_
 
int deadResults_
 
LLVMTCECmdLineOptionsoptions_
 
MoveNodejumpNode_
 
int tripCount_
 

Additional Inherited Members

- Static Public Member Functions inherited from BasicBlockScheduler
static MoveNodefindTrigger (const ProgramOperation &po, const TTAMachine::Machine &mach)
 
- Static Public Member Functions inherited from BasicBlockPass
static void copyRMToBB (SimpleResourceManager &rm, TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, int lastCycle=-1)
 
- Static Protected Member Functions inherited from BasicBlockScheduler
static MoveNodefindTriggerFromUnit (const ProgramOperation &po, const TTAMachine::Unit &unit)
 

Detailed Description

A class that implements the functionality of a bottom up basic block scheduler.

Schedules the program one basic block at a time. Does not fill delay slots if they couldn't be filled with the basic block's contents itself (no instruction importing).

Definition at line 61 of file BUBasicBlockScheduler.hh.

Member Typedef Documentation

◆ OrderedSet

typedef std::set<MoveNode*, ltstr> BUBasicBlockScheduler::OrderedSet
protected

Definition at line 97 of file BUBasicBlockScheduler.hh.

Constructor & Destructor Documentation

◆ BUBasicBlockScheduler()

BUBasicBlockScheduler::BUBasicBlockScheduler ( InterPassData data,
SoftwareBypasser bypasser = NULL,
RegisterRenamer renamer = NULL 
)

Constructs the basic block scheduler.

Parameters
dataInterpass data
bypasserHelper module implementing software bypassing
delaySlotFillerHelper module implementing jump delay slot filling
registerRenamerHelper module implementing register renaming

Definition at line 86 of file BUBasicBlockScheduler.cc.

89  :
90  BasicBlockScheduler(data, bypasser, renamer),
91  endCycle_(INT_MAX), bypass_(true), dre_(true), bypassDistance_(3) {
92 
93  CmdLineOptions *cmdLineOptions = Application::cmdLineOptions();
94  options_ = dynamic_cast<LLVMTCECmdLineOptions*>(cmdLineOptions);
95  jumpMove_ = NULL;
96 }

References Application::cmdLineOptions(), jumpMove_, and BasicBlockScheduler::options_.

Here is the call graph for this function:

◆ ~BUBasicBlockScheduler()

BUBasicBlockScheduler::~BUBasicBlockScheduler ( )
virtual

Destructor.

Definition at line 101 of file BUBasicBlockScheduler.cc.

101  {
102 }

Member Function Documentation

◆ bypassNode()

bool BUBasicBlockScheduler::bypassNode ( MoveNode moveNode,
int &  maxResultCycle 
)
protected

Tries to bypass node with all of it's successors.

Parameters
moveNode,nodewhich is tried to bypass
maxResultCycle,cycleof latest of rescheduled nodes
Returns
True if all of the successors were successfully bypassed

Definition at line 1602 of file BUBasicBlockScheduler.cc.

1604  {
1605  bool edgesCopied = false;
1606  unsigned int bypassCount = 0;
1607  int localMaximum = 0;
1608  if (!bypass_)
1609  return false;
1610  // First try to bypass all uses of the result
1611  unsigned int rawDestinations =
1612  ddg_->onlyRegisterRawDestinations(moveNode, false, false).size();
1613  OrderedSet destinations =
1614  findBypassDestinations(moveNode);
1615  if (destinations.size() > 0) {
1616  for (OrderedSet::iterator it = destinations.begin();
1617  it != destinations.end(); it++) {
1618  if (!ddg_->guardsAllowBypass(moveNode, **it)) {
1619  continue;
1620  }
1621  MoveNode* temp = succeedingTempMove(moveNode);
1622  if (!(*it)->isScheduled() && temp == (*it)) {
1623  // skip temp moves if unscheduled.
1624  // The temp moves of reading operand could be
1625  // scheduled and bypass will try to skip those
1626  // but temp moves of result are there for reason
1627  // so bypass would only revert to original
1628  // status which is unschedulable.
1629  std::cerr << "\t\tSkipping temporary outgoing move " <<
1630  (*it)->toString() << std::endl;
1631  continue;
1632  }
1633  assert((*it)->isScheduled());
1634  int originalCycle = (*it)->cycle();
1635  int latestLimit = originalCycle + bypassDistance_;
1636  int earliestLimit = originalCycle - bypassDistance_;
1637  if ((*it)->isDestinationVariable() && temp == (*it)) {
1638  // If bypassing to temporary register
1639  // missing edges in DDG could cause
1640  // overwrite of temporary value before it is
1641  // consumed.
1642  // Find previous and following reads from temp
1643  // register around location of original temp write.
1644  MoveNode* lastRead =
1646  (*it)->move().destination().registerFile(),
1647  (*it)->move().destination().index(),
1648  originalCycle);
1649  if (lastRead != NULL) {
1650  assert(lastRead->isScheduled());
1651  earliestLimit = lastRead->cycle();
1652  }
1653  MoveNode *firstRead =
1655  (*it)->move().destination().registerFile(),
1656  (*it)->move().destination().index(),
1657  originalCycle);
1658  if (firstRead != NULL) {
1659  assert(firstRead->isScheduled());
1660  latestLimit = firstRead->cycle();
1661  }
1662  }
1663 
1664 #ifdef DEBUG_BYPASS
1665  ddg_->writeToDotFile("beforeUnschedule.dot");
1666 #endif
1667  const TTAMachine::Bus* bus = &(*it)->move().bus();
1668  bypassDestinationsBus_[&moveNode].push_back(
1669  dynamic_cast<const TTAMachine::Bus*>(bus));
1670  unschedule(**it);
1671  if (!ddg_->mergeAndKeepUser(moveNode, **it)) {
1672  assert(!(*it)->isScheduled());
1673  scheduleMove(**it, originalCycle, true);
1674 #ifdef DEBUG_BYPASS
1675  std::cerr << "Merge fail. moveNode=" << moveNode.toString()
1676  << ", **it=" << (*it)->toString() << std::endl;
1677 #endif
1678  bypassDestinationsBus_[&moveNode].pop_back();
1679  continue;
1680  }
1681 
1682  if ((**it).move().source().isImmediateRegister()) {
1683  (**it).move().setSource(
1684  static_cast<SimpleResourceManager*>(rm_)->immediateValue(moveNode)->copy());
1685  }
1686 
1687  bypassDestinations_[&moveNode].push_back(*it);
1688  bypassDestinationsCycle_[&moveNode].push_back(
1689  originalCycle);
1690  assert((*it)->isScheduled() == false);
1691  int startCycle = std::min(latestLimit, maxResultCycle);
1692  scheduleMove(**it, startCycle, true);
1693 
1694 #ifdef DEBUG_BYPASS
1695  std::cerr << "\t\t\tCreated " << (*it)->toString()
1696  << " with original cycle " << originalCycle << std::endl;
1697 #endif
1698  if (!(*it)->isScheduled() ||
1699  (*it)->cycle() > latestLimit ||
1700  (*it)->cycle() < earliestLimit ||
1701  (*it)->cycle() < originalCycle) {
1702  // Scheduling bypass failed, undo and try to
1703  // schedule other possible bypasses.
1704  undoBypass(moveNode, *it, originalCycle);
1705  bypassDestinations_[&moveNode].pop_back();
1706  bypassDestinationsCycle_[&moveNode].pop_back();
1707  bypassDestinationsBus_[&moveNode].pop_back();
1708  } else {
1709  localMaximum =
1710  ((*it)->cycle() > localMaximum) ?
1711  (*it)->cycle() : localMaximum;
1712  if (!edgesCopied) {
1713  // In case operands reads same register that
1714  // result writes, removing result move after
1715  // successfull bypass could lead to operand
1716  // scheduled after the register it reads is
1717  // overwriten. This should prevent such situation.
1718  ddg_->copyDepsOver(moveNode, true, true);
1719  edgesCopied = true;
1720  }
1721  bypassCount++;
1722  }
1723  }
1724  } else {
1725  DataDependenceGraph::NodeSet rrDestinations =
1726  ddg_->onlyRegisterRawDestinations(moveNode, false, false);
1727  if (rrDestinations.size() == 0 &&
1728  moveNode.isDestinationVariable() &&
1729  moveNode.isSourceVariable() &&
1730  !ddg_->resultUsed(moveNode)) {
1731  // move is not used at all anywhere? Lets try to drop it
1732  return true;
1733  }
1734  }
1735  if (bypassCount == rawDestinations && bypassCount != 0) {
1736  maxResultCycle = localMaximum;
1737  return true;
1738  } else {
1739  return false;
1740  }
1741 }

References assert, bypass_, bypassDestinations_, bypassDestinationsBus_, bypassDestinationsCycle_, bypassDistance_, DataDependenceGraph::copyDepsOver(), MoveNode::cycle(), BasicBlockScheduler::ddg_, findBypassDestinations(), DataDependenceGraph::firstScheduledRegisterRead(), DataDependenceGraph::guardsAllowBypass(), MoveNode::isDestinationVariable(), MoveNode::isScheduled(), MoveNode::isSourceVariable(), DataDependenceGraph::lastScheduledRegisterRead(), DataDependenceGraph::mergeAndKeepUser(), DataDependenceGraph::onlyRegisterRawDestinations(), DataDependenceGraph::resultUsed(), BasicBlockScheduler::rm_, scheduleMove(), BasicBlockScheduler::succeedingTempMove(), MoveNode::toString(), undoBypass(), BasicBlockScheduler::unschedule(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by handleDDG(), handleLoopDDG(), scheduleResultReads(), scheduleResultReadTempMoves(), and scheduleRRTempMoves().

Here is the call graph for this function:

◆ clearRemovedNodes()

void BUBasicBlockScheduler::clearRemovedNodes ( )
protected

Finaly, remove moves that were dropped during dead result move elimination also from the parent of the given subgraph DDG.

Definition at line 1874 of file BUBasicBlockScheduler.cc.

1874  {
1875 
1876  for (std::set<MoveNode*>::iterator i = droppedNodes_.begin();
1877  i != droppedNodes_.end(); i++) {
1878  MoveNode& node = **i;
1879  if (ddg_->rootGraph() != ddg_ && !node.isScheduled()) {
1880  ddg_->rootGraph()->removeNode(node);
1882  bypassDestinations_.erase(&node);
1883  bypassDestinationsCycle_.erase(&node);
1884  bypassDestinationsBus_.erase(&node);
1885  }
1886  }
1887  }
1888  droppedNodes_.clear();
1889 }

References bypassDestinations_, bypassDestinationsBus_, bypassDestinationsCycle_, MapTools::containsKey(), BasicBlockScheduler::ddg_, droppedNodes_, MoveNode::isScheduled(), BoostGraph< GraphNode, GraphEdge >::removeNode(), and BoostGraph< GraphNode, GraphEdge >::rootGraph().

Referenced by handleDDG(), and handleLoopDDG().

Here is the call graph for this function:

◆ ddgBuilder()

virtual DataDependenceGraphBuilder& BasicBlockPass::ddgBuilder
inline

Definition at line 86 of file BasicBlockPass.hh.

86 { return ddgBuilder_; }

◆ finalizeSchedule()

void BUBasicBlockScheduler::finalizeSchedule ( MoveNode node,
BUMoveNodeSelector selector 
)
protected

Definition at line 1744 of file BUBasicBlockScheduler.cc.

1745  {
1746  if (node.isScheduled()) {
1747  selector.notifyScheduled(node);
1748  std::map<const MoveNode*, DataDependenceGraph::NodeSet >::
1749  iterator tmIter = scheduledTempMoves_.find(&node);
1750  if (tmIter != scheduledTempMoves_.end()) {
1751  DataDependenceGraph::NodeSet& tempMoves = tmIter->second;
1752  for (DataDependenceGraph::NodeSet::iterator i =
1753  tempMoves.begin(); i != tempMoves.end(); i++) {
1754  selector.notifyScheduled(**i);
1755  }
1756  }
1757  } else if (MapTools::containsKey(bypassDestinations_, &node) && dre_) {
1758 
1759 #ifdef DEBUG_BYPASS
1760  std::cerr << "\tDroping node " << node.toString() << std::endl;
1761  ddg_->writeToDotFile("before_copyDeps.dot");
1762 #endif
1763  static_cast<DataDependenceGraph*>(ddg_->rootGraph())->
1764  copyDepsOver(node, true, true);
1766  ddg_->dropNode(node);
1767  droppedNodes_.insert(&node);
1768 #ifdef DEBUG_BYPASS
1769  ddg_->writeToDotFile("after_dropNode.dot");
1770 #endif
1771 
1772  for (DataDependenceGraph::NodeSet::iterator i =
1773  preds.begin(); i != preds.end(); i++) {
1774  selector.mightBeReady(**i);
1775  }
1776  std::map<const MoveNode*, DataDependenceGraph::NodeSet >::
1777  iterator tmIter = scheduledTempMoves_.find(&node);
1778  if (tmIter != scheduledTempMoves_.end()) {
1779  DataDependenceGraph::NodeSet& tempMoves = tmIter->second;
1780  for (DataDependenceGraph::NodeSet::iterator i =
1781  tempMoves.begin(); i != tempMoves.end(); i++) {
1782  if ((*i)->isScheduled()) {
1783  selector.notifyScheduled(**i);
1784  } else {
1785 #ifdef DEBUG_BYPASS
1786  std::cerr << "\tDroping temp move for node "
1787  << node.toString() << ", " << (*i)->toString()
1788  << std::endl;
1789  ddg_->writeToDotFile("before_temp_copyDeps.dot");
1790 #endif
1791  static_cast<DataDependenceGraph*>(ddg_->rootGraph())->
1792  copyDepsOver(**i, true, true);
1793  ddg_->dropNode(**i);
1794  droppedNodes_.insert(*i);
1795 #ifdef DEBUG_BYPASS
1796  ddg_->writeToDotFile("after_temp_dropNode.dot");
1797 #endif
1798  }
1799  }
1800  }
1801  } else if (node.move().source().equals(node.move().destination()) ||
1802  (node.isSourceVariable()
1803  && node.isDestinationVariable()
1804  && !ddg_->resultUsed(node))) {
1805 
1806  // we lost edges so our notifyScheduled does not notify
1807  // some antidependencies. store them for notification.
1808 
1809  DataDependenceGraph::NodeSet predecessors =
1810  ddg_->predecessors(node);
1811  predecessors.erase(&node); // if WaW to itself, rremove it.
1812 
1813  assert(node.isScheduled() == false);
1814 
1815  // this may lead to extra raw edges.
1816  static_cast<DataDependenceGraph*>(ddg_->rootGraph())->
1817  copyDepsOver(node, true, true);
1818 
1819  ddg_->dropNode(node);
1820  droppedNodes_.insert(&node);
1821  // we lost edges so our notifyScheduled does not notify
1822  // some antidependencies. notify them.
1823  for (DataDependenceGraph::NodeSet::iterator iter =
1824  predecessors.begin();
1825  iter != predecessors.end(); iter++) {
1826  selector.mightBeReady(**iter);
1827  }
1828 
1829  } else {
1830  TCEString msg = "Node " + node.toString() + " did not get scheduled";
1831  ddg_->writeToDotFile("after_dropNode.dot");
1832  throw InvalidData(
1833  __FILE__, __LINE__, __func__, msg);
1834  }
1835 }

References __func__, assert, bypassDestinations_, MapTools::containsKey(), BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), dre_, BoostGraph< GraphNode, GraphEdge >::dropNode(), droppedNodes_, TTAProgram::Terminal::equals(), MoveNode::isDestinationVariable(), MoveNode::isScheduled(), MoveNode::isSourceVariable(), BUMoveNodeSelector::mightBeReady(), MoveNode::move(), BUMoveNodeSelector::notifyScheduled(), BoostGraph< GraphNode, GraphEdge >::predecessors(), DataDependenceGraph::resultUsed(), BoostGraph< GraphNode, GraphEdge >::rootGraph(), BasicBlockScheduler::scheduledTempMoves_, TTAProgram::Move::source(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by handleDDG(), handleLoopDDG(), scheduleOperation(), scheduleResultReadTempMoves(), and scheduleRRTempMoves().

Here is the call graph for this function:

◆ findBypassDestinations()

BUBasicBlockScheduler::OrderedSet BUBasicBlockScheduler::findBypassDestinations ( MoveNode node)
protected

Finds a destination where to bypass.

Goes through ddg and checks for connectivity.

Returns
pair of destination of bypass and amount of regs skipped by the bypass.

Definition at line 1488 of file BUBasicBlockScheduler.cc.

1488  {
1489 
1490  OrderedSet okDestination;
1491  // DDG can only handle single hops so far.
1492  // TODO: Fix when DDG could handle multiple destinations
1493  DataDependenceGraph::NodeSet rrDestinations =
1494  ddg_->onlyRegisterRawDestinations(node, false, false);
1495  for (DataDependenceGraph::NodeSet::iterator j =
1496  rrDestinations.begin(); j != rrDestinations.end(); j++) {
1497  MoveNode* n = *j;
1498  if (ddg_->onlyRegisterRawSource(*n) == NULL) {
1499  // No bypassing of moves with multiple register definition
1500  // sources.
1501  // TODO: bypass destination with multiple definition sources
1502  // using inverse guard of guarded source.
1503  continue;
1504  }
1505  MachineConnectivityCheck::PortSet destinationPorts;
1506  destinationPorts.insert(&n->move().destination().port());
1507 
1509  node, destinationPorts)) {
1510  if (n->isScheduled() == false
1511  && rm_->initiationInterval() != 0) {
1512  // Found node connected by loop edge, ignore it.
1513  ddg_->writeToDotFile("failing_test.dot");
1514  continue;
1515  }
1516  okDestination.insert(n);
1517  }
1518  destinationPorts.clear();
1519  }
1520  return okDestination;
1521 }

References MachineConnectivityCheck::canSourceWriteToAnyDestinationPort(), BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), SimpleResourceManager::initiationInterval(), MoveNode::isScheduled(), MoveNode::move(), DataDependenceGraph::onlyRegisterRawDestinations(), DataDependenceGraph::onlyRegisterRawSource(), TTAProgram::Terminal::port(), BasicBlockScheduler::rm_, and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by bypassNode().

Here is the call graph for this function:

◆ handleDDG()

int BUBasicBlockScheduler::handleDDG ( DataDependenceGraph ddg,
SimpleResourceManager rm,
const TTAMachine::Machine targetMachine,
int  minCycle = 0,
bool  test = false 
)
virtual

Schedules a piece of code in a DDG

Parameters
ddgThe ddg containing the code
rmResource manager that is to be used.
targetMachineThe target machine.
Exceptions
Exceptionseveral TCE exceptions can be thrown in case of a scheduling error.

Reimplemented from BasicBlockScheduler.

Definition at line 113 of file BUBasicBlockScheduler.cc.

115  {
116  ddg_ = &ddg;
117  targetMachine_ = &targetMachine;
118 
119  if (renamer_ != NULL) {
120  renamer_->initialize(ddg);
121  }
122 
123  if (options_ != NULL && options_->dumpDDGsDot()) {
124  ddgSnapshot(
125  ddg, std::string("0"), DataDependenceGraph::DUMP_DOT, false);
126  }
127 
128  if (options_ != NULL && options_->dumpDDGsXML()) {
129  ddgSnapshot(
130  ddg, std::string("0"), DataDependenceGraph::DUMP_XML, false);
131  }
132 
133  if (options_ != NULL && options_->bypassDistance() > -1) {
135  }
136 
137  if (options_ != NULL && options_->bypassDistance() == 0) {
138  bypass_ = false;
139  }
140 
141  if (options_ != NULL && !options_->killDeadResults()) {
142  dre_ = false;
143  }
144 
145  // empty need not to be scheduled
146  if (ddg.nodeCount() == 0 ||
147  (ddg.nodeCount() == 1 && !ddg.node(0).isMove())) {
148  return 0;
149  }
150 
151  // INT_MAX/2 won't work on trunk due to multithreading injecting empty
152  // instructions into the beginning of basic block.
153  endCycle_ = INT_MAX/1000;
154 
155  // scheduling pipeline resources after last cycle may cause problems.
156  // make RM to check for those
158 
159  BUMoveNodeSelector selector(ddg, targetMachine);
160  selector_ = &selector;
161  // register selector to renamer for notfications.
162  if (renamer_ != NULL) {
163  renamer_->setSelector(&selector);
164  }
165 
166  rm_ = &rm;
167 
168  MoveNodeGroup moves = selector.candidates();
169  while (moves.nodeCount() > 0) {
170  bool movesRemoved = false;
171  MoveNode& firstMove = moves.node(0);
172  if (firstMove.isOperationMove()) {
173  scheduleOperation(moves, selector);
174  movesRemoved = true;
175  } else {
176  if (firstMove.move().destination().isRA()) {
177  scheduleMove(firstMove, endCycle_, true);
178  finalizeSchedule(firstMove, selector);
179  } else {
180  int tmp = endCycle_;
181  if (bypassNode(firstMove,tmp) && dre_
182  &&!ddg_->resultUsed(firstMove)) {
183  // No need to schedule original move any more
184  movesRemoved = true;
185  } else {
186  // schedule original move
187  scheduleRRMove(firstMove);
188  // If move was register copy to self, it could have been
189  // just dropped.
190  movesRemoved = true;
191  if (!firstMove.isScheduled()) {
192  undoBypass(firstMove);
193  scheduleRRMove(firstMove);
194  }
195  }
196  if (bypass_) {
197  bypassNode(firstMove, tmp);
198  }
199  finalizeSchedule(firstMove, selector);
200  }
201  }
202  if (!movesRemoved) {
203  if (!moves.isScheduled()) {
204  std::string message = " Move(s) did not get scheduled: ";
205  for (int i = 0; i < moves.nodeCount(); i++) {
206  message += moves.node(i).toString() + " ";
207  }
208  ddg.writeToDotFile("failed_bb.dot");
209  throw ModuleRunTimeError(__FILE__,__LINE__,__func__, message);
210  }
211  }
212  moves = selector.candidates();
213  if (!test)
215  }
216 
217  if (ddg.nodeCount() != ddg.scheduledNodeCount()) {
218  debugLog("All moves in the DDG didn't get scheduled.");
219  ddg.writeToDotFile("failed_bb.dot");
220  abortWithError("Should not happen!");
221  }
222 
223  if (options_ != NULL && options_->dumpDDGsDot()) {
224  std::string wtf = "0";
225  ddgSnapshot(
226  ddg, wtf, DataDependenceGraph::DUMP_DOT, true);
227  }
228 
229  if (options_ != NULL && options_->dumpDDGsXML()) {
230  ddgSnapshot(
231  ddg, std::string("0"), DataDependenceGraph::DUMP_XML, true);
232  }
233  if (rm_->largestCycle() > (int)endCycle_) {
234  ddg.writeToDotFile("largest_bigger_than_endcycle.dot");
235  std::cerr << "rm largest cycle bigger than endCycle_!" <<
236  std::endl << "This may break delay slot filler!" <<
237  std::endl << " rm largest: " << rm_->largestCycle() <<
238  " end cycle: " << endCycle_ << std::endl;
239 
240  abortWithError("Should not happen!");
241  }
242  int size = rm_->largestCycle() - rm_->smallestCycle();
243  if (test) {
245  }
246  return size;
247 }

References __func__, abortWithError, bypass_, SchedulerCmdLineOptions::bypassDistance(), bypassDistance_, bypassNode(), BUMoveNodeSelector::candidates(), clearRemovedNodes(), BasicBlockScheduler::ddg_, BasicBlockScheduler::ddgSnapshot(), debugLog, TTAProgram::Move::destination(), dre_, DataDependenceGraph::DUMP_DOT, DataDependenceGraph::DUMP_XML, LLVMTCECmdLineOptions::dumpDDGsDot(), LLVMTCECmdLineOptions::dumpDDGsXML(), endCycle_, finalizeSchedule(), RegisterRenamer::initialize(), MoveNode::isMove(), MoveNode::isOperationMove(), TTAProgram::Terminal::isRA(), MoveNodeGroup::isScheduled(), MoveNode::isScheduled(), SchedulerCmdLineOptions::killDeadResults(), SimpleResourceManager::largestCycle(), MoveNode::move(), MoveNodeGroup::node(), BoostGraph< GraphNode, GraphEdge >::node(), MoveNodeGroup::nodeCount(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), BasicBlockScheduler::options_, BasicBlockScheduler::renamer_, DataDependenceGraph::resultUsed(), BasicBlockScheduler::rm_, DataDependenceGraph::scheduledNodeCount(), scheduleMove(), scheduleOperation(), scheduleRRMove(), BasicBlockScheduler::selector_, SimpleResourceManager::setMaxCycle(), RegisterRenamer::setSelector(), SimpleResourceManager::smallestCycle(), BasicBlockScheduler::targetMachine_, MoveNode::toString(), undoBypass(), unscheduleAllNodes(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

◆ handleLoopDDG()

int BUBasicBlockScheduler::handleLoopDDG ( DataDependenceGraph ddg,
SimpleResourceManager rm,
const TTAMachine::Machine targetMachine,
int  tripCount,
SimpleResourceManager prologRM = NULL,
bool  testOnly = false 
)
virtual

Schedules loop in a DDG

Parameters
ddgThe ddg containing the loop
rmResource manager that is to be used.
targetMachineThe target machine.
Exceptions
Exceptionseveral TCE exceptions can be thrown in case of a scheduling error.
Returns
negative if failed, else overlapcount.

Reimplemented from BasicBlockScheduler.

Definition at line 260 of file BUBasicBlockScheduler.cc.

263  {
264  tripCount_ = tripCount;
265  ddg_ = &ddg;
266  targetMachine_ = &targetMachine;
267  minCycle_ = 0;
268  schedulingTime_.restart();
269 
270  if (renamer_ != NULL) {
271  renamer_->initialize(ddg);
272  }
273 
274  if (options_ != NULL && options_->dumpDDGsDot()) {
275  ddgSnapshot(
276  ddg, std::string("0"), DataDependenceGraph::DUMP_DOT, false, true);
277  }
278 
279  if (options_ != NULL && options_->dumpDDGsXML()) {
280  ddgSnapshot(
281  ddg, std::string("0"), DataDependenceGraph::DUMP_XML, false, true);
282  }
283 
284  if (options_ != NULL && options_->bypassDistance() > -1) {
286  }
287 
288  if (options_ != NULL && options_->bypassDistance() == 0) {
289  bypass_ = false;
290  }
291 
292  if (options_ != NULL && !options_->killDeadResults()) {
293  dre_ = false;
294  }
295 
296  scheduledTempMoves_.clear();
297 
298  // empty DDGs can be ignored
299  if (ddg.nodeCount() == 0 ||
300  (ddg.nodeCount() == 1 && !ddg.node(0).isMove())) {
301  return 0;
302  }
303  endCycle_ = 2 * rm.initiationInterval() - 1;
304  BUMoveNodeSelector selector(ddg, targetMachine);
305 
306  rm_ = &rm;
307 
308  if (renamer_ != NULL) {
309  renamer_->setSelector(&selector);
310  }
311  MoveNodeGroup moves = selector.candidates();
312  while (moves.nodeCount() > 0) {
313  bool movesRemoved = false;
314  MoveNode& firstMove = moves.node(0);
315  if (firstMove.isOperationMove()) {
316  scheduleOperation(moves, selector);
317  movesRemoved = true;
318  } else {
319  if (firstMove.move().destination().isRA()) {
320  scheduleMove(firstMove, endCycle_, true);
321  notifyScheduled(moves, selector);
322  } else {
323  int tmp = endCycle_;
324  if (bypassNode(firstMove,tmp) && dre_
325  &&!ddg_->resultUsed(firstMove)) {
326  // No need to schedule original move any more
327  movesRemoved = true;
328  } else {
329  // schedule original move
330  scheduleRRMove(firstMove);
331  // If move was register copy to self, it could have been
332  // just dropped.
333  movesRemoved = true;
334  }
335  if (bypass_) {
336  bypassNode(firstMove, tmp);
337  }
338  finalizeSchedule(firstMove, selector);
339  }
340  }
341 
342  if (!movesRemoved && !moves.isScheduled()) {
344  std::string("ii_") +
346  std::string("_dag.dot"));
347 
349  return -1;
350  }
351 
352  moves = selector.candidates();
353  }
354 
355  if (ddg.nodeCount() !=
356  ddg.scheduledNodeCount()) {
357  debugLog("All moves in the DDG didn't get scheduled.");
358 // debugLog("Disassembly of the situation:");
359 // Application::logStream() << bb.disassemble() << std::endl;
360  ddg.writeToDotFile("failed_bb.dot");
361  abortWithError("Should not happen!");
362  }
363 
364  // loop scheduling did not help
365  if (static_cast<unsigned>(ddg.largestCycle() - ddg.smallestCycle()) < rm.initiationInterval()
366  || testOnly) {
367  if (static_cast<unsigned>(ddg.largestCycle() - ddg.smallestCycle()) <
368  rm.initiationInterval()) {
370  << "No overlapping instructions."
371  << "Should Revert to ordinary scheduler."
372  << " ii = " << rm.initiationInterval()
373  << " size = " << ddg.largestCycle() - ddg.smallestCycle()
374  << std::endl;
375  }
376  // this have to be calculated before unscheduling.
377  int rv = (ddg.largestCycle() - ddg.smallestCycle()) / rm.initiationInterval();
379  return rv;
380  }
381 
382  // test that ext-cond jump not in prolog (where it is skipped)
383  int overlap_count = (ddg.largestCycle() - ddg.smallestCycle()) / rm.initiationInterval();
384  if (overlap_count >= tripCount) {
386  return -1;
387  }
388 
389  if (options_ != NULL && options_->dumpDDGsDot()) {
390  ddgSnapshot(ddg, std::string("0"), DataDependenceGraph::DUMP_DOT, true);
391  }
392 
393  if (options_ != NULL && options_->dumpDDGsXML()) {
394  ddgSnapshot(ddg, std::string("0"), DataDependenceGraph::DUMP_XML, true);
395  }
396 
397  if (jumpMove_ != NULL) {
398  MoveNode* jumpLimit = ddg_->findLoopLimitAndIndex(*jumpMove_).first;
399  if (jumpLimit != NULL) {
400  int jumpOverlapCount = (endCycle_ - rm.smallestCycle())
401  / rm.initiationInterval();
402  TTAProgram::TerminalImmediate& ti = dynamic_cast<
403  TTAProgram::TerminalImmediate&>(jumpLimit->move().source());
404  int jumpLimitValue = ti.value().unsignedValue();
405  int loopCounterStep = 1;
406  if (jumpLimitValue != tripCount_) {
407  if (jumpLimitValue == 2 * tripCount_) {
408  loopCounterStep = 2;
409  } else {
410  if (jumpLimitValue == 4 * tripCount_) {
411  loopCounterStep = 4;
412  } else {
413  // don't know how much to decr. counter.
415  return -1;
416  }
417  }
418  }
419  if (tripCount_ > jumpOverlapCount) {
420  jumpLimit->move().setSource(
422  SimValue(
423  jumpLimitValue -
424  (jumpOverlapCount * loopCounterStep),
425  ti.value().width())));
426  } else {
427  // loop limit is too short.
428  // would be always executed too many times.
429  jumpLimit->move().setSource(
430  new TTAProgram::TerminalImmediate(SimValue(jumpLimitValue)));
432  return -1;
433  }
434 
435  }
436  }
438  return (ddg.largestCycle() - ddg.smallestCycle()) / rm.initiationInterval();
439 }

References abortWithError, bypass_, SchedulerCmdLineOptions::bypassDistance(), bypassDistance_, bypassNode(), BUMoveNodeSelector::candidates(), clearRemovedNodes(), BasicBlockScheduler::ddg_, BasicBlockScheduler::ddgSnapshot(), debugLog, TTAProgram::Move::destination(), dre_, DataDependenceGraph::DUMP_DOT, DataDependenceGraph::DUMP_XML, LLVMTCECmdLineOptions::dumpDDGsDot(), LLVMTCECmdLineOptions::dumpDDGsXML(), endCycle_, finalizeSchedule(), DataDependenceGraph::findLoopLimitAndIndex(), RegisterRenamer::initialize(), SimpleResourceManager::initiationInterval(), MoveNode::isMove(), MoveNode::isOperationMove(), TTAProgram::Terminal::isRA(), MoveNodeGroup::isScheduled(), jumpMove_, SchedulerCmdLineOptions::killDeadResults(), DataDependenceGraph::largestCycle(), Application::logStream(), BasicBlockScheduler::minCycle_, MoveNode::move(), MoveNodeGroup::node(), BoostGraph< GraphNode, GraphEdge >::node(), MoveNodeGroup::nodeCount(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), BasicBlockScheduler::notifyScheduled(), BasicBlockScheduler::options_, BasicBlockScheduler::renamer_, DataDependenceGraph::resultUsed(), BasicBlockScheduler::rm_, DataDependenceGraph::scheduledNodeCount(), BasicBlockScheduler::scheduledTempMoves_, scheduleMove(), scheduleOperation(), scheduleRRMove(), BasicBlockScheduler::schedulingTime_, RegisterRenamer::setSelector(), TTAProgram::Move::setSource(), SimpleResourceManager::smallestCycle(), DataDependenceGraph::smallestCycle(), TTAProgram::Move::source(), BasicBlockScheduler::targetMachine_, Conversion::toString(), BasicBlockScheduler::tripCount_, unscheduleAllNodes(), SimValue::unsignedValue(), TTAProgram::TerminalImmediate::value(), SimValue::width(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

◆ longDescription()

std::string BUBasicBlockScheduler::longDescription ( ) const
virtual

Optional longer description of the pass.

This description can include usage instructions, details of choice of algorithmic details, etc.

Returns
The description as a string.

Reimplemented from BasicBlockScheduler.

Definition at line 1210 of file BUBasicBlockScheduler.cc.

1210  {
1211  return
1212  "Bottom-up list basic block scheduler that uses the longest path "
1213  "information of data dependency graph to prioritize the ready list."
1214  "Assumes that the input has registers allocated and no connectivity "
1215  "missing.";
1216 }

◆ precedingTempMove()

MoveNode * BUBasicBlockScheduler::precedingTempMove ( MoveNode current)
protected

Finds the temp move preceding the given movenode.

If it does not have one, returns null.

Parameters
currentMoveNode whose tempmoves we are searching
Returns
tempMove preceding given node, or null if does not exist.

Definition at line 1425 of file BUBasicBlockScheduler.cc.

1425  {
1426 
1428  MoveNode* result = NULL;
1429  for (DataDependenceGraph::NodeSet::iterator i = pred.begin();
1430  i != pred.end(); ++i) {
1431  MoveNode& m = **i;
1432  if (m.isScheduled() ||
1433  !m.move().hasAnnotations(
1435  continue;
1436 
1437  assert(result == NULL &&
1438  "Multiple candidates for the temp move of result read.");
1439  result = &m;
1440  }
1441  return result;
1442 }

References TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE, assert, BasicBlockScheduler::ddg_, TTAProgram::AnnotatedInstructionElement::hasAnnotations(), MoveNode::isScheduled(), MoveNode::move(), and BoostGraph< GraphNode, GraphEdge >::predecessors().

Referenced by scheduleOperand().

Here is the call graph for this function:

◆ scheduleInputOperandTempMoves()

void BUBasicBlockScheduler::scheduleInputOperandTempMoves ( MoveNode operandMove,
MoveNode operandWrite 
)
protected

Schedules the (possible) temporary register copy moves (due to missing connectivity) preceeding the given input move.

The function recursively goes through all the temporary moves added to the given input move.

Parameters
operandMoveA temp move whose predecessor has to be scheduled.
operandWriteThe original move of which temp moves to schedule.

Definition at line 1290 of file BUBasicBlockScheduler.cc.

1291  {
1292  /* Because temporary register moves do not have WaR dependency edges
1293  between the other possible uses of the same temp register in
1294  the same operation, we have to limit the scheduling of the new
1295  temp reg move to the last use of the same temp register so
1296  we don't overwrite the temp registers of other operands. */
1297  int lastUse = endCycle_;
1298 
1299  // find all unscheduled preceeding temp moves of the operand move
1300  DataDependenceGraph::EdgeSet inEdges = ddg_->inEdges(operandMove);
1301  MoveNode* tempMove = NULL;
1302  for (DataDependenceGraph::EdgeSet::iterator i = inEdges.begin();
1303  i != inEdges.end(); ++i) {
1304 
1305  if ((**i).edgeReason() != DataDependenceEdge::EDGE_REGISTER ||
1306  (**i).guardUse() ||
1307  (**i).dependenceType() != DataDependenceEdge::DEP_RAW) {
1308  continue;
1309  }
1310 
1311  MoveNode& m = ddg_->tailNode(**i);
1312  if (m.isScheduled() ||
1313  !m.move().hasAnnotations(
1315  continue;
1316  }
1317 
1318  assert(tempMove == NULL &&
1319  "Multiple unscheduled moves for the operand move, should have "
1320  "max. one (the temporary move)!");
1321  tempMove = &m;
1322  // First cycle where temporary register will be read, this should
1323  // be actuall operand move cycle!
1324  MoveNode* firstRead =
1326  tempMove->move().destination().registerFile(),
1327  tempMove->move().destination().index());
1328  if (firstRead != NULL) {
1329  assert(firstRead->isScheduled());
1330  lastUse = firstRead->cycle();
1331  if (operandMove.isScheduled() && lastUse != operandMove.cycle()) {
1332  Application::logStream() << "\tFirst register read problem "
1333  << operandMove.toString() << " temp " << firstRead->toString()
1334  << std::endl;
1335  }
1336  }
1337  }
1338 
1339  if (tempMove == NULL)
1340  return; // no temp moves found
1341 
1342  scheduleMove(*tempMove, lastUse - 1, true);
1343  if (!tempMove->isScheduled()) {
1344  std::cerr << "temp move: " << tempMove->toString()
1345  << "not scheduled."
1346  << std::endl;
1347  ddg_->writeToDotFile("failTempNotSched.dot");
1348  }
1349  assert(tempMove->isScheduled());
1350  scheduledTempMoves_[&operandWrite].insert(tempMove);
1351  scheduleInputOperandTempMoves(*tempMove, operandWrite);
1352 }

References TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE, assert, MoveNode::cycle(), BasicBlockScheduler::ddg_, DataDependenceEdge::DEP_RAW, TTAProgram::Move::destination(), DataDependenceEdge::EDGE_REGISTER, endCycle_, DataDependenceGraph::firstScheduledRegisterRead(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), TTAProgram::Terminal::index(), BoostGraph< GraphNode, GraphEdge >::inEdges(), MoveNode::isScheduled(), Application::logStream(), MoveNode::move(), TTAProgram::Terminal::registerFile(), BasicBlockScheduler::scheduledTempMoves_, scheduleMove(), BoostGraph< GraphNode, GraphEdge >::tailNode(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by scheduleOperand().

Here is the call graph for this function:

◆ scheduleMove()

void BUBasicBlockScheduler::scheduleMove ( MoveNode moveNode,
int  latestCycle,
bool  allowPredicationAndRenaming 
)
protected

Schedules a single move to the earliest possible cycle, taking in account the DDG, resource constraints, and latencies in producing source values.

This method assumes the move is possible to schedule with regards to connectivity and resources. Short immediates are converted to long immediates when needed.

Parameters
moveThe move to schedule.
earliestCycleThe earliest cycle to try.

Definition at line 960 of file BUBasicBlockScheduler.cc.

961  {
962  if (moveNode.isScheduled()) {
963  ddg_->writeToDotFile("already_sched.dot");
964  throw InvalidData(
965  __FILE__, __LINE__, __func__,
966  (boost::format("Move '%s' is already scheduled!")
967  % moveNode.toString()).str());
968  }
969  int ii = rm_->initiationInterval();
970  int ddgCycle = endCycle_;
971  if (moveNode.move().isControlFlowMove()) {
972  ddgCycle = endCycle_ - targetMachine_->controlUnit()->delaySlots();
973  if (ddg_->latestCycle(moveNode, ii) < ddgCycle) {
974  // Trying to schedule CFG move but data dependence does not
975  // allow it to schedule in correct place
976  throw InvalidData(
977  __FILE__, __LINE__, __func__,
978  (boost::format("Move '%s' needs to be scheduled in %d,"
979  " but data dependence does not allow it!")
980  % moveNode.toString() % ddgCycle).str());
981  }
982  jumpMove_ = &moveNode;
983  } else { // not a control flow move:
984  ddgCycle = ddg_->latestCycle(moveNode, ii);
985  if (renamer_ != NULL && allowPredicationAndRenaming) {
986  int latestFromTrigger =
987  (moveNode.isDestinationOperation()) ?
988  moveNode.latestTriggerWriteCycle() : latestCycle;
989  int minRenamedEC = std::min(
990  latestFromTrigger, ddg_->latestCycle(
991  moveNode, ii, true)); // TODO: 0 or INT_MAX
992 
993  // rename if can and may alow scheuduling later.
994  if (minRenamedEC > ddgCycle) {
995  minRenamedEC = rm_->latestCycle(minRenamedEC, moveNode);
996  if (minRenamedEC > ddgCycle) {
998  moveNode, ii != 0, true, true, minRenamedEC)) {
999  ddgCycle = ddg_->latestCycle(moveNode, ii);
1000  }
1001 #ifdef THIS_IS_BUGGY_WITH_REGCOPY_ADDER
1002  else {
1003  MoveNode *limitingAdep =
1005  moveNode);
1006  if (limitingAdep != NULL) {
1007  // don't try to rename is same operation.
1008  // as it would not help at all.
1009  if (!moveNode.isDestinationOperation() ||
1010  !limitingAdep->isSourceOperation() ||
1011  &moveNode.destinationOperation() !=
1012  &limitingAdep->sourceOperation()) {
1014  *limitingAdep, false, true, true)) {
1015  ddgCycle =
1016  ddg_->latestCycle(moveNode, ii);
1017  }
1018  }
1019  }
1020  }
1021 #endif
1022  }
1023  }
1024  }
1025  }
1026  // if it's a conditional move then we have to be sure that the guard
1027  // is defined before executing the move.
1028  // this is already handled by DDGs earliestCycle, except cases
1029  // where the guard is defined in a previous BB.
1030  // So this prevents scheduling unconditional moves at the beginning
1031  // of a BB.
1032 
1033  if (!moveNode.move().isUnconditional()) {
1034 
1035  if (allowPredicationAndRenaming) {
1036  // try to get rid of the guard if it gives earlier earliestcycle.
1037  if (ddg_->latestCycle(moveNode, ii, false, true, true)
1038  > ddgCycle) {
1039  bool guardNeeded = false;
1040  if (moveNode.move().destination().isGPR() ||
1041  moveNode.move().isControlFlowMove()) {
1042  guardNeeded = true;
1043  } else {
1044  // this would be needed only for trigger,
1045  // but trigger may change during scheduling.
1046  // so lets just limit all operands, it seems
1047  // this does not make the schedule any worse.
1048  if (moveNode.isDestinationOperation()) {
1049  const Operation& o =
1050  moveNode.destinationOperation().operation();
1051  if (o.writesMemory() || o.hasSideEffects() ||
1052  o.affectsCount() != 0) {
1053  guardNeeded = true;
1054  }
1055  }
1056  }
1057  if (!guardNeeded) {
1058  moveNode.move().setGuard(NULL);
1059  ddg_->removeIncomingGuardEdges(moveNode);
1060  ddgCycle = ddg_->latestCycle(moveNode, ii);
1061  assert(moveNode.move().isUnconditional());
1062  }
1063  }
1064 
1065  if (ii == 0 && tryToOptimizeWaw(moveNode)) {
1066  ddgCycle = std::max(ddg_->latestCycle(moveNode, ii),
1067  moveNode.guardLatency()-1);
1068  }
1069 
1070  }
1071  }
1072 
1073  ddgCycle = (ddgCycle == INT_MAX) ? endCycle_ : ddgCycle;
1074  assert(ddgCycle != -1);
1075  // Earliest cycle from which to start, could depend on result ready
1076  // for result moves.
1077  int minCycle = std::min(latestCycle, ddgCycle);
1078  if (moveNode.isSourceConstant() &&
1079  !moveNode.move().hasAnnotations(
1081  // If source is constant and node does not have annotation already,
1082  // we add it if constant can not be transported so IU broker and
1083  // OutputPSocket brokers will add Immediate
1084  // Example : 999999 -> integer0.2
1085  if (!rm_->canTransportImmediate(moveNode)){
1086  TTAProgram::ProgramAnnotation annotation(
1088  moveNode.move().setAnnotation(annotation);
1089 
1090  } else if (!moveNode.isDestinationOperation() &&
1091  rm_->latestCycle(endCycle_, moveNode) == -1 && ii == 0) {
1092  // If source is constant and node does not have annotation already,
1093  // we add it if node has no connection, so IU broker and
1094  // OutputPSocket brokers will add Immediate
1095  // Example: 27 -> integer0.2
1096  // With bus capable of transporting 27 as short immediate but
1097  // no connection from that bus to integer0 unit
1098  TTAProgram::ProgramAnnotation annotation(
1100  moveNode.move().setAnnotation(annotation);
1101  }
1102  }
1103  // annotate the return move otherwise it might get undetected in the
1104  // simulator after the short to long immediate conversion and thus
1105  // stopping simulation automatically might not work
1106  if (moveNode.isSourceConstant() &&
1107  moveNode.move().isReturn() &&
1108  !rm_->canTransportImmediate(moveNode)) {
1109  TTAProgram::ProgramAnnotation annotation(
1111  moveNode.move().setAnnotation(annotation);
1112  }
1113  int earliestDDG = ddg_->earliestCycle(moveNode, ii);
1114  minCycle = rm_->latestCycle(minCycle, moveNode);
1115  if (minCycle < earliestDDG) {
1116  // Bypassed move could get scheduld too early, this should prevent it
1117  return ;
1118  }
1119  if (minCycle == -1 || minCycle == INT_MAX) {
1120  if (moveNode.isSourceConstant() &&
1121  !moveNode.isDestinationOperation() &&
1122  moveNode.move().hasAnnotations(
1124  // If earliest cycle returns -1 and source is constant and moveNode
1125  // needs long immediate there is most likely missing long immediate
1126  // unit
1127  std::string msg = "Assignment of MoveNode " + moveNode.toString();
1128  msg += " failed! Most likely missing Long Immediate Unit";
1129  msg += " or Instruction Template!";
1130  throw IllegalMachine(
1131  __FILE__, __LINE__, __func__, msg);
1132  }
1133  return;
1134  }
1135  if (moveNode.isSourceOperation() && !moveNode.isDestinationOperation()) {
1136  ProgramOperation& po = moveNode.sourceOperation();
1137  if (po.isAnyOutputAssigned()) {
1138  // Some of the output moves are already assigned, we try to
1139  // put this as close to them as possible
1140  int localMaximum = 0;
1141  for (int i = 0; i < po.outputMoveCount(); i++) {
1142  MoveNode& temp = po.outputMove(i);
1143  if (temp.isScheduled()) {
1144  localMaximum = std::max(temp.cycle(), localMaximum);
1145  }
1146  }
1147  if (localMaximum != 0 && localMaximum < minCycle) {
1148  // Bypassed moves are earlier then this one can be scheduled
1149  // scheduling it too late won't help since operands are limited
1150  // with already scheduled result move
1151 
1152  // if ddg requires move to be later then the bypassed
1153  // versions, we have to obey that
1154  localMaximum = std::max(earliestDDG, localMaximum);
1155  int rmEarliest =
1156  rm_->earliestCycle((localMaximum + minCycle)/2, moveNode);
1157  if (rmEarliest != -1 &&
1158  rmEarliest != INT_MAX &&
1159  rmEarliest < minCycle) {
1160  minCycle = rmEarliest;
1161  }
1162  }
1163  }
1164  }
1165  rm_->assign(minCycle, moveNode);
1166  if (!moveNode.isScheduled()) {
1167  throw ModuleRunTimeError(
1168  __FILE__, __LINE__, __func__,
1169  (boost::format("Assignment of MoveNode '%s' failed!")
1170  % moveNode.toString()).str());
1171  }
1172  // Find out the cycle when execution of operation actually ends.
1173  // Only use for operations that uses internal pipeline after the result read.
1174  if (moveNode.isDestinationOperation()) {
1175 
1176  const Operation& op = moveNode.destinationOperation().operation();
1177  const TTAMachine::HWOperation& hwop =
1178  *moveNode.move().destination().functionUnit().operation(op.name());
1179 
1180  unsigned int epEndCycle = moveNode.cycle() + hwop.latency();
1181  // The pipeline will end after current the final cycle,
1182  // have to scheduler earlier.
1183  if (epEndCycle > endCycle_ &&
1184  moveNode.destinationOperation().outputMoveCount() > 0) {
1185  rm_->unassign(moveNode);
1186  }
1187  }
1188 }

References __func__, Operation::affectsCount(), TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM, TTAProgram::ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN, assert, SimpleResourceManager::assign(), SimpleResourceManager::canTransportImmediate(), TTAMachine::Machine::controlUnit(), MoveNode::cycle(), BasicBlockScheduler::ddg_, TTAMachine::ControlUnit::delaySlots(), TTAProgram::Move::destination(), MoveNode::destinationOperation(), SimpleResourceManager::earliestCycle(), DataDependenceGraph::earliestCycle(), endCycle_, DataDependenceGraph::findLimitingAntidependenceDestination(), TTAProgram::Terminal::functionUnit(), MoveNode::guardLatency(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), Operation::hasSideEffects(), SimpleResourceManager::initiationInterval(), ProgramOperation::isAnyOutputAssigned(), TTAProgram::Move::isControlFlowMove(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isReturn(), MoveNode::isScheduled(), MoveNode::isSourceConstant(), MoveNode::isSourceOperation(), TTAProgram::Move::isUnconditional(), jumpMove_, TTAMachine::HWOperation::latency(), SimpleResourceManager::latestCycle(), DataDependenceGraph::latestCycle(), MoveNode::latestTriggerWriteCycle(), MoveNode::move(), Operation::name(), TTAMachine::FunctionUnit::operation(), ProgramOperation::operation(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), DataDependenceGraph::removeIncomingGuardEdges(), RegisterRenamer::renameDestinationRegister(), BasicBlockScheduler::renamer_, RegisterRenamer::renameSourceRegister(), BasicBlockScheduler::rm_, TTAProgram::AnnotatedInstructionElement::setAnnotation(), TTAProgram::Move::setGuard(), MoveNode::sourceOperation(), BasicBlockScheduler::targetMachine_, MoveNode::toString(), tryToOptimizeWaw(), SimpleResourceManager::unassign(), Operation::writesMemory(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by bypassNode(), handleDDG(), handleLoopDDG(), scheduleInputOperandTempMoves(), scheduleOperand(), scheduleResultReads(), scheduleResultReadTempMoves(), scheduleRRMove(), scheduleRRTempMoves(), tryToOptimizeWaw(), and undoBypass().

Here is the call graph for this function:

◆ scheduleOperand()

bool BUBasicBlockScheduler::scheduleOperand ( MoveNode node,
int  cycle 
)
protected

Checks existence of temporary moves and schedules operand according to discovered dependencies.

Definition at line 1449 of file BUBasicBlockScheduler.cc.

1449  {
1450  int tempRegLimitCycle = cycle;
1451  // Find out if RegCopyAdded create temporary move for input.
1452  // If so, the operand has to be scheduled before the other use
1453  // of same temporary register.
1454  MoveNode* test = precedingTempMove(node);
1455  if (test != NULL) {
1456  // Input temp move exists. Check where the move is reading data
1457  // from, so operand move can be scheduled earlier then
1458  // the already scheduled overwriting cycle.
1459  MoveNode* firstWrite =
1461  node.move().source().registerFile(),
1462  node.move().source().index());
1463  if (firstWrite != NULL) {
1464  assert(firstWrite->isScheduled());
1465  tempRegLimitCycle = firstWrite->cycle();
1466  }
1467  }
1468  cycle = std::min(cycle, tempRegLimitCycle);
1469  // This must pass, since we got latest cycle from RM.
1470  scheduleMove(node, cycle, true);
1471  if (node.isScheduled() == false) {
1472  // the latest cycle may change because scheduleMove may do things like
1473  // register renaming, so this may fail.
1474  return false;
1475  }
1476  scheduleInputOperandTempMoves(node, node);
1477  return true;
1478 }

References assert, MoveNode::cycle(), BasicBlockScheduler::ddg_, DataDependenceGraph::firstScheduledRegisterWrite(), TTAProgram::Terminal::index(), MoveNode::isScheduled(), MoveNode::move(), precedingTempMove(), TTAProgram::Terminal::registerFile(), scheduleInputOperandTempMoves(), scheduleMove(), and TTAProgram::Move::source().

Referenced by scheduleOperandWrites().

Here is the call graph for this function:

◆ scheduleOperandWrites()

bool BUBasicBlockScheduler::scheduleOperandWrites ( MoveNodeGroup moves,
int  cycle 
)
protected

Schedules operand moves of an operation execution.

Assumes the given MoveNodeGroup contains all moves in the operation execution. Also assumes that all result moves of the MoveNodeGroup have been scheduled. Assumes bottom up scheduling.

Parameters
movesMoves of the operation execution.
cyclelatest cycle for starting scheduling of operands
Returns
True if all operands got scheduled

Definition at line 664 of file BUBasicBlockScheduler.cc.

664  {
665  ProgramOperation& po =
666  (moves.node(0).isSourceOperation())?
667  (moves.node(0).sourceOperation()):
668  (moves.node(0).destinationOperation());
669 
670  int unscheduledMoves = 0;
671  int scheduledMoves = 0;
672  MoveNode* trigger = NULL;
673 
674  for (int i = 0; i < moves.nodeCount(); i++) {
675  if (!moves.node(i).isDestinationOperation()) {
676  continue;
677  }
678  // count how many operand moves will need to be scheduled
679  unscheduledMoves++;
680  if (moves.node(i).move().destination().isTriggering()) {
681  int limit = moves.node(i).latestTriggerWriteCycle();
682  // update starting cycle based on scheduled results
683  // if necessary.
684  cycle = (limit < cycle) ? limit : cycle;
685  }
686  }
687  int counter = 0;
688 
689  while (unscheduledMoves != scheduledMoves && counter < 5 && cycle >=0) {
690  // try to schedule all input moveNodes, also find trigger
691  // Try to schedule trigger first, otherwise the operand
692  // may get scheduled in cycle where trigger does not fit and
693  // later cycle will not be possible for trigger.
694  trigger = findTrigger(po, *targetMachine_);
695  if (trigger != NULL && !trigger->isScheduled()) {
696  if (scheduleOperand(*trigger, cycle) == false) {
697  cycle--;
698  counter++;
699  continue;
700  }
701  assert(trigger->isScheduled());
702  cycle = trigger->cycle();
703 
704  if (trigger->move().destination().isTriggering()) {
705  // We schedulled trigger, this will give us latest possible cycle
706  // in order not to have operands later then trigger.
707  if (ddg_->hasNode(*trigger)) {
708  // handle moving fu deps.
709  // they may move trigger to later time.
711  int triggerLatest =
712  std::min(ddg_->latestCycle(*trigger,
713  rm_->initiationInterval()),
714  cycle);
715  triggerLatest = rm_->latestCycle(triggerLatest, *trigger);
716  if (triggerLatest != INT_MAX &&
717  triggerLatest > trigger->cycle()) {
718  unschedule(*trigger);
720  if (scheduleOperand(*trigger, triggerLatest) == false) {
721  // reschedule with new dependencies failed,
722  // bringing back originaly scheduled trigger
723  scheduleOperand(*trigger, cycle);
724  }
725  assert(trigger->isScheduled());
726  cycle = trigger->cycle();
727  }
728  }
729  }
730  }
731 
732  for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
733  MoveNode& moveNode = moves.node(moveIndex);
734  // skip the result reads
735  if (!moveNode.isDestinationOperation()) {
736  continue;
737  }
738 
739  if (moveNode.isScheduled()) {
740  continue;
741  }
742  if (scheduleOperand(moveNode, cycle) == false) {
744  break;
745  }
746 
747  }
748  // Tests if all input moveNodes were scheduled, if so check if trigger
749  // is latest
750  scheduledMoves = 0;
751  for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
752  MoveNode& moveNode = moves.node(moveIndex);
753  // skip the result reads
754  if (!moveNode.isDestinationOperation()) {
755  continue;
756  }
757  if (moveNode.isScheduled()) {
758  scheduledMoves++;
759  if (moveNode.cycle() > cycle) {
760  // moveNode is operand and it is scheduled after the
761  // trigger! This is wrong!
762  std::cerr << "Move " << moveNode.toString()
763  << " is scheduled after the trigger!" << std::endl;
764  scheduledMoves--;
765  }
766  }
767  }
768 
769  // Some moveNodes were not scheduled
770  // unschedule all and try with higher start cycle
771  if (scheduledMoves != unscheduledMoves) {
772  for (int i = 0; i < moves.nodeCount(); i++){
773  MoveNode& moveNode = moves.node(i);
774  if (moveNode.isScheduled() &&
775  moveNode.isDestinationOperation()) {
776  unschedule(moveNode);
778  }
779  }
780  scheduledMoves = 0;
781  } else {
782  // every operand is scheduled, we can return quickly
783  return true;
784  }
785  cycle--;
786  counter++;
787  }
788  // If loop timeouts we get here
789  if (scheduledMoves != unscheduledMoves) {
790  return false;
791  }
792  return true;
793 }

References assert, MoveNode::cycle(), BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), MoveNode::destinationOperation(), BasicBlockScheduler::findTrigger(), BoostGraph< GraphNode, GraphEdge >::hasNode(), SimpleResourceManager::initiationInterval(), MoveNode::isDestinationOperation(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), TTAProgram::Terminal::isTriggering(), SimpleResourceManager::latestCycle(), DataDependenceGraph::latestCycle(), MoveNode::latestTriggerWriteCycle(), MoveNode::move(), DataDependenceGraph::moveFUDependenciesToTrigger(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), BasicBlockScheduler::rm_, scheduleOperand(), MoveNode::sourceOperation(), BasicBlockScheduler::targetMachine_, MoveNode::toString(), BasicBlockScheduler::unschedule(), and BasicBlockScheduler::unscheduleInputOperandTempMoves().

Referenced by scheduleOperation().

Here is the call graph for this function:

◆ scheduleOperation()

void BUBasicBlockScheduler::scheduleOperation ( MoveNodeGroup moves,
BUMoveNodeSelector selector 
)
protected

Schedules moves in a single operation execution.

Assumes the given MoveNodeGroup contains all moves in the operation execution. Also assumes that all outputs of the MoveNodeGroup have been scheduled.

Parameters
movesMoves of the operation execution.

Definition at line 455 of file BUBasicBlockScheduler.cc.

456  {
457  ProgramOperation& po =
458  (moves.node(0).isSourceOperation())?
459  (moves.node(0).sourceOperation()):
460  (moves.node(0).destinationOperation());
461  tryToSwitchInputs(po);
462  bool operandsFailed = true;
463  bool resultsFailed = true;
464  int resultsStartCycle = endCycle_;
465  int maxResult = resultsStartCycle;
466 
467 #ifdef DEBUG_REG_COPY_ADDER
468  ddg_->setCycleGrouping(true);
470  (boost::format("%s_before_ddg.dot") % ddg_->name()).str());
471 #endif
472  RegisterCopyAdder regCopyAdder(
475  regCopyAdder.addMinimumRegisterCopies(po, *targetMachine_, ddg_);
476 
477 #ifdef DEBUG_REG_COPY_ADDER
478  const int tempsAdded = copies.count_;
479 #endif
480  ;
481 #ifdef DEBUG_REG_COPY_ADDER
482  if (tempsAdded > 0) {
484  (boost::format("%s_after_regcopy_ddg.dot") % ddg_->name()).str());
485  }
486 // ddg_->sanityCheck();
487 #endif
488 
489  bool bypass = bypass_;
490  bool bypassLate = bypass_;
491  int ii = rm_->initiationInterval();
492  // Find smallest cycle from RM is known, otherwise 1
493  int rmSmallest = (rm_->smallestCycle() < INT_MAX) ? rm_->smallestCycle() : 1;
494  // rmSmallest is cycle where there is nothing scheduled, and nothing
495  // is scheduled before it, so it the schedule of result fails there
496  // there is no point decreasing the schedule any more.
497  int stopingPoint = (ii == 0) ?
498  rmSmallest - 1 :
499  endCycle_ - ii -1;
500  while ((operandsFailed || resultsFailed) &&
501  resultsStartCycle >= stopingPoint) {
502  maxResult = scheduleResultReads(
503  moves, resultsStartCycle, bypass, bypassLate);
504  if (maxResult != -1) {
505  resultsFailed = false;
506  } else {
507  // At least one of the results did not get scheduled correctly,
508  // We try with earlier starting cycle.
509  // Drawback, in case of 3 results, 1 could be scheduled very late,
510  // second bit earlier and third failing because of location of
511  // second scheduled result, not first.
512  // Better solution would be to try to push scheduled results up
513  // individually, but that would be rather slow process.
514  for (int i = 0; i < moves.nodeCount(); i++){
515  MoveNode& moveNode = moves.node(i);
516  if (moveNode.isScheduled() &&
517  moveNode.isSourceOperation()) {
518  unschedule(moveNode);
520  undoBypass(moveNode);
521  }
522  }
523  resultsFailed = true;
524  if (bypass && bypassLate) {
525  bypass = true;
526  bypassLate = false;
527  } else if (bypass && !bypassLate) {
528  bypass = false;
529  bypassLate = true;
530  } else if (!bypass && bypassLate) {
531  bypassLate = false;
532  } else {
533  // We will try to schedule results in earlier cycle
534  resultsStartCycle--;
535  bypass = bypass_;
536  bypassLate = bypass_;
537  }
538  continue;
539  }
540  regCopyAdder.resultsScheduled(copies, *ddg_);
541  if (scheduleOperandWrites(moves, resultsStartCycle)) {
542  operandsFailed = false;
543  } else {
544  // Scheduling some operand failed, unschedule all moves, try earlier
545  for (int i = 0;i < po.inputMoveCount(); i++) {
546  MoveNode& moveNode = po.inputMove(i);//moves.node(i);
547  if (moveNode.isScheduled()) {
548  unschedule(moveNode);
549  if (moveNode.isDestinationOperation()) {
551  }
552 
553  if (moveNode.isSourceOperation()) {
555  }
556  }
557  }
558 
559  for (int i = 0;i < po.outputMoveCount(); i++) {
560  MoveNode& moveNode = po.outputMove(i);//moves.node(i);
561  if (moveNode.isScheduled()) {
562  unschedule(moveNode);
563  if (moveNode.isDestinationOperation()) {
565  }
566 
567  if (moveNode.isSourceOperation()) {
569  }
570  }
571  }
572 
573  std::vector<MoveNode*> outputMoves;
574  for (int i = 0; i < po.outputMoveCount(); i++) {
575  outputMoves.push_back(&po.outputMove(i));
576  }
577 
578  for (unsigned int i = 0; i < outputMoves.size(); i++) {
579  // then undo the bypass etc.
580  MoveNode& moveNode = *outputMoves[i]; //moves.node(i);
581  if (moveNode.isSourceOperation()) {
582  undoBypass(moveNode);
583  }
584  }
585 
586  operandsFailed = true;
587  if (bypass && bypassLate) {
588  bypass = true;
589  bypassLate = false;
590  } else if (bypass && !bypassLate) {
591  bypass = false;
592  bypassLate = true;
593  } else if (!bypass && bypassLate) {
594  bypassLate = false;
595  } else {
596  resultsStartCycle--;
597  maxResult--;
598  resultsStartCycle = std::min(maxResult, resultsStartCycle);
599  bypass = bypass_;
600  bypassLate = bypass_;
601  }
602  }
603  }
604  // This fails if we reach 0 cycle.
605  if (resultsFailed) {
606  if (ii == 0) {
607  // This is only problem with regular scheduling, with loop schedule
608  // this is expected for too small II.
610  (boost::format("bb_%s_2_failed_scheduling.dot")
611  % ddg_->name()).str());
612  }
614  throw ModuleRunTimeError(
615  __FILE__, __LINE__, __func__,
616  "Results scheduling failed for \'" + moves.toString());
617  }
618 
619  if (operandsFailed) {
620  if (ii == 0) {
621  // This is only problem with regular scheduling, with loop schedule
622  // this is expected for too small II.
624  (boost::format("bb_%s_2_scheduling.dot")
625  % ddg_->name()).str());
626  }
628  throw ModuleRunTimeError(
629  __FILE__, __LINE__, __func__,
630  "Operands scheduling failed for \'" + moves.toString());
631  }
632 
633  for (int i = 0; i < moves.nodeCount(); i++) {
634  finalizeSchedule(moves.node(i), selector);
635  }
636  regCopyAdder.operandsScheduled(copies,*ddg_);
637 #ifdef DEBUG_REG_COPY_ADDER
638  if (tempsAdded > 0) {
640  (boost::format("%s_after_scheduler_ddg.dot") %
641  ddg_->name()).str());
643  << "(operation fix #" << ddg_->name() << ")" << std::endl
644  << std::endl;
645  ++graphCount;
646  }
647 
648 #endif
649 }

References __func__, RegisterCopyAdder::addMinimumRegisterCopies(), bypass_, RegisterCopyAdder::AddedRegisterCopies::count_, BasicBlockScheduler::ddg_, MoveNode::destinationOperation(), endCycle_, finalizeSchedule(), SimpleResourceManager::initiationInterval(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), SchedulerPass::interPassData(), MoveNode::isDestinationOperation(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), Application::logStream(), BoostGraph< GraphNode, GraphEdge >::name(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), RegisterCopyAdder::operandsScheduled(), ProgramOperation::outputMove(), ProgramOperation::outputMoveCount(), RegisterCopyAdder::resultsScheduled(), BasicBlockScheduler::rm_, scheduleOperandWrites(), scheduleResultReads(), BasicBlockScheduler::selector_, DataDependenceGraph::setCycleGrouping(), SimpleResourceManager::smallestCycle(), MoveNode::sourceOperation(), BasicBlockScheduler::targetMachine_, MoveNodeGroup::toString(), tryToSwitchInputs(), undoBypass(), BasicBlockScheduler::unschedule(), unscheduleAllNodes(), BasicBlockScheduler::unscheduleInputOperandTempMoves(), BasicBlockScheduler::unscheduleResultReadTempMoves(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by handleDDG(), and handleLoopDDG().

Here is the call graph for this function:

◆ scheduleResultReads()

int BUBasicBlockScheduler::scheduleResultReads ( MoveNodeGroup moves,
int  cycle,
bool  bypass = false,
bool  bypassLate = false 
)
protected

Schedules the result read moves of an operation execution.

Assumes the given MoveNodeGroup contains all moves in the operation execution.

Parameters
movesMoves of the operation execution.
Returns
Last cycle in which any of the results was scheduled

Definition at line 805 of file BUBasicBlockScheduler.cc.

806  {
807  int maxResultCycle = cycle;
808  int tempRegLimitCycle = cycle;
809  int localMaximum = 0;
810  bool resultScheduled = false;
811  for (int moveIndex = 0; moveIndex < moves.nodeCount(); ++moveIndex) {
812  if (!moves.node(moveIndex).isSourceOperation()) {
813  continue;
814  }
815  MoveNode& moveNode = moves.node(moveIndex);
816  bool bypassSuccess = false;
817  if (!moveNode.isScheduled()) {
818  if (!moveNode.isSourceOperation()) {
819  throw InvalidData(
820  __FILE__, __LINE__, __func__,
821  (boost::format("Move to schedule '%s' is not "
822  "result move!") % moveNode.toString()).str());
823  }
824  if (bypass) {
825  int newMaximum = maxResultCycle + bypassDistance_;
826  bypassSuccess = bypassNode(moveNode, newMaximum);
827  localMaximum =
828  (newMaximum > localMaximum) ? newMaximum : localMaximum;
829  if (dre_ && bypassSuccess &&
830  !ddg_->resultUsed(moveNode)) {
831  // All uses of result were bypassed, result will be removed
832  // after whole operation is scheduled.
833  //tempRegLimitCycle = std::max(tempRegLimitCycle, maxResultCycle);
834  resultScheduled = true;
835  continue;
836  }
837  }
838 
839  // Find out if RegCopyAdded create temporary copy for output move
840  MoveNode* test = succeedingTempMove(moveNode);
841  if (test != NULL) {
842  // Output temp move exists. Check where the original move
843  // will be writing, that is the temporary register.
844  MoveNode* firstWrite =
846  moveNode.move().destination().registerFile(),
847  moveNode.move().destination().index());
848  if (firstWrite != NULL) {
849  assert(firstWrite->isScheduled());
850  tempRegLimitCycle = firstWrite->cycle();
851  }
852  // Schedule temporary move first.
854  moveNode, moveNode, tempRegLimitCycle);
855  // If there was temporary result read scheduled, write needs
856  // to be at least one cycle earlier.
857  if (test != NULL && test->isScheduled())
858  tempRegLimitCycle = std::min(test->cycle() -1, cycle);
859  }
860  tempRegLimitCycle =
861  (localMaximum != 0)
862  ? std::min(localMaximum +1, tempRegLimitCycle)
863  : tempRegLimitCycle;
864 
865  scheduleMove(moveNode, tempRegLimitCycle, true);
866  if (!moveNode.isScheduled()) {
867  // Scheduling result failed due to some of the bypassed moves
868  // will try again without bypassing anything.
869  undoBypass(moveNode);
870  return -1;
871  }
872  if (bypassLate) {
873  int newMaximum = moveNode.cycle() + bypassDistance_;
874  if (bypassNode(moveNode, newMaximum)) {
875  localMaximum =
876  (localMaximum < newMaximum) ? newMaximum : localMaximum;
877  localMaximum = (localMaximum > cycle) ? localMaximum : cycle;
878  int originalCycle = moveNode.cycle();
879  unschedule(moveNode);
880  scheduleMove(moveNode, localMaximum, true);
881  if (!moveNode.isScheduled()) {
882  scheduleMove(moveNode, originalCycle, false);
883  }
884  }
885  assert(moveNode.isScheduled());
886  }
887  resultScheduled = true;
888  // Find latest schedule result cycle
889  localMaximum =
890  (localMaximum < moveNode.cycle())
891  ? moveNode.cycle() : localMaximum;
892 
893  maxResultCycle =
894  (moveNode.cycle() > maxResultCycle) ?
895  moveNode.cycle() : maxResultCycle;
896  }
897 
898  }
899  return (resultScheduled) ? localMaximum : maxResultCycle;
900 }

References __func__, assert, bypassDistance_, bypassNode(), MoveNode::cycle(), BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), dre_, DataDependenceGraph::firstScheduledRegisterWrite(), TTAProgram::Terminal::index(), MoveNode::isScheduled(), MoveNode::isSourceOperation(), MoveNode::move(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), TTAProgram::Terminal::registerFile(), DataDependenceGraph::resultUsed(), scheduleMove(), scheduleResultReadTempMoves(), BasicBlockScheduler::succeedingTempMove(), MoveNode::toString(), undoBypass(), and BasicBlockScheduler::unschedule().

Referenced by scheduleOperation().

Here is the call graph for this function:

◆ scheduleResultReadTempMoves()

void BUBasicBlockScheduler::scheduleResultReadTempMoves ( MoveNode resultMove,
MoveNode resultRead,
int  firstWriteCycle 
)
protected

Schedules the (possible) temporary register copy moves (due to missing connectivity) preceeding the given result read move.

The function recursively goes through all the temporary moves added to the given result move.

Parameters
resultMoveA temp move whose predecessor has to be scheduled.
resultReadThe original move of which temp moves to schedule.
firstWriteCycleRecursive function parameter.

Definition at line 1229 of file BUBasicBlockScheduler.cc.

1230  {
1231  /* Because temporary register moves do not have WaR/WaW dependency edges
1232  between the other possible uses of the same temp register in
1233  the same operation, we have to limit the scheduling of the new
1234  temp reg move to the last use of the same temp register so
1235  we don't overwrite the temp registers of the other operands. */
1236 
1237 
1238  // find all unscheduled succeeding moves of the result read move
1239  // there should be only only one with the only dependence edge (RaW) to
1240  // the result move
1241 
1242  MoveNode* tempMove1 = succeedingTempMove(resultMove);
1243  if (tempMove1 == NULL)
1244  return; // no temp moves found
1245 
1246  MoveNode* tempMove2 = succeedingTempMove(*tempMove1);
1247  if (tempMove2 != NULL) {
1248  // Found second temp move. First temp move will write register
1249  // which second will read.
1250  MoveNode* firstWrite =
1252  tempMove1->move().destination().registerFile(),
1253  tempMove1->move().destination().index());
1254  if (firstWrite != NULL && firstWrite->isScheduled())
1255  firstWriteCycle = firstWrite->cycle();
1256  scheduleResultReadTempMoves(*tempMove1, resultRead, firstWriteCycle);
1257  if (tempMove2 != NULL && tempMove2->isScheduled()){ // TODO: maybe there is scheduled is missing
1258  firstWriteCycle = tempMove2->cycle() -1;
1259  }
1260  }
1261  bool bypassSuccess = false;
1262  if (bypass_) {
1263  int tmp = endCycle_;
1264  bypassSuccess = bypassNode(*tempMove1, tmp);
1265  }
1266  if (!bypassSuccess || !dre_ || ddg_->resultUsed(*tempMove1)) {
1267  scheduleMove(*tempMove1, firstWriteCycle, true);
1268  assert(tempMove1->isScheduled());
1269  if (bypass_) {
1270  int tmp = endCycle_;
1271  bypassSuccess = bypassNode(*tempMove1, tmp);
1272  }
1273  scheduledTempMoves_[&resultRead].insert(tempMove1);
1274  } else if (dre_ && !ddg_->resultUsed(*tempMove1)) {
1275  finalizeSchedule(*tempMove1, dynamic_cast<BUMoveNodeSelector&>(*selector_));
1276  }
1277 }

References assert, bypass_, bypassNode(), MoveNode::cycle(), BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), dre_, endCycle_, finalizeSchedule(), DataDependenceGraph::firstScheduledRegisterWrite(), TTAProgram::Terminal::index(), MoveNode::isScheduled(), MoveNode::move(), TTAProgram::Terminal::registerFile(), DataDependenceGraph::resultUsed(), BasicBlockScheduler::scheduledTempMoves_, scheduleMove(), BasicBlockScheduler::selector_, and BasicBlockScheduler::succeedingTempMove().

Referenced by scheduleResultReads(), scheduleRRMove(), and scheduleRRTempMoves().

Here is the call graph for this function:

◆ scheduleRRMove()

void BUBasicBlockScheduler::scheduleRRMove ( MoveNode moveNode)
protected

Schedules moves in a single operation execution.

Assumes the given MoveNodeGroup contains all moves in the operation execution. Also assumes that all inputs to the MoveNodeGroup have been scheduled.

Parameters
moveNodeR-R Move to schedule.

Definition at line 912 of file BUBasicBlockScheduler.cc.

912  {
913 #ifdef DEBUG_REG_COPY_ADDER
914  ddg_->setCycleGrouping(true);
916  (boost::format("%s_before_ddg.dot") % ddg_->name()).str());
917 #endif
918 
919  if (moveNode.move().source().equals(
920  moveNode.move().destination())) {
921  return;
922  }
923 
924  RegisterCopyAdder regCopyAdder(
926 
927 #ifdef DEBUG_REG_COPY_ADDER
928  const int tempsAdded =
929 #endif
930 
931  regCopyAdder.addRegisterCopiesToRRMove(moveNode, ddg_)
932 #ifdef DEBUG_REG_COPY_ADDER
933  .count_
934 #endif
935  ;
936 #ifdef DEBUG_REG_COPY_ADDER
937  if (tempsAdded > 0) {
939  (boost::format("%s_after_regcopy_ddg.dot") % ddg_->name()).str());
940  }
941 // ddg_->sanityCheck();
942 #endif
943  scheduleResultReadTempMoves(moveNode, moveNode, endCycle_);
944  scheduleMove(moveNode, endCycle_, true);
945 }

References RegisterCopyAdder::addRegisterCopiesToRRMove(), RegisterCopyAdder::AddedRegisterCopies::count_, BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), endCycle_, TTAProgram::Terminal::equals(), SchedulerPass::interPassData(), MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::name(), BasicBlockScheduler::rm_, scheduleMove(), scheduleResultReadTempMoves(), BasicBlockScheduler::selector_, DataDependenceGraph::setCycleGrouping(), TTAProgram::Move::source(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by handleDDG(), and handleLoopDDG().

Here is the call graph for this function:

◆ scheduleRRTempMoves()

void BUBasicBlockScheduler::scheduleRRTempMoves ( MoveNode regToRegMove,
MoveNode firstMove,
int  lastUse 
)
protected

Schedules the (possible) temporary register copy moves (due to missing connectivity) succeeding the given RR move.

The function recursively goes through all the temporary moves added to the given RR move.

Parameters
regToRegMoveA temp move whose successor has to be scheduled.
firstMoveThe original move of which temp moves to schedule.
lastUseRecursive function parameter, it should be set as 0 for the first function call.

Definition at line 1366 of file BUBasicBlockScheduler.cc.

1367  {
1368  /* Because temporary register moves do not have WaR/WaW dependency edges
1369  between the other possible uses of the same temp register in
1370  the same operation, we have to limit the scheduling of the new
1371  temp reg move to the last use of the same temp register so
1372  we don't overwrite the temp registers of the other operands. */
1373 
1374  // find all unscheduled succeeding moves of the result read move
1375  // there should be only only one with the only dependence edge (RaW) to
1376  // the result move
1377 
1378  MoveNode* tempMove1 = succeedingTempMove(regToRegMove);
1379  if (tempMove1 == NULL)
1380  return; // no temp moves found
1381 
1382  MoveNode* tempMove2 = succeedingTempMove(*tempMove1);
1383  if (tempMove2 != NULL) {
1384  MoveNode* firstWrite =
1386  tempMove1->move().destination().registerFile(),
1387  tempMove1->move().destination().index());
1388  if (firstWrite != NULL) {
1389  assert(firstWrite->isScheduled());
1390  lastUse = firstWrite->cycle();
1391  }
1392  }
1393  scheduleResultReadTempMoves(*tempMove1, firstMove, lastUse);
1394  bool bypassSuccess = false;
1395  if (bypass_) {
1396  int tmp = endCycle_;
1397  bypassSuccess = bypassNode(*tempMove1, tmp);
1398  }
1399  if (!bypassSuccess || !dre_ || ddg_->resultUsed(*tempMove1)) {
1400  scheduleMove(*tempMove1, lastUse - 1, true);
1401  if (!tempMove1->isScheduled()) {
1402  std::cerr << "not scheduled: " << tempMove1->toString() << std::endl;
1403  ddg_->writeToDotFile("tempNotSched.dot");
1404  }
1405  if (bypass_) {
1406  int tmp = endCycle_;
1407  bypassSuccess = bypassNode(*tempMove1, tmp);
1408  }
1409  assert(tempMove1->isScheduled());
1410  scheduledTempMoves_[&firstMove].insert(tempMove1);
1411  } else if (dre_ && !ddg_->resultUsed(*tempMove1)) {
1412  finalizeSchedule(*tempMove1, dynamic_cast<BUMoveNodeSelector&>(*selector_));
1413  }
1414 }

References assert, bypass_, bypassNode(), MoveNode::cycle(), BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), dre_, endCycle_, finalizeSchedule(), DataDependenceGraph::firstScheduledRegisterWrite(), TTAProgram::Terminal::index(), MoveNode::isScheduled(), MoveNode::move(), TTAProgram::Terminal::registerFile(), DataDependenceGraph::resultUsed(), BasicBlockScheduler::scheduledTempMoves_, scheduleMove(), scheduleResultReadTempMoves(), BasicBlockScheduler::selector_, BasicBlockScheduler::succeedingTempMove(), MoveNode::toString(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Here is the call graph for this function:

◆ shortDescription()

std::string BUBasicBlockScheduler::shortDescription ( ) const
virtual

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

Returns
The description as a string.

Reimplemented from BasicBlockScheduler.

Definition at line 1197 of file BUBasicBlockScheduler.cc.

1197  {
1198  return "Bottom-up list scheduler with a basic block scope.";
1199 }

◆ tryToOptimizeWaw()

bool BUBasicBlockScheduler::tryToOptimizeWaw ( const MoveNode moveNode)
protected

Tries to get rid of WaW dependence from unconditional to conditional.

if the conditional move's result is overwritten by the cond for all users, make the unconditional move conditional, with opposite guard.

Definition at line 1978 of file BUBasicBlockScheduler.cc.

1978  {
1979 
1980  if (ddg_->latestCycle(moveNode, endCycle_ , false, true, true) >=
1981  ddg_->latestCycle(moveNode)) {
1982  return false;
1983  }
1984 
1985  MoveNode* wawPred = NULL;
1986  DataDependenceEdge* wawEdge = NULL;
1987 
1988  DataDependenceGraph::EdgeSet inEdges = ddg_->inEdges(moveNode);
1989  for (DataDependenceGraph::EdgeSet::iterator i = inEdges.begin();
1990  i != inEdges.end(); i++) {
1991  DataDependenceEdge* e = *i;
1992 
1995  !e->tailPseudo()) {
1996  if (wawPred == NULL) {
1997  wawPred = &ddg_->tailNode(**i);
1998  wawEdge = e;
1999  } else {
2000  return false;
2001  }
2002  }
2003  }
2004  if (wawPred == NULL) {
2005  return false;
2006  }
2007 
2008  if (!wawPred->move().isUnconditional()) {
2009  return false;
2010  }
2011 
2012  // check that no other usage of the data.
2013  DataDependenceGraph::NodeSet consumers = ddg_->regRawSuccessors(*wawPred);
2014  DataDependenceGraph::NodeSet consumers2 = ddg_->regRawSuccessors(moveNode);
2015  for (DataDependenceGraph::NodeSet::iterator i = consumers.begin();
2016  i != consumers.end(); i++) {
2017  MoveNode* mn = *i;
2018  if (consumers2.find(mn) == consumers2.end() &&
2019  (mn->move().isUnconditional() ||
2020  !ddg_->exclusingGuards(*mn, moveNode))) {
2021  return false;
2022  }
2023  }
2024  if (wawPred->isScheduled())
2025  unschedule(*wawPred);
2026 
2028  wawPred->move().setGuard(cg.createInverseGuard(moveNode.move().guard()));
2029 
2030  ddg_->copyDepsOver(*wawPred, true, false);
2031 
2032  ddg_->copyIncomingGuardEdges(moveNode, *wawPred);
2033  ddg_->copyOutgoingGuardWarEdges(moveNode, *wawPred);
2034 
2035  ddg_->removeEdge(*wawEdge);
2036 
2037  scheduleMove(*wawPred, endCycle_, false);
2038  bool revert = false;
2039 
2040  if (!wawPred->isScheduled()) {
2041  revert = true;
2042  }
2043  if (revert) {
2044  wawPred->move().setGuard(NULL);
2045  ddg_->removeIncomingGuardEdges(*wawPred);
2046  ddg_->removeOutgoingGuardWarEdges(*wawPred);
2047  ddg_->connectNodes(*wawPred, moveNode, *wawEdge);
2048  return false;
2049  }
2050 
2051  return true;
2052 }

References BoostGraph< GraphNode, GraphEdge >::connectNodes(), DataDependenceGraph::copyDepsOver(), DataDependenceGraph::copyIncomingGuardEdges(), DataDependenceGraph::copyOutgoingGuardWarEdges(), TTAProgram::CodeGenerator::createInverseGuard(), BasicBlockScheduler::ddg_, DataDependenceEdge::DEP_WAW, DataDependenceEdge::dependenceType(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), endCycle_, DataDependenceGraph::exclusingGuards(), TTAProgram::Move::guard(), BoostGraph< GraphNode, GraphEdge >::inEdges(), MoveNode::isScheduled(), TTAProgram::Move::isUnconditional(), DataDependenceGraph::latestCycle(), MoveNode::move(), DataDependenceGraph::regRawSuccessors(), BoostGraph< GraphNode, GraphEdge >::removeEdge(), DataDependenceGraph::removeIncomingGuardEdges(), DataDependenceGraph::removeOutgoingGuardWarEdges(), scheduleMove(), TTAProgram::Move::setGuard(), BoostGraph< GraphNode, GraphEdge >::tailNode(), DataDependenceEdge::tailPseudo(), BasicBlockScheduler::targetMachine_, and BasicBlockScheduler::unschedule().

Referenced by scheduleMove().

Here is the call graph for this function:

◆ tryToSwitchInputs()

bool BUBasicBlockScheduler::tryToSwitchInputs ( ProgramOperation po)
protected

If the operation is commutative, tries to change the operands so that the scheduler can schedule it better.

If the operation is not commutative, does nothing.

Which is better depends lots on the code being compiled and architecture which we are compiling for.

Current implementation tries to make constants triggers, and if there are no constant inputs, try to also change inputs so that last ready operand becomes trigger if it's near, but first ready operand becomes trigger if it's further (allows better bypassing of other operands) This seems to work in practice

Parameters
poprogramoperation whose inputs to switch
Returns
true if changed inputs, false if not.

Definition at line 1910 of file BUBasicBlockScheduler.cc.

1910  {
1911 
1912  const Operation& op = po.operation();
1913  if (op.numberOfInputs() == 2 && op.canSwap(1, 2)) {
1914 
1915  int triggerOperand = getTriggerOperand(op, *targetMachine_);
1916 
1917  if (triggerOperand != 0) {
1918  MoveNode* latest = NULL;
1919  int latestMinCycle = -1;
1920  int firstMinCycle = INT_MAX;
1921 
1922  //check all input moves.
1923  for (int i = 0; i < po.inputMoveCount(); i++) {
1924  MoveNode& node = po.inputMove(i);
1925  // always make constants triggers.
1926  // todo: shoudl do this only with short imms?
1927  if (node.isSourceConstant()) {
1928  int operandIndex =
1929  node.move().destination().operationIndex();
1930  if (operandIndex != triggerOperand) {
1931  po.switchInputs();
1932  return true;
1933  } else {
1934  return false;
1935  }
1936  }
1937 
1938  int minCycle = ddg_->latestCycle(
1939  node, rm_->initiationInterval(), false, true, true, true, true);
1940  if (minCycle > latestMinCycle) {
1941  latest = &node;
1942  latestMinCycle = minCycle;
1943  }
1944  if (minCycle < firstMinCycle) {
1945  firstMinCycle = minCycle;
1946  }
1947  }
1948 
1949  int lastOperand = latest->move().destination().operationIndex();
1950 
1951  // don't change if min cycles of first and last are equal.
1952  if (latestMinCycle == firstMinCycle) {
1953  return false;
1954  }
1955  if (latestMinCycle - firstMinCycle > 1) { // reverse logic if far.
1956  if (lastOperand == triggerOperand) {
1957  po.switchInputs();
1958  return true;
1959  }
1960  } else {
1961  if (lastOperand != triggerOperand) {
1962  po.switchInputs();
1963  return true;
1964  }
1965  }
1966  }
1967  }
1968  return false;
1969 }

References Operation::canSwap(), BasicBlockScheduler::ddg_, TTAProgram::Move::destination(), BasicBlockScheduler::getTriggerOperand(), SimpleResourceManager::initiationInterval(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), MoveNode::isSourceConstant(), DataDependenceGraph::latestCycle(), MoveNode::move(), Operation::numberOfInputs(), ProgramOperation::operation(), TTAProgram::Terminal::operationIndex(), BasicBlockScheduler::rm_, ProgramOperation::switchInputs(), and BasicBlockScheduler::targetMachine_.

Referenced by scheduleOperation().

Here is the call graph for this function:

◆ undoBypass()

void BUBasicBlockScheduler::undoBypass ( MoveNode moveNode,
MoveNode single = NULL,
int  oCycle = -1 
)
protected

Remove all the bypasses of result write in moveNode and restore and schedule original moves.

Definition at line 1528 of file BUBasicBlockScheduler.cc.

1529  {
1530 
1531  if (single == NULL) {
1532  if (MapTools::containsKey(bypassDestinations_, &moveNode)) {
1533  std::vector<MoveNode*> destinationsVector =
1534  bypassDestinations_[&moveNode];
1535  std::vector<std::pair<MoveNode*, int> > rescheduleVector;
1536 
1537  for (unsigned int j = 0; j < destinationsVector.size(); j++) {
1538  // unschedule and unmerge all bypassed nodes
1539  MoveNode* dest = destinationsVector[j];
1540  if (dest->isScheduled()) {
1541  unschedule(*dest);
1542  }
1543  ddg_->unMergeUser(moveNode, *dest);
1544  int originalCycle =
1545  bypassDestinationsCycle_[&moveNode][j];
1546  const TTAMachine::Bus* bus =
1547  bypassDestinationsBus_[&moveNode][j];
1548  dest->move().setBus(*bus);
1549  rescheduleVector.push_back(
1550  std::pair<MoveNode*, int>(dest, originalCycle));
1551  droppedNodes_.erase(dest);
1552  }
1553  for (unsigned int i = 0; i < rescheduleVector.size(); i++) {
1554  // reassign nodes to their original places
1555  std::pair<MoveNode*, int> dest = rescheduleVector[i];
1556  //rm_->assign(dest.second, *dest.first);
1557  scheduleMove(*dest.first, dest.second, false);
1558  if (!dest.first->isScheduled()) {
1559  ddg_->writeToDotFile("unbypassFailed.dot");
1560  std::cerr << " Source: " << moveNode.toString()
1561  << ", Original: " << dest.first->toString() <<
1562  ", original cycle: " << dest.second << std::endl<< std::endl;
1563  }
1564  assert(dest.first->isScheduled());
1565  }
1566  bypassDestinations_.erase(&moveNode);
1567  bypassDestinationsCycle_.erase(&moveNode);
1568  bypassDestinationsBus_.erase(&moveNode);
1569  }
1570  } else {
1571  if (single->isScheduled()) {
1572  // Bypassed node could get scheduled too early, in such a case
1573  // this move need to be unscheduled.
1574  unschedule(*single);
1575  }
1576  int size = bypassDestinationsBus_[&moveNode].size();
1577  const TTAMachine::Bus* bus =
1578  bypassDestinationsBus_[&moveNode][size-1];
1579  ddg_->unMergeUser(moveNode, *single);
1580  single->move().setBus(*bus);
1581  //rm_->assign(oCycle, *single);
1582  scheduleMove(*single, oCycle, false);
1583  if (!single->isScheduled()) {
1584  ddg_->writeToDotFile("unbypassFailed.dot");
1585  std::cerr << " Source: " << moveNode.toString()
1586  << ", Original: " << single->toString() << ", original cycle: "
1587  << oCycle << std::endl;
1588  }
1589  droppedNodes_.erase(single);
1590  assert(single->isScheduled());
1591  }
1592 }

References assert, bypassDestinations_, bypassDestinationsBus_, bypassDestinationsCycle_, MapTools::containsKey(), BasicBlockScheduler::ddg_, droppedNodes_, MoveNode::isScheduled(), MoveNode::move(), scheduleMove(), TTAProgram::Move::setBus(), MoveNode::toString(), DataDependenceGraph::unMergeUser(), BasicBlockScheduler::unschedule(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by bypassNode(), handleDDG(), scheduleOperation(), and scheduleResultReads().

Here is the call graph for this function:

◆ unscheduleAllNodes()

void BUBasicBlockScheduler::unscheduleAllNodes ( )
protected

Calls unschedule() for all ddg nodes, which were scheduled and remove possible bypasses.

Definition at line 1841 of file BUBasicBlockScheduler.cc.

1841  {
1843 
1844  for (DataDependenceGraph::NodeSet::iterator i = scheduled.begin();
1845  i != scheduled.end(); ++i) {
1846  MoveNode& moveNode = **i;
1847  if (moveNode.isScheduled()) {
1848  unschedule(moveNode);
1849  i = scheduled.begin();
1850  }
1851  }
1852  std::map<MoveNode*, std::vector<MoveNode*>, MoveNode::Comparator>::iterator it =
1853  bypassDestinations_.begin();
1854  for (; it != bypassDestinations_.end(); it++) {
1855  std::vector<MoveNode*> destinationsVector = (*it).second;
1856  for (unsigned int k = 0; k < destinationsVector.size(); k++) {
1857  // unschedule and unmerge all bypassed nodes
1858  MoveNode* dest = destinationsVector[k];
1859  ddg_->unMergeUser(*(*it).first, *dest);
1860  }
1861  }
1862  bypassDestinationsCycle_.clear();
1863  bypassDestinationsBus_.clear();
1864  bypassDestinations_.clear();
1865  droppedNodes_.clear();
1866  assert(ddg_->scheduledNodeCount() == 0);
1867 }

References assert, bypassDestinations_, bypassDestinationsBus_, bypassDestinationsCycle_, BasicBlockScheduler::ddg_, droppedNodes_, MoveNode::isScheduled(), DataDependenceGraph::scheduledMoves(), DataDependenceGraph::scheduledNodeCount(), DataDependenceGraph::unMergeUser(), and BasicBlockScheduler::unschedule().

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

Here is the call graph for this function:

Member Data Documentation

◆ bypass_

bool BUBasicBlockScheduler::bypass_
protected

◆ bypassDestinations_

std::map<MoveNode*, std::vector<MoveNode*>, MoveNode::Comparator> BUBasicBlockScheduler::bypassDestinations_
protected

◆ bypassDestinationsBus_

std::map<MoveNode*, std::vector<const TTAMachine::Bus*>, MoveNode::Comparator > BUBasicBlockScheduler::bypassDestinationsBus_
protected

◆ bypassDestinationsCycle_

std::map<MoveNode*, std::vector<int>, MoveNode::Comparator > BUBasicBlockScheduler::bypassDestinationsCycle_
protected

◆ bypassDistance_

int BUBasicBlockScheduler::bypassDistance_
protected

◆ dre_

bool BUBasicBlockScheduler::dre_
protected

◆ droppedNodes_

std::set<MoveNode*> BUBasicBlockScheduler::droppedNodes_
protected

◆ endCycle_

unsigned int BUBasicBlockScheduler::endCycle_
protected

◆ jumpMove_

MoveNode* BUBasicBlockScheduler::jumpMove_
protected

Definition at line 142 of file BUBasicBlockScheduler.hh.

Referenced by BUBasicBlockScheduler(), handleLoopDDG(), and scheduleMove().


The documentation for this class was generated from the following files:
ProgramOperation::operation
const Operation & operation() const
Definition: ProgramOperation.cc:590
DataDependenceGraph::lastScheduledRegisterRead
MoveNode * lastScheduledRegisterRead(const TTAMachine::BaseRegisterFile &rf, int registerIndex, int lastCycleToTest=INT_MAX) const
Definition: DataDependenceGraph.cc:766
RegisterCopyAdder::AddedRegisterCopies
Definition: RegisterCopyAdder.hh:104
BoostGraph::predecessors
virtual NodeSet predecessors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
TTAProgram::Terminal::isTriggering
virtual bool isTriggering() const
Definition: Terminal.cc:298
BasicBlockScheduler::ddg_
DataDependenceGraph * ddg_
DDG of the currently scheduled BB.
Definition: BasicBlockScheduler.hh:152
BoostGraph::connectNodes
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
Operation::writesMemory
virtual bool writesMemory() const
Definition: Operation.cc:252
DataDependenceGraph::removeIncomingGuardEdges
void removeIncomingGuardEdges(MoveNode &node)
Definition: DataDependenceGraph.cc:5466
BasicBlockScheduler::unschedule
void unschedule(MoveNode &moveNode)
Definition: BasicBlockScheduler.cc:1488
BUBasicBlockScheduler::findBypassDestinations
OrderedSet findBypassDestinations(MoveNode &node)
Definition: BUBasicBlockScheduler.cc:1488
BoostGraph::removeEdge
virtual void removeEdge(Edge &e)
DataDependenceGraph::regRawSuccessors
NodeSet regRawSuccessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4272
BUBasicBlockScheduler::scheduleResultReadTempMoves
void scheduleResultReadTempMoves(MoveNode &resultMove, MoveNode &resultRead, int lastUse)
Definition: BUBasicBlockScheduler.cc:1229
MoveNode::isDestinationVariable
bool isDestinationVariable() const
Definition: MoveNode.cc:264
BoostGraph::tailNode
virtual Node & tailNode(const Edge &edge) const
BUBasicBlockScheduler::undoBypass
void undoBypass(MoveNode &node, MoveNode *single=NULL, int originalCycle=-1)
Definition: BUBasicBlockScheduler.cc:1528
SimpleResourceManager::largestCycle
virtual int largestCycle() const override
Definition: SimpleResourceManager.cc:463
DataDependenceGraph::scheduledNodeCount
int scheduledNodeCount() const
Definition: DataDependenceGraph.cc:1859
MoveNode::toString
std::string toString() const
Definition: MoveNode.cc:576
Operation::hasSideEffects
virtual bool hasSideEffects() const
Definition: Operation.cc:272
MoveNodeGroup::node
MoveNode & node(int index) const
Definition: MoveNodeGroup.cc:152
TTAProgram::Terminal::index
virtual int index() const
Definition: Terminal.cc:274
BasicBlockScheduler::succeedingTempMove
MoveNode * succeedingTempMove(MoveNode &current)
Definition: BasicBlockScheduler.cc:1410
RegisterCopyAdder
Definition: RegisterCopyAdder.hh:91
DataDependenceGraph::firstScheduledRegisterWrite
MoveNode * firstScheduledRegisterWrite(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:847
TTAMachine::HWOperation
Definition: HWOperation.hh:52
BoostGraph::node
Node & node(const int index) const
BasicBlockPass::ddgBuilder_
DataDependenceGraphBuilder ddgBuilder_
Definition: BasicBlockPass.hh:100
DataDependenceGraph::resultUsed
bool resultUsed(MoveNode &resultNode)
Definition: DataDependenceGraph.cc:2348
TTAProgram::Terminal::registerFile
virtual const TTAMachine::RegisterFile & registerFile() const
Definition: Terminal.cc:225
MoveNode::isDestinationOperation
bool isDestinationOperation() const
TTAProgram::Move::isReturn
bool isReturn() const
Definition: Move.cc:259
BUBasicBlockScheduler::scheduleMove
void scheduleMove(MoveNode &move, int cycle, bool allowPredicationandRenaming)
Definition: BUBasicBlockScheduler.cc:960
DataDependenceGraph::findLoopLimitAndIndex
std::pair< MoveNode *, MoveNode * > findLoopLimitAndIndex(MoveNode &jumpMove)
Definition: DataDependenceGraph.cc:4618
BoostGraph< MoveNode, DataDependenceEdge >::NodeSet
std::set< MoveNode *, typename MoveNode ::Comparator > NodeSet
Definition: BoostGraph.hh:86
BasicBlockScheduler::selector_
MoveNodeSelector * selector_
Definition: BasicBlockScheduler.hh:167
SimpleResourceManager::smallestCycle
virtual int smallestCycle() const override
Definition: SimpleResourceManager.cc:480
TTAProgram::Move::isUnconditional
bool isUnconditional() const
Definition: Move.cc:154
BUBasicBlockScheduler::bypass_
bool bypass_
Definition: BUBasicBlockScheduler.hh:155
BUBasicBlockScheduler::OrderedSet
std::set< MoveNode *, ltstr > OrderedSet
Definition: BUBasicBlockScheduler.hh:97
ProgramOperation::isAnyOutputAssigned
bool isAnyOutputAssigned()
Definition: ProgramOperation.cc:451
TTAMachine::Bus
Definition: Bus.hh:53
TTAProgram::AnnotatedInstructionElement::setAnnotation
void setAnnotation(const ProgramAnnotation &annotation)
Definition: AnnotatedInstructionElement.cc:79
SchedulerCmdLineOptions::killDeadResults
virtual bool killDeadResults() const
Definition: SchedulerCmdLineOptions.cc:361
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
DataDependenceGraph::scheduledMoves
NodeSet scheduledMoves() const
Definition: DataDependenceGraph.cc:1375
Operation::numberOfInputs
virtual int numberOfInputs() const
Definition: Operation.cc:192
ProgramOperation::switchInputs
void switchInputs(int idx1=1, int idx2=2)
Definition: ProgramOperation.cc:795
ProgramOperation
Definition: ProgramOperation.hh:70
TTAProgram::Move::setGuard
void setGuard(MoveGuard *guard)
Definition: Move.cc:360
MoveNode
Definition: MoveNode.hh:65
MoveNode::isSourceConstant
bool isSourceConstant() const
Definition: MoveNode.cc:238
BasicBlockScheduler::unscheduleResultReadTempMoves
void unscheduleResultReadTempMoves(MoveNode &resultMove)
Definition: BasicBlockScheduler.cc:1553
BUMoveNodeSelector::mightBeReady
virtual void mightBeReady(MoveNode &node)
Definition: BUMoveNodeSelector.cc:237
BasicBlockScheduler::BasicBlockScheduler
BasicBlockScheduler(InterPassData &data, SoftwareBypasser *bypasser=NULL, RegisterRenamer *renamer=NULL)
Definition: BasicBlockScheduler.cc:85
BUMoveNodeSelector
Definition: BUMoveNodeSelector.hh:70
BasicBlockScheduler::options_
LLVMTCECmdLineOptions * options_
Definition: BasicBlockScheduler.hh:173
SimpleResourceManager::assign
virtual void assign(int cycle, MoveNode &node, const TTAMachine::Bus *bus=NULL, const TTAMachine::FunctionUnit *srcFU=NULL, const TTAMachine::FunctionUnit *dstFU=NULL, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) override
Definition: SimpleResourceManager.cc:221
DataDependenceEdge::EDGE_REGISTER
@ EDGE_REGISTER
Definition: DataDependenceEdge.hh:53
Application::logStream
static std::ostream & logStream()
Definition: Application.cc:155
MoveNodeGroup::nodeCount
int nodeCount() const
Definition: MoveNodeGroup.cc:140
SimpleResourceManager::initiationInterval
virtual unsigned initiationInterval() const
Definition: SimpleResourceManager.hh:135
Operation::name
virtual TCEString name() const
Definition: Operation.cc:93
DataDependenceEdge::dependenceType
DependenceType dependenceType() const
Definition: DataDependenceEdge.hh:88
SimpleResourceManager::unassign
virtual void unassign(MoveNode &node) override
Definition: SimpleResourceManager.cc:252
BoostGraph::dropNode
virtual void dropNode(Node &node)
DataDependenceGraph::onlyRegisterRawSource
MoveNode * onlyRegisterRawSource(const MoveNode &mn, int allowGuardEdges=2, int backEdges=0) const
Definition: DataDependenceGraph.cc:4083
LLVMTCECmdLineOptions::dumpDDGsDot
virtual bool dumpDDGsDot() const
Definition: LLVMTCECmdLineOptions.cc:359
Conversion::toString
static std::string toString(const T &source)
DataDependenceEdge::tailPseudo
bool tailPseudo() const
Definition: DataDependenceEdge.hh:109
BUBasicBlockScheduler::tryToSwitchInputs
bool tryToSwitchInputs(ProgramOperation &op)
Definition: BUBasicBlockScheduler.cc:1910
DataDependenceGraph::moveFUDependenciesToTrigger
void moveFUDependenciesToTrigger(MoveNode &trigger)
Definition: DataDependenceGraph.cc:4785
BasicBlockScheduler::minCycle_
int minCycle_
The earliest cycle to schedule moves in. Used to leave room for sched_yield() by the sched_yield() em...
Definition: BasicBlockScheduler.hh:165
BasicBlockScheduler::tripCount_
int tripCount_
Definition: BasicBlockScheduler.hh:177
SimValue
Definition: SimValue.hh:96
DataDependenceGraph::onlyRegisterRawDestinations
NodeSet onlyRegisterRawDestinations(const MoveNode &mn, bool allowGuardEdges=false, bool allowBackEdges=false) const
Definition: DataDependenceGraph.cc:4163
DataDependenceGraph::mergeAndKeepUser
bool mergeAndKeepUser(MoveNode &resultNode, MoveNode &userNode, bool force=false)
Definition: DataDependenceGraph.cc:2079
BUBasicBlockScheduler::clearRemovedNodes
void clearRemovedNodes()
Definition: BUBasicBlockScheduler.cc:1874
DataDependenceGraph::setCycleGrouping
virtual void setCycleGrouping(bool flag)
Definition: DataDependenceGraph.cc:1738
Operation::canSwap
virtual bool canSwap(int id1, int id2) const
Definition: Operation.cc:470
BasicBlockScheduler::findTrigger
static MoveNode * findTrigger(const ProgramOperation &po, const TTAMachine::Machine &mach)
Definition: BasicBlockScheduler.cc:2094
BasicBlockScheduler::targetMachine_
const TTAMachine::Machine * targetMachine_
The target machine we are scheduling the program against.
Definition: BasicBlockScheduler.hh:150
MoveNode::sourceOperation
ProgramOperation & sourceOperation() const
Definition: MoveNode.cc:453
assert
#define assert(condition)
Definition: Application.hh:86
TTAProgram::TerminalImmediate::value
virtual SimValue value() const
Definition: TerminalImmediate.cc:75
MoveNode::isMove
bool isMove() const
BasicBlockScheduler::ddgSnapshot
void ddgSnapshot(DataDependenceGraph &ddg, const std::string &name, DataDependenceGraph::DumpFileFormat format, bool final, bool resetCounter=false) const
Definition: BasicBlockScheduler.cc:1633
TTAMachine::Machine::controlUnit
virtual ControlUnit * controlUnit() const
Definition: Machine.cc:345
TTAProgram::Terminal::operationIndex
virtual int operationIndex() const
Definition: Terminal.cc:364
abortWithError
#define abortWithError(message)
Definition: Application.hh:72
BUBasicBlockScheduler::bypassNode
bool bypassNode(MoveNode &node, int &maxResultCycle)
Definition: BUBasicBlockScheduler.cc:1602
MoveNode::cycle
int cycle() const
Definition: MoveNode.cc:421
MoveNode::guardLatency
int guardLatency() const
Definition: MoveNode.cc:779
TTAProgram::Move::isControlFlowMove
bool isControlFlowMove() const
Definition: Move.cc:233
DataDependenceGraph::largestCycle
int largestCycle() const
Definition: DataDependenceGraph.cc:1838
BoostGraph::rootGraph
BoostGraph * rootGraph()
InvalidData
Definition: Exception.hh:149
BoostGraph< MoveNode, DataDependenceEdge >::EdgeSet
std::set< DataDependenceEdge *, typename DataDependenceEdge ::Comparator > EdgeSet
Definition: BoostGraph.hh:87
BoostGraph::removeNode
virtual void removeNode(Node &node)
BUBasicBlockScheduler::unscheduleAllNodes
void unscheduleAllNodes()
Definition: BUBasicBlockScheduler.cc:1841
BUBasicBlockScheduler::dre_
bool dre_
Definition: BUBasicBlockScheduler.hh:156
DataDependenceEdge::DEP_RAW
@ DEP_RAW
Definition: DataDependenceEdge.hh:47
RegisterRenamer::initialize
void initialize(DataDependenceGraph &ddg)
Definition: RegisterRenamer.cc:81
DataDependenceGraph::DUMP_XML
@ DUMP_XML
Definition: DataDependenceGraph.hh:87
CmdLineOptions
Definition: CmdLineOptions.hh:54
DataDependenceGraph::firstScheduledRegisterRead
MoveNode * firstScheduledRegisterRead(const TTAMachine::BaseRegisterFile &rf, int registerIndex, int firstCycleToTest=0) const
Definition: DataDependenceGraph.cc:808
TTAProgram::Move::guard
MoveGuard & guard() const
Definition: Move.cc:345
Application::cmdLineOptions
static CmdLineOptions * cmdLineOptions()
Definition: Application.cc:397
MachineConnectivityCheck::canSourceWriteToAnyDestinationPort
static int canSourceWriteToAnyDestinationPort(const MoveNode &src, PortSet &ports, bool ignoreGuard=false)
Definition: MachineConnectivityCheck.cc:1754
__func__
#define __func__
Definition: Application.hh:67
RegisterRenamer::renameSourceRegister
bool renameSourceRegister(MoveNode &node, bool loopScheduling, bool allowSameRf, bool differentRfOnlyDirectlyReachable, int latestCycle=INT_MAX)
Definition: RegisterRenamer.cc:617
MoveNode::latestTriggerWriteCycle
int latestTriggerWriteCycle() const
Definition: MoveNode.cc:698
RegisterCopyAdder::AddedRegisterCopies::count_
int count_
Definition: RegisterCopyAdder.hh:107
SimpleResourceManager::earliestCycle
virtual int earliestCycle(MoveNode &node, const TTAMachine::Bus *bus=NULL, const TTAMachine::FunctionUnit *srcFU=NULL, const TTAMachine::FunctionUnit *dstFU=NULL, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const override
Definition: SimpleResourceManager.cc:278
TTAProgram::Terminal::isGPR
virtual bool isGPR() const
Definition: Terminal.cc:107
GraphNode::Comparator
Definition: GraphNode.hh:56
BUBasicBlockScheduler::tryToOptimizeWaw
bool tryToOptimizeWaw(const MoveNode &moveNode)
Definition: BUBasicBlockScheduler.cc:1978
MoveNode::isSourceOperation
bool isSourceOperation() const
Definition: MoveNode.cc:168
DataDependenceGraph::smallestCycle
int smallestCycle() const
Definition: DataDependenceGraph.cc:1818
DataDependenceGraph::copyIncomingGuardEdges
void copyIncomingGuardEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:3865
TTAProgram::ProgramAnnotation::ANN_REQUIRES_LIMM
@ ANN_REQUIRES_LIMM
Definition: ProgramAnnotation.hh:125
DataDependenceGraph::DUMP_DOT
@ DUMP_DOT
Definition: DataDependenceGraph.hh:86
BasicBlockScheduler::unscheduleInputOperandTempMoves
void unscheduleInputOperandTempMoves(MoveNode &operandMove)
Definition: BasicBlockScheduler.cc:1532
TTAMachine::ControlUnit::delaySlots
int delaySlots() const
BUBasicBlockScheduler::finalizeSchedule
void finalizeSchedule(MoveNode &node, BUMoveNodeSelector &selector)
Definition: BUBasicBlockScheduler.cc:1744
ModuleRunTimeError
Definition: Exception.hh:1043
DataDependenceGraph::unMergeUser
void unMergeUser(MoveNode &resultNode, MoveNode &mergedNode, bool loopBypass=false)
Definition: DataDependenceGraph.cc:2240
LLVMTCECmdLineOptions
Definition: LLVMTCECmdLineOptions.hh:48
ProgramOperation::inputMoveCount
int inputMoveCount() const
Definition: ProgramOperation.cc:600
DataDependenceGraph::findLimitingAntidependenceDestination
MoveNode * findLimitingAntidependenceDestination(MoveNode &mn)
Definition: DataDependenceGraph.cc:5293
BoostGraph::hasNode
bool hasNode(const Node &) const
LLVMTCECmdLineOptions::dumpDDGsXML
virtual bool dumpDDGsXML() const
Definition: LLVMTCECmdLineOptions.cc:364
DataDependenceEdge::DEP_WAW
@ DEP_WAW
Definition: DataDependenceEdge.hh:49
Operation
Definition: Operation.hh:59
TTAProgram::AnnotatedInstructionElement::hasAnnotations
bool hasAnnotations(ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID) const
Definition: AnnotatedInstructionElement.cc:165
MoveNodeGroup::toString
std::string toString() const
Definition: MoveNodeGroup.cc:248
BUBasicBlockScheduler::bypassDestinationsBus_
std::map< MoveNode *, std::vector< const TTAMachine::Bus * >, MoveNode::Comparator > bypassDestinationsBus_
Definition: BUBasicBlockScheduler.hh:151
BoostGraph::inEdges
virtual EdgeSet inEdges(const Node &node) const
GraphBase::writeToDotFile
virtual void writeToDotFile(const TCEString &fileName) const
BUBasicBlockScheduler::jumpMove_
MoveNode * jumpMove_
Definition: BUBasicBlockScheduler.hh:142
BUBasicBlockScheduler::scheduleOperand
bool scheduleOperand(MoveNode &, int cycle)
Definition: BUBasicBlockScheduler.cc:1449
ProgramOperation::outputMoveCount
int outputMoveCount() const
Definition: ProgramOperation.cc:610
BasicBlockScheduler::renamer_
RegisterRenamer * renamer_
Definition: BasicBlockScheduler.hh:161
DataDependenceGraph::earliestCycle
int earliestCycle(const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegWaRs=false, bool ignoreRegWaWs=false, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false, bool assumeBypassing=false) const
Definition: DataDependenceGraph.cc:388
TTAProgram::Terminal::functionUnit
virtual const TTAMachine::FunctionUnit & functionUnit() const
Definition: Terminal.cc:251
SimValue::unsignedValue
unsigned int unsignedValue() const
Definition: SimValue.cc:919
BasicBlockScheduler::rm_
SimpleResourceManager * rm_
Resource Manager of the currently scheduled BB.
Definition: BasicBlockScheduler.hh:154
MoveNode::isSourceVariable
bool isSourceVariable() const
Definition: MoveNode.cc:196
TTAProgram::TerminalImmediate
Definition: TerminalImmediate.hh:44
BUBasicBlockScheduler::scheduleInputOperandTempMoves
void scheduleInputOperandTempMoves(MoveNode &resultMove, MoveNode &resultRead)
Definition: BUBasicBlockScheduler.cc:1290
MoveNode::destinationOperation
ProgramOperation & destinationOperation(unsigned int index=0) const
MoveNode::move
TTAProgram::Move & move()
BUBasicBlockScheduler::bypassDestinations_
std::map< MoveNode *, std::vector< MoveNode * >, MoveNode::Comparator > bypassDestinations_
Definition: BUBasicBlockScheduler.hh:145
SchedulerPass::interPassData
InterPassData & interPassData()
Definition: SchedulerPass.cc:53
SimValue::width
int width() const
Definition: SimValue.cc:103
MapTools::containsKey
static bool containsKey(const MapType &aMap, const KeyType &aKey)
BUBasicBlockScheduler::droppedNodes_
std::set< MoveNode * > droppedNodes_
Definition: BUBasicBlockScheduler.hh:152
TTAProgram::ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN
@ ANN_STACKFRAME_PROCEDURE_RETURN
precedure return jmp
Definition: ProgramAnnotation.hh:76
IllegalMachine
Definition: Exception.hh:878
BasicBlockScheduler::getTriggerOperand
int getTriggerOperand(const Operation &operation, const TTAMachine::Machine &machine)
Definition: BasicBlockScheduler.cc:1684
SimpleResourceManager::setMaxCycle
void setMaxCycle(unsigned int maxCycle)
Definition: SimpleResourceManager.cc:647
BUBasicBlockScheduler::scheduleRRMove
void scheduleRRMove(MoveNode &moveNode)
Definition: BUBasicBlockScheduler.cc:912
SimpleResourceManager::canTransportImmediate
virtual bool canTransportImmediate(const MoveNode &node, const TTAMachine::Bus *preAssignedBus=NULL) const
Definition: SimpleResourceManager.cc:411
DataDependenceGraph::exclusingGuards
bool exclusingGuards(const MoveNode &mn1, const MoveNode &mn2) const
Definition: DataDependenceGraph.cc:4480
BUBasicBlockScheduler::scheduleOperandWrites
bool scheduleOperandWrites(MoveNodeGroup &moves, int cycle)
Definition: BUBasicBlockScheduler.cc:664
RegisterRenamer::renameDestinationRegister
bool renameDestinationRegister(MoveNode &node, bool loopScheduling, bool allowSameRf, bool differentRfOnlyDirectlyReachable, int earliestCycle=-1)
Definition: RegisterRenamer.cc:458
TCEString
Definition: TCEString.hh:53
DataDependenceGraph::guardsAllowBypass
bool guardsAllowBypass(const MoveNode &defNode, const MoveNode &useNode, bool loopBypass=false)
Definition: DataDependenceGraph.cc:4543
BUMoveNodeSelector::notifyScheduled
virtual void notifyScheduled(MoveNode &node)
Definition: BUMoveNodeSelector.cc:209
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
RegisterRenamer::setSelector
void setSelector(MoveNodeSelector *selector)
Definition: RegisterRenamer.cc:1126
DataDependenceGraph::copyOutgoingGuardWarEdges
void copyOutgoingGuardWarEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:3897
SimpleResourceManager::latestCycle
virtual int latestCycle(MoveNode &node, const TTAMachine::Bus *bus=NULL, const TTAMachine::FunctionUnit *srcFU=NULL, const TTAMachine::FunctionUnit *dstFU=NULL, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const override
Definition: SimpleResourceManager.cc:349
BasicBlockScheduler::scheduledTempMoves_
std::map< const MoveNode *, DataDependenceGraph::NodeSet > scheduledTempMoves_
Stores the MoveNodes that were scheduled as temp moves during scheduling of the operand move.
Definition: BasicBlockScheduler.hh:157
MoveNode::isOperationMove
bool isOperationMove() const
Definition: MoveNode.cc:253
TTAProgram::CodeGenerator
Definition: CodeGenerator.hh:53
BUBasicBlockScheduler::bypassDistance_
int bypassDistance_
Definition: BUBasicBlockScheduler.hh:157
BUBasicBlockScheduler::scheduleOperation
void scheduleOperation(MoveNodeGroup &moves, BUMoveNodeSelector &selector)
Definition: BUBasicBlockScheduler.cc:455
TTAProgram::Terminal::equals
virtual bool equals(const Terminal &other) const =0
MoveNodeGroup::isScheduled
bool isScheduled() const
Definition: MoveNodeGroup.cc:164
DataDependenceEdge
Definition: DataDependenceEdge.hh:43
MoveNode::isScheduled
bool isScheduled() const
Definition: MoveNode.cc:409
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
SimpleResourceManager
Definition: SimpleResourceManager.hh:58
TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE
@ ANN_CONNECTIVITY_MOVE
A reg to reg move that was added because of missing connectivity between the original target and dest...
Definition: ProgramAnnotation.hh:123
TTAProgram::Terminal::port
virtual const TTAMachine::Port & port() const
Definition: Terminal.cc:378
TTAMachine::FunctionUnit::operation
virtual HWOperation * operation(const std::string &name) const
Definition: FunctionUnit.cc:363
TTAMachine::HWOperation::latency
int latency() const
Definition: HWOperation.cc:216
DataDependenceGraph::removeOutgoingGuardWarEdges
void removeOutgoingGuardWarEdges(MoveNode &node)
Definition: DataDependenceGraph.cc:5496
BUBasicBlockScheduler::bypassDestinationsCycle_
std::map< MoveNode *, std::vector< int >, MoveNode::Comparator > bypassDestinationsCycle_
Definition: BUBasicBlockScheduler.hh:147
TTAProgram::ProgramAnnotation
Definition: ProgramAnnotation.hh:49
MoveNodeGroup
Definition: MoveNodeGroup.hh:48
SchedulerCmdLineOptions::bypassDistance
virtual int bypassDistance() const
Definition: SchedulerCmdLineOptions.cc:327
TTAProgram::Terminal::isRA
virtual bool isRA() const
Definition: Terminal.cc:129
BoostGraph::name
virtual const TCEString & name() const
BUBasicBlockScheduler::precedingTempMove
MoveNode * precedingTempMove(MoveNode &current)
Definition: BUBasicBlockScheduler.cc:1425
debugLog
#define debugLog(text)
Definition: Application.hh:95
BUBasicBlockScheduler::scheduleResultReads
int scheduleResultReads(MoveNodeGroup &moves, int cycle, bool bypass=false, bool bypassLate=false)
Definition: BUBasicBlockScheduler.cc:805
DataDependenceGraph::copyDepsOver
EdgeSet copyDepsOver(MoveNode &node, bool anti, bool raw)
Definition: DataDependenceGraph.cc:2422
BoostGraph::nodeCount
int nodeCount() const
ProgramOperation::outputMove
MoveNode & outputMove(int index) const
Definition: ProgramOperation.cc:632
TTAProgram::Move::setBus
void setBus(const TTAMachine::Bus &bus)
Definition: Move.cc:383
Operation::affectsCount
virtual int affectsCount() const
Definition: Operation.cc:402
MachineConnectivityCheck::PortSet
std::set< const TTAMachine::Port *, const TTAMachine::MachinePart::Comparator > PortSet
Definition: MachineConnectivityCheck.hh:72
BUBasicBlockScheduler::endCycle_
unsigned int endCycle_
Definition: BUBasicBlockScheduler.hh:154
DataDependenceEdge::edgeReason
EdgeReason edgeReason() const
Definition: DataDependenceEdge.hh:91
BasicBlockScheduler::notifyScheduled
void notifyScheduled(MoveNodeGroup &moves, MoveNodeSelector &selector)
Definition: BasicBlockScheduler.cc:1602
TTAProgram::Move::setSource
void setSource(Terminal *src)
Definition: Move.cc:312
ProgramOperation::inputMove
MoveNode & inputMove(int index) const
Definition: ProgramOperation.cc:621
BasicBlockScheduler::schedulingTime_
boost::timer schedulingTime_
Time for getting the scheduling time for current basic block.
Definition: BasicBlockScheduler.hh:169
DataDependenceGraph::latestCycle
int latestCycle(const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegAntideps=false, bool ignoreUnscheduledSuccessors=true, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false) const
Definition: DataDependenceGraph.cc:543