OpenASIP  2.0
BUMoveNodeSelector.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2011 Tampere University.
3 
4  This file is part of TTA-Based Codesign Environment (TCE).
5 
6  Permission is hereby granted, free of charge, to any person obtaining a
7  copy of this software and associated documentation files (the "Software"),
8  to deal in the Software without restriction, including without limitation
9  the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  and/or sell copies of the Software, and to permit persons to whom the
11  Software is furnished to do so, subject to the following conditions:
12 
13  The above copyright notice and this permission notice shall be included in
14  all copies or substantial portions of the Software.
15 
16  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  DEALINGS IN THE SOFTWARE.
23  */
24 /**
25  * @file BUMoveNodeSelector.cc
26  *
27  * Implementation of BUMoveNodeSelector interface.
28  *
29  * @author Vladim’r Guzma 2011 (vladimir.guzma-no.spam-tut.fi)
30  * @note rating: red
31  */
32 
33 #include "BUMoveNodeSelector.hh"
34 #include "DataDependenceGraph.hh"
36 #include "POMDisassembler.hh"
37 #include "ProgramOperation.hh"
38 #include "Procedure.hh"
39 #include "BasicBlock.hh"
40 #include "SpecialRegisterPort.hh"
41 #include "Terminal.hh"
42 
43 //#define DEBUG_OUTPUT__
44 //#define WRITE_DOT_SNAPSHOTS
45 
46 //#define ABORT_ORPHAN_NODES
47 //#define WARN_ORPHAN_NODES
48 
49 #ifdef ABORT_ORPHAN_NODES
50 #define WARN_ORPHAN_NODES
51 #endif
52 
53 /**
54  * Add the unscheduled sink nodes of the DDG to the ready list
55  */
56 void
58  while (!readyList_.empty()) {
59  readyList_.pop();
60  }
62  for (DataDependenceGraph::NodeSet::iterator i = sinks.begin();
63  i != sinks.end();
64  ++i) {
65  MoveNode& node = **i;
66 
67  // a hack to avoid adding the root operations multiple times
68  // (the count of input moves): only "announce" the move to the first
69  // operand (every operation should have one input operand)
70  if (node.isDestinationOperation() && !node.move().destination().isFUPort()) {
71  std::cerr << "termimal not fuport even though dest op!: " << node.toString();
72  ddg_->writeToDotFile("not_dest_port.dot");
73  }
74  if (!node.isDestinationOperation())
75  mightBeReady(**i);
76  else if (node.move().destination().operationIndex() == 1) {
77  mightBeReady(**i);
78  }
79  }
80 }
81 
82 /**
83  * Constructor. Creates subgraph of the given big graph
84  *
85  * @param bigDDG big ddg containing more than just the basic block
86  * @param bb basic block for this selector.
87  */
91  : ddgOwned_(true) {
92  try {
93  ddg_ = bigDDG.createSubgraph(bb);
95  } catch (InstanceNotFound& inf) {
97  __FILE__,__LINE__,__func__,"Creation of subgraph failed");
98  e.setCause(inf);
99  throw e;
100  }
102 }
103 
104 /**
105  * Constructor.
106  *
107  * @param bb The basic block from which to select moves.
108  */
111  ddgOwned_(true) {
112  DataDependenceGraphBuilder ddgBuilder;
113  ddg_ = ddgBuilder.build(
117 #if 0
118  ddg_->setCycleGrouping(true);
119  ddg_->writeToDotFile("ddg.dot");
120 #endif
121 }
122 
123 /**
124  * Constructor.
125  *
126  * @param ddg The data dependence graph from which to select moves.
127  * Selector does not take the ownership of the ddg.
128  */
131  ddg_(&ddg), ddgOwned_(false) {
134 }
135 /**
136  * Destructor.
137  */
139  if (ddgOwned_) {
140  delete ddg_;
141  }
142 }
143 
144 /**
145  * Returns DDG used internally.
146  */
149  return *ddg_;
150 }
151 /**
152  * Returns a group of move nodes which should be scheduled next.
153  *
154  * @return Move node group.
155  */
158 
159  // find a MoveNodeGroup with unscheduled MoveNodes
160  while (readyList_.size() > 0) {
161  MoveNodeGroup moves = readyList_.top();
162  if (!moves.isAlive() || moves.isScheduled() ||
163  !isReadyToBeScheduled(moves))
164  readyList_.pop();
165  else
166  return moves;
167  }
168  // nothing in ready list, let's see if there are "orphan" nodes
169  // still to schedule
170  if (ddg_->nodeCount() - ddg_->scheduledNodeCount() > 0) {
172  for (DataDependenceGraph::NodeSet::iterator i = unscheduled.begin();
173  i != unscheduled.end();
174  ++i) {
175  MoveNode& node = **i;
176 #ifdef WARN_ORPHAN_NODES
177  std::cerr << "Found orphan node: " << node.toString() << " max src dist: "
178  << ddg_->maxSourceDistance(node) << " sink dist: " <<
179  ddg_->maxSinkDistance(node) << std::endl;
180  ddg_->writeToDotFile("oprhan.dot");
181 #ifdef ABORT_ORPHAN_NODES
182  abortWithError("orphan node!");
183 #endif
184 #endif
185  mightBeReady(node);
186  }
187  }
188 
189  // did we find new nodes?
190  while (readyList_.size() > 0) {
191  MoveNodeGroup moves = readyList_.top();
192  if (moves.isScheduled())
193  readyList_.pop();
194  else
195  return moves;
196  }
197 
198  // return an empty move node group
199  return MoveNodeGroup();
200 }
201 
202 /**
203  * This should be called by the client as soon as a MoveNode is scheduled
204  * in order to update the internal state of the selector.
205  *
206  * @param node The scheduled MoveNode.
207  */
208 void
210 
211  assert(node.isScheduled() && "Notifying scheduled even though it isn't.");
213  for (DataDependenceGraph::NodeSet::iterator i = pred.begin();
214  i != pred.end(); ++i) {
215  MoveNode& predecessor = **i;
216 
217  // we schedule operations as entities, so if the predecessor is a
218  // (operand) move, it's already in the ready list along with the
219  // move itself
220  if (!predecessor.inSameOperation(node))
221  mightBeReady(**i);
222  }
223 }
224 
225 /**
226  * Adds the given move node (along with the other possible move nodes in the
227  * same operation) to the ready list in case all its children in the DDG have
228  * been scheduled.
229  *
230  * In case the node belongs to an operation, also checks that the other
231  * result moves are also ready. In that case adds all the nodes in the said
232  * MoveOperation to the ready list in a single MoveNodeGroup.
233  *
234  * @param node Move node that might be ready.
235  */
236 void
238 
239  if (node.isScheduled()) {
240  return;
241  }
242 
245  queue.insert(&node);
246 
247  while (!queue.empty()) {
248  MoveNode* mn = *queue.begin();
249  nodes.insert(mn);
250  queue.erase(mn);
251  if (mn->isSourceOperation()) {
252  queueOperation(mn->sourceOperation(), nodes, queue);
253  }
254 
255  for (unsigned int i = 0; i < mn->destinationOperationCount(); i++) {
256  queueOperation(mn->destinationOperation(i), nodes, queue);
257  }
258 
259  if (mn->move().source().isUniversalMachineRegister()) {
260  if (ddg_->hasNode(*mn)) {
261  MoveNode* bypassSrc =
263  if (bypassSrc != NULL) {
264  if (nodes.find(bypassSrc) == nodes.end()) {
265  queue.insert(bypassSrc);
266  }
267  } else {
268  std::cerr << "Warning: Cannot find source for forced bypass. "
269  << " Instruction scheduler may fail/deadlock" << std::endl;
270  }
271  }
272  }
274  if (ddg_->hasNode(*mn)) {
275  DataDependenceGraph::NodeSet rrDestinations =
276  ddg_->onlyRegisterRawDestinations(*mn, false, false);
277  for (DataDependenceGraph::NodeSet::iterator j =
278  rrDestinations.begin(); j != rrDestinations.end(); j++) {
279  MoveNode* n = *j;
280  if (nodes.find(n) == nodes.end()) {
281  queue.insert(n);
282  }
283  }
284  }
285  }
286  }
287 
288  if (!isReadyToBeScheduled(nodes)) {
289  return;
290  }
291 
292 
293  if (!nodes.empty()) {
294  MoveNodeGroup moves(*ddg_);
295  for (DataDependenceGraph::NodeSet::iterator i = nodes.begin(); i != nodes.end(); i++) {
296  if (!((**i).isScheduled())) {
297  moves.addNode(**i);
298  }
299  }
300  if (moves.nodeCount()) {
301  readyList_.push(moves);
302  }
303  }
304 
305 }
306 
307 /**
308  * Queues all nodes of PO into queue, if they are not already in another set.
309  *
310  * @param po ProgramOperation whose nodes to add
311  * @param nodes nodes where the final result is. if node is here, do not add
312  * to queue
313  * @param queue quque where to add the nodes.
314  */
316  ProgramOperation& po,
317  const DataDependenceGraph::NodeSet& nodes,
319  for (int j = 0; j < po.inputMoveCount(); j++) {
320  MoveNode& inputMove = po.inputMove(j);
321  // only add if not already added
322  if (nodes.find(&inputMove) == nodes.end()) {
323  queue.insert(&inputMove);
324  }
325  }
326 
327  for (int j = 0; j < po.outputMoveCount(); j++) {
328  MoveNode& outputMove = po.outputMove(j);
329  // only add if not already added
330  if (nodes.find(&outputMove) == nodes.end()) {
331  queue.insert(&outputMove);
332  }
333  }
334 }
335 
336 /**
337  * Returns true in case the move is "data ready", that is, all its
338  * successors have been scheduled.
339  *
340  * It should be noted that moves within same operation are treated
341  * specially. Additionally, as we are considering a basic block
342  * at a time, the branch operation is considered always ready before
343  * all the other moves in the basic block have been scheduled.
344  *
345  * @param node Move to check.
346  * @return True if the move is ready to be scheduled.
347  */
348 bool
350  const {
351 
352  for (DataDependenceGraph::NodeSet::iterator i = nodes.begin(); i != nodes.end(); i++) {
353  MoveNode& node = **i;
354  if (!isReadyToBeScheduled(node, nodes)) {
355  return false;
356  }
357  }
358  return true;
359 }
360 
361 bool
363  const {
364  if (!ddg_->hasNode(node)) {
365  return true;
366  }
367 
368  return ddg_->otherSuccessorsScheduled(node, nodes);
369 }
370 
371 bool
374  for (int i = 0; i < nodes.nodeCount(); i++) {
375  MoveNode& mn = nodes.node(i);
376  ns.insert(&mn);
377  }
378  return isReadyToBeScheduled(ns);
379 }
TTAProgram::Terminal::isFUPort
virtual bool isFUPort() const
Definition: Terminal.cc:118
BoostGraph::predecessors
virtual NodeSet predecessors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
MoveNodeGroup::isAlive
bool isAlive() const
Definition: MoveNodeGroup.cc:190
DataDependenceGraph::scheduledNodeCount
int scheduledNodeCount() const
Definition: DataDependenceGraph.cc:1859
MoveNode::toString
std::string toString() const
Definition: MoveNode.cc:576
MoveNodeGroup::node
MoveNode & node(int index) const
Definition: MoveNodeGroup.cc:152
machine
TTAMachine::Machine * machine
the architecture definition of the estimated processor
Definition: EstimatorCmdLineUI.cc:59
BUMoveNodeSelector::dataDependenceGraph
virtual DataDependenceGraph & dataDependenceGraph()
Definition: BUMoveNodeSelector.cc:148
BoostGraph::maxSourceDistance
int maxSourceDistance(const GraphNode &node) const
MoveNode::isDestinationOperation
bool isDestinationOperation() const
BoostGraph< MoveNode, DataDependenceEdge >::NodeSet
std::set< MoveNode *, typename MoveNode ::Comparator > NodeSet
Definition: BoostGraph.hh:86
Procedure.hh
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
BUMoveNodeSelector::candidates
virtual MoveNodeGroup candidates()
Definition: BUMoveNodeSelector.cc:157
Exception::setCause
void setCause(const Exception &cause)
Definition: Exception.cc:75
DataDependenceGraph.hh
ProgramOperation
Definition: ProgramOperation.hh:70
DataDependenceGraph::setMachine
void setMachine(const TTAMachine::Machine &machine)
Definition: DataDependenceGraph.cc:3116
MoveNode
Definition: MoveNode.hh:65
BUMoveNodeSelector.hh
BUMoveNodeSelector::mightBeReady
virtual void mightBeReady(MoveNode &node)
Definition: BUMoveNodeSelector.cc:237
Terminal.hh
MoveNodeGroup::nodeCount
int nodeCount() const
Definition: MoveNodeGroup.cc:140
DataDependenceGraph::onlyRegisterRawSource
MoveNode * onlyRegisterRawSource(const MoveNode &mn, int allowGuardEdges=2, int backEdges=0) const
Definition: DataDependenceGraph.cc:4083
DataDependenceGraph::onlyRegisterRawDestinations
NodeSet onlyRegisterRawDestinations(const MoveNode &mn, bool allowGuardEdges=false, bool allowBackEdges=false) const
Definition: DataDependenceGraph.cc:4163
POMDisassembler.hh
DataDependenceGraph::setCycleGrouping
virtual void setCycleGrouping(bool flag)
Definition: DataDependenceGraph.cc:1738
TTAProgram::Terminal::isUniversalMachineRegister
virtual bool isUniversalMachineRegister() const
Definition: Terminal.cc:166
MoveNode::sourceOperation
ProgramOperation & sourceOperation() const
Definition: MoveNode.cc:453
assert
#define assert(condition)
Definition: Application.hh:86
DataDependenceGraph::createSubgraph
DataDependenceGraph * createSubgraph(NodeSet &nodes, bool includeLoops=false)
Definition: DataDependenceGraph.cc:3377
DataDependenceGraphBuilder.hh
TTAProgram::Terminal::operationIndex
virtual int operationIndex() const
Definition: Terminal.cc:364
abortWithError
#define abortWithError(message)
Definition: Application.hh:72
BUMoveNodeSelector::readyList_
ReadyMoveNodeGroupListBU readyList_
The prioritized ready list.
Definition: BUMoveNodeSelector.hh:103
DataDependenceGraph::INTRA_BB_ANTIDEPS
@ INTRA_BB_ANTIDEPS
Definition: DataDependenceGraph.hh:80
__func__
#define __func__
Definition: Application.hh:67
DataDependenceGraph::otherSuccessorsScheduled
bool otherSuccessorsScheduled(MoveNode &node, const NodeSet &ignoredNodes) const
Definition: DataDependenceGraph.cc:3266
BoostGraph::maxSinkDistance
int maxSinkDistance(const GraphNode &node) const
MoveNode::isSourceOperation
bool isSourceOperation() const
Definition: MoveNode.cc:168
BoostGraph::sinkNodes
virtual NodeSet sinkNodes() const
BUMoveNodeSelector::ddg_
DataDependenceGraph * ddg_
The data dependence graph built from the basic block.
Definition: BUMoveNodeSelector.hh:101
ModuleRunTimeError
Definition: Exception.hh:1043
MoveNode::destinationOperationCount
unsigned int destinationOperationCount() const
ProgramOperation::inputMoveCount
int inputMoveCount() const
Definition: ProgramOperation.cc:600
BoostGraph::hasNode
bool hasNode(const Node &) const
BUMoveNodeSelector::ddgOwned_
bool ddgOwned_
Definition: BUMoveNodeSelector.hh:105
GraphBase::writeToDotFile
virtual void writeToDotFile(const TCEString &fileName) const
ProgramOperation::outputMoveCount
int outputMoveCount() const
Definition: ProgramOperation.cc:610
ProgramOperation.hh
MoveNodeGroup::addNode
void addNode(MoveNode &node)
Definition: MoveNodeGroup.cc:70
MoveNode::destinationOperation
ProgramOperation & destinationOperation(unsigned int index=0) const
TTAProgram::BasicBlock
Definition: BasicBlock.hh:85
MoveNode::move
TTAProgram::Move & move()
BUMoveNodeSelector::queueOperation
static void queueOperation(ProgramOperation &po, const DataDependenceGraph::NodeSet &nodes, DataDependenceGraph::NodeSet &queue)
Definition: BUMoveNodeSelector.cc:315
false
find Finds info of the inner loops in the false
Definition: InnerLoopFinder.cc:81
DataDependenceGraphBuilder
Definition: DataDependenceGraphBuilder.hh:70
MoveNode::inSameOperation
bool inSameOperation(const MoveNode &other) const
Definition: MoveNode.cc:306
BUMoveNodeSelector::notifyScheduled
virtual void notifyScheduled(MoveNode &node)
Definition: BUMoveNodeSelector.cc:209
BasicBlock.hh
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
SpecialRegisterPort.hh
DataDependenceGraphBuilder::build
virtual DataDependenceGraph * build(ControlFlowGraph &cGraph, DataDependenceGraph::AntidependenceLevel antidependenceLevel, const TTAMachine::Machine &mach, const UniversalMachine *um=NULL, bool createMemAndFUDeps=true, bool createDeathInformation=true, llvm::AliasAnalysis *AA=NULL)
Definition: DataDependenceGraphBuilder.cc:2120
BUMoveNodeSelector::~BUMoveNodeSelector
virtual ~BUMoveNodeSelector()
Definition: BUMoveNodeSelector.cc:138
MoveNodeGroup::isScheduled
bool isScheduled() const
Definition: MoveNodeGroup.cc:164
MoveNode::isScheduled
bool isScheduled() const
Definition: MoveNode.cc:409
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
MoveNodeGroup
Definition: MoveNodeGroup.hh:48
BUMoveNodeSelector::isReadyToBeScheduled
bool isReadyToBeScheduled(DataDependenceGraph::NodeSet &nodes) const
Definition: BUMoveNodeSelector.cc:349
BoostGraph::nodeCount
int nodeCount() const
ProgramOperation::outputMove
MoveNode & outputMove(int index) const
Definition: ProgramOperation.cc:632
BUMoveNodeSelector::initializeReadylist
virtual void initializeReadylist()
Initializes ready list from nodes that are ready.
Definition: BUMoveNodeSelector.cc:57
DataDependenceGraph::unscheduledMoves
NodeSet unscheduledMoves() const
Definition: DataDependenceGraph.cc:1355
InstanceNotFound
Definition: Exception.hh:304
ProgramOperation::inputMove
MoveNode & inputMove(int index) const
Definition: ProgramOperation.cc:621
TTAMachine::Machine
Definition: Machine.hh:73
BUMoveNodeSelector::BUMoveNodeSelector
BUMoveNodeSelector(TTAProgram::BasicBlock &bb, const TTAMachine::Machine &machine)
Definition: BUMoveNodeSelector.cc:109