OpenASIP  2.0
DataDependenceGraph.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2020 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 DataDependenceGraph.cc
26  *
27  * Implementation of data dependence graph class
28  *
29  * @author Heikki Kultala 2006-2012 (heikki.kultala-no.spam-tut.fi)
30  * @author Pekka Jääskeläinen 2010-2012
31  * @author Fabio Garzia 2010 (fabio.garzia-no.spam-tut.fi)
32 
33  * @note rating: red
34  */
35 
36 #include "StringTools.hh"
37 #include "AssocTools.hh"
38 #include "DataDependenceGraph.hh"
39 #include "DataDependenceEdge.hh"
40 #include "ProgramOperation.hh"
41 #include "Application.hh"
42 #include "ImmediateUnit.hh"
43 #include "ControlUnit.hh"
44 #include "Guard.hh"
45 #include "MoveGuard.hh"
46 #include "HWOperation.hh"
47 #include "CodeSnippet.hh"
48 #include "Instruction.hh"
49 #include "POMDisassembler.hh"
50 #include "BasicBlockNode.hh"
51 #include "TCEString.hh"
52 #include "Guard.hh"
53 #include "MachineAnalysis.hh"
54 #include "LiveRange.hh"
55 #include "DisassemblyRegister.hh"
56 #include "ObjectState.hh"
57 #include "XMLSerializer.hh"
58 #include "MoveNodeSet.hh"
59 #include "LiveRangeData.hh"
60 #include "LiveRange.hh"
61 #include "Terminal.hh"
62 #include "BasicBlock.hh"
63 #include "Operation.hh"
64 #include "Move.hh"
65 #include "UniversalMachine.hh"
66 
67 /**
68  * Constructor.
69  *
70  * @param name The graph can be named for debugging purposes.
71  * @param containsProcedure whether the DDG contains complete procedure.
72  * @param ownedBBN if the DDG should delete a BBn at destructor.
73  * @param containsProcedure if the ddg contains a whole procedure.
74  * @param if the ddg should not accept loop edges.
75  * @param antidependenceLevel level of register antidependencies which this
76  * ddg should contain.
77  */
79  std::set<TCEString> allParamRegs,
80  const TCEString& name, AntidependenceLevel antidependenceLevel,
81  BasicBlockNode* ownedBBN, bool containsProcedure,
82  bool noLoopEdges) :
83  BoostGraph<MoveNode, DataDependenceEdge>(name, !noLoopEdges),
84  allParamRegs_(allParamRegs), cycleGrouping_(true),
85  dotProgramOperationNodes_(false),
86  machine_(NULL), delaySlots_(0), rrCost_(3), ownedBBN_(ownedBBN),
87  procedureDDG_(containsProcedure),
88  registerAntidependenceLevel_(antidependenceLevel),
89  edgeWeightHeuristics_(EWH_HEURISTIC) {
90 }
91 
92 /**
93  * Deletes all MoveNodes and ProgramOperations.
94  */
96 
97  if (parentGraph_ == NULL) {
98 
99  //delete nodes.
100  int nc = nodeCount();
101  for (int i = 0; i < nc; i++) {
102  delete &node(i, false);
103  }
104  programOperations_.clear();
105  }
106  if (ownedBBN_ != NULL) {
107  delete ownedBBN_;
108  }
109 }
110 
111 /**
112  * Sets bookkeeping that the given movende belongs to the given basic block.
113  *
114  * @param mn MoveNode given
115  * @param bblock Basic Block node where the move node belongs
116  * @param modifier modifier graph on the subgraph tree
117  */
118 void
120  MoveNode& mn, BasicBlockNode& bblock, DataDependenceGraph* modifier) {
121  moveNodeBlocks_[&mn] = &bblock;
122 
123  if (parentGraph_ != NULL && parentGraph_ != modifier) {
124  static_cast<DataDependenceGraph*>(parentGraph_)->
125  setNodeBB(mn, bblock, this);
126  }
127 
128  for (unsigned int i = 0; i < childGraphs_.size(); i++) {
129  if ( childGraphs_[i] != modifier ) {
130  static_cast<DataDependenceGraph*>(childGraphs_[i])->
131  setNodeBB(mn,bblock,this);
132  }
133  }
134 }
135 
136 /**
137  * Adds a node into the graph.
138  *
139  * This method should not be called by the user, used internally
140  *
141  * @param moveNode moveNode being added.
142  */
143 void
146  if (moveNode.isMove()) {
147  nodesOfMoves_[&moveNode.move()] = &moveNode;
148  }
149 }
150 
151 /**
152  * Adds a node into the graph.
153  *
154  * @param moveNode moveNode being added.
155  * @param bblock Basic block where the move logically belongs.
156  */
157 void
159  addNode(moveNode);
160  setNodeBB(moveNode, bblock, NULL);
161 }
162 
163 /**
164  * Adds a node into the graph.
165  *
166  * @param moveNode moveNode being added.
167  * @param relatedNode another node already existing in the graph
168  * where this movenode relates to. , for example is created by
169  * splitting that
170  */
171 void
173  addNode(moveNode);
174  setNodeBB(moveNode, getBasicBlockNode(relatedNode), NULL);
175  /// @todo: also add to subgrapsh which have the related node?
176 }
177 
178 
179 /**
180  * Gives the basic block node where the node belongs to.
181  *
182  * @param mn MoveNode whose basic block we are asking
183  * @return BasicBlockNode of the move
184  */
185 const BasicBlockNode&
187  std::map<const MoveNode*, BasicBlockNode*>::const_iterator iter =
188  moveNodeBlocks_.find(&mn);
189  if (iter == moveNodeBlocks_.end()) {
190  TCEString msg = "MoveNode not in DDG!: ";
191  msg += mn.toString();
192  throw InvalidData(__FILE__,__LINE__,__func__,msg);
193  }
194  return *iter->second;
195 }
196 
197 /**
198  * Gives the basic block node where the node belongs to.
199  *
200  * @param mn MoveNode whose basic block we are asking
201  * @return BasicBlockNode of the move
202  */
205  std::map<const MoveNode*, BasicBlockNode*>::iterator iter =
206  moveNodeBlocks_.find(&mn);
207  if (iter == moveNodeBlocks_.end()) {
208  TCEString msg = "MoveNode not in DDG!: ";
209  msg += mn.toString();
210  throw InvalidData(__FILE__,__LINE__,__func__,msg);
211  }
212  return *iter->second;
213 }
214 
215 void
217  const MoveNode& mn, BasicBlockNode& bbn) {
218  moveNodeBlocks_[&mn] = &bbn;
219 }
220 
221 /**
222  * Returs programoperation which is in this graph.
223  *
224  * @param index index of the programoperation.
225  */
228  return *programOperations_.at(index);
229 }
230 
231 const ProgramOperation&
233  return *programOperations_.at(index);
234 }
235 
238  return programOperations_.at(index);
239 }
240 
241 
242 /**
243  * Returns the number of programoperations in this ddg.
244  */
245 int
247  return programOperations_.size();
248 }
249 
250 /**
251  * Returns the only incoming register edge to a node.
252  * If none or multiple, returns NULL.
253  */
256 
257  DataDependenceEdge* result = NULL;
258  for (int i = 0; i < inDegree(mn); i++) {
259  DataDependenceEdge &edge = inEdge(mn, i);
261  if (result == NULL) {
262  result = &edge;
263  } else {
264  return NULL;
265  }
266  }
267  }
268  return result;
269 }
270 
271 /**
272  * Returns the only outgoing register edge from a node.
273  * If none or multiple, returns NULL.
274  */
277 
278  DataDependenceEdge* result = NULL;
279  for (int i = 0; i < outDegree(mn); i++) {
280  DataDependenceEdge &edge = outEdge(mn, i);
282  if (result == NULL) {
283  result = &edge;
284  } else {
285  return NULL;
286  }
287  }
288  }
289  return result;
290 }
291 
292 /**
293  * Adds a program operation to the graph, and its parent graphs.
294  *
295  * @param po ProgramOperation being added.
296  */
297 void
299  for (int i = 0; i < programOperationCount(); i++) {
300  if (programOperations_[i] == po) {
301  return;
302  }
303  }
304  programOperations_.push_back(po);
305  if (parentGraph_ != NULL) {
306  dynamic_cast<DataDependenceGraph*>(parentGraph_)
307  ->addProgramOperation(po);
308  }
309 }
310 
312  int ii,
313  const MoveNode* tail,
314  const MoveNode* head) const {
315 
316  int latency = 1;
318  if (head == NULL) {
319  head = &headNode(edge);
320  }
321  if (head->isSourceOperation()) {
322  if (tail == NULL) {
323  tail = &tailNode(edge);
324  }
325  if (tail->inSameOperation(*head)) {
326  latency = getOperationLatency(edge.data());
327  }
328  }
330  latency = 0;
331  }
332 
333  if (edge.headPseudo()) {
334  latency -= delaySlots_;
335  }
336 
337  if (edge.tailPseudo()) {
338  latency += delaySlots_;
339  }
340 
341  if (edge.guardUse()) {
343  latency += (head->guardLatency()-1);
344  } else {
346  latency -= (tail->guardLatency()-1);
347  } else {
348  std::cerr << "invalid guard edge: " << edge.toString();
349  }
350  }
351  }
352  return latency - ii*edge.loopDepth();
353 }
354 
355 /**
356  * Drops a program operation to the graph, but not its parent graphs.
357  *
358  * @param po ProgramOperation being added.
359  */
360 void
362  for (auto i = programOperations_.begin();
363  i != programOperations_.end();i++) {
364  if (*i == po) {
365  programOperations_.erase(i);
366  return;
367  }
368  }
369 }
370 
371 
372 /**
373  * Returns the earliest cycle this move can be scheduled at given the
374  * cycles of the dependencies.
375  *
376  * Checks all the parent nodes of the move in the DDG and finds their max
377  * cycle if they are scheduled, if none found, 0 is returned, if at least one
378  * of the preceeding nodes is unscheduled, returns INT_MAX.
379  *
380  * @param moveNode The move node for which to find the earliest cycle.
381  * @param assumeBypassing If the preceeding MoveNodes are register writes,
382  * assume a reading MoveNode will be able to bypass
383  * from the source to save a cycle.
384  * @return The earliest cycle the move can be scheduled to according to
385  * data dependencies, INT_MAX if unknown.
386  */
387 int
389  const MoveNode& moveNode, unsigned int ii, bool ignoreRegWaRs,
390  bool ignoreRegWaWs, bool ignoreGuards, bool ignoreFuDeps,
391  bool ignoreSameOperationEdges, bool assumeBypassing) const {
392 
393  if (machine_ == NULL) {
394  throw InvalidData(__FILE__,__LINE__,__func__,
395  " setMachine() must be called before this");
396  }
397  const EdgeSet edges = inEdges(moveNode);
398  int minCycle = 0;
399  for (EdgeSet::const_iterator i = edges.begin(); i != edges.end(); ++i) {
400  DataDependenceEdge& edge = **i;
401 
402  if (ignoreGuards && edge.guardUse()) {
403  continue;
404  }
405 
406  if (ignoreFuDeps &&
409  continue;
410  }
411 
412  if (ignoreSameOperationEdges &&
414  continue;
415  }
416 
417  MoveNode& tail = tailNode(edge);
418  if (&tail == &moveNode) {
419  continue;
420  }
421 
422  if (ignoreSameOperationEdges && !edge.isBackEdge() &&
423  moveNode.isSourceOperation() &&
424  tail.isDestinationOperation() &&
425  &moveNode.sourceOperation() == &tail.destinationOperation()) {
426  continue;
427  }
428 
429 
430  if (tail.isPlaced()) {
431  int effTailCycle = tail.cycle();
432 
433  // If call, make sure all incoming deps fit into delay slots,
434  // can still be later than the call itself
435  // dependence type does not matter.
436  if (edge.headPseudo()) {
437  effTailCycle -= delaySlots_;
438  } else {
439  /// @todo clean this up: should be the same code as the edgeWeight
440  /// when EWH_REAL is used.
442  moveNode.isSourceOperation() && tail.inSameOperation(moveNode)) {
443  effTailCycle += getOperationLatency(edge.data());
445 
446  // ignore reg antidep? then skip over this edge.
448  && !edge.headPseudo() &&
449  ignoreRegWaWs) {
450  continue;
451  }
452  // latency does not matter with WAW. always +1.
453  effTailCycle += 1;
454  } else {
455  int latency;
456  if (assumeBypassing) {
457  latency = 0;
458  } else {
459  latency = 1;
460  }
462  // ignore reg antidep? then skip over this edge.
463  if (edge.edgeReason() ==
465  !edge.headPseudo() && ignoreRegWaRs) {
466  continue;
467  }
468 
469  // WAR allows writing at same cycle than reading.
470  // in WAR also the latency goes backwards,
471  // new value can
472  // be written before old is read is latency is big.
473  if (edge.guardUse()) {
474  latency = tail.guardLatency();
475  }
476 
477  // TODO: generate some hasAutomaticBundling()
478  // property to ADF
480  latency = 0;
481  }
482  effTailCycle = effTailCycle - latency + 1;
483  } else {
484  // RAW
485  if (edge.guardUse()) {
486  latency = moveNode.guardLatency();
487  }
488  // in case of RAW, we have to wait latency cycles
489  // before we can use the written value.
490  effTailCycle += latency;
491  }
492  }
493  }
494 
495  assert ((ii != 0 || edge.loopDepth() ==0) &&
496  "ii should not be 0 if we have an loop edge");
497 
498  effTailCycle -= (ii * edge.loopDepth());
499  minCycle = std::max(effTailCycle, minCycle);
500  }
501  }
502 
503  // on architectures with hw data hazard detection this is needed.
504  // TODO: now does this for all input moves, not just trigger
506  moveNode.isDestinationOperation()) {
507 
508  ProgramOperation& po = moveNode.destinationOperation();
509  MoveNode* trigger = po.triggeringMove();
510  if (trigger == nullptr || trigger == &moveNode) {
511  for (int i = 0; i < po.outputMoveCount(); i++) {
512  MoveNode& outMove = po.outputMove(i);
513  if (hasNode(outMove)) {
514  minCycle =
515  std::max(minCycle,
516  earliestCycle(outMove, ii,
517  ignoreRegWaRs,
518  ignoreRegWaWs,
519  ignoreGuards,
520  true, // ignoreFuDeps
521  true)); // operation edges ignored
522  }
523  }
524  }
525  }
526  return minCycle;
527 }
528 
529 /**
530  * Returns the latest cycle this move can be scheduled at given the
531  * cycles of the dependencies.
532  *
533  * This is assumed to be used with bottom-up scheduling.
534  * Checks all successor nodes and checks their min cycle if they are scheduled.
535  * If none found, INT_MAX is returned, if at least one of successors is
536  * unscheduled, returns 0.
537  *
538  * @param moveNode The move node for which to find the latest cycle.
539  * @return The latest cycle the move can be scheduled to according to
540  * data dependencies, 0 if unknown.
541  */
542 int
544  const MoveNode& moveNode, unsigned int ii, bool ignoreRegAntideps,
545  bool ignoreUnscheduledSuccessors, bool ignoreGuards, bool ignoreFuDeps,
546  bool ignoreSameOperationEdges) const {
547 
548  if (machine_ == NULL) {
549  throw InvalidData(__FILE__,__LINE__,__func__,
550  " setMachine() must be called before this");
551  }
552 
553  const EdgeSet edges = outEdges(moveNode);
554  int maxCycle = INT_MAX;
555  for (EdgeSet::const_iterator i = edges.begin();
556  i != edges.end(); ++i) {
557  DataDependenceEdge& edge = **i;
558 
559  if (ignoreGuards && edge.guardUse()) {
560  continue;
561  }
562  if (ignoreFuDeps &&
565  continue;
566  }
567 
568  if (ignoreSameOperationEdges &&
570  continue;
571  }
572 
573  MoveNode& head = headNode(edge);
574  if (&head == &moveNode) {
575  continue;
576  }
577 
578  /// @todo Consider the latency for result read move!
579  if (head.isPlaced()) {
580  int latency = 1;
581  int effHeadCycle = head.cycle();
582 
583  // If call, make sure all incoming deps fit into delay slots,
584  // can still be later than the call itself
585  // dependence type does not matter.
586  if (edge.headPseudo()) {
587  effHeadCycle += delaySlots_;
588  } else {
590 
591  // ignore deg antidep? then skip over this edge.
593  && !edge.tailPseudo() && ignoreRegAntideps) {
594  continue;
595  }
596 
597  // latency does not matter with WAW. always +1.
598  effHeadCycle -= 1;
599  } else {
601 
602  // ignore deg antidep? then skip over this edge.
603  if (edge.edgeReason() ==
605  !edge.tailPseudo() && ignoreRegAntideps) {
606  continue;
607  }
608 
609  // WAR allows writing at same cycle than reading.
610  // in WAR also the latency goes backwards,
611  // new value can
612  // be written before old is read is latency is big.
613  if (edge.guardUse()) {
614  latency = moveNode.guardLatency();
615  }
616  // TODO: generate some hasAutomaticBundling()
617  // property to ADF
619  latency = 0;
620  }
621  effHeadCycle = effHeadCycle + latency - 1;
622  } else {
623  // RAW
624  if (edge.guardUse()) {
625  latency = head.guardLatency();
626  } else {
627  if (edge.edgeReason() ==
629  moveNode.isDestinationOperation() &&
630  head.inSameOperation(moveNode)) {
631  latency = getOperationLatency(edge.data());
632  }
633  }
634  // in case of RAW, value must be written latency
635  // cycles before it is used
636  effHeadCycle -= latency;
637  }
638  }
639  }
640 
641  assert ((ii != 0 || edge.loopDepth() ==0) &&
642  "ii should not be 0 if we have an loop edge");
643  effHeadCycle += (ii * edge.loopDepth());
644 
645  maxCycle = std::min(effHeadCycle, maxCycle);
646  } else {
647  if (!edge.isBackEdge()) {
648  if (!ignoreUnscheduledSuccessors) {
649  return -1;
650  }
651  }
652  }
653 
654  // TODO: now does this for all input moves, not just trigger
656  head.isSourceOperation()) {
657  ProgramOperation& headPO = head.sourceOperation();
658  for (int i = 0; i < headPO.inputMoveCount(); i++) {
659  MoveNode& inputMove = headPO.inputMove(i);
660  if (!inputMove.isPlaced()) {
661  continue;
662  }
663 
667 
668  // same operation. 0 cycle war.
669  // TODO: also this if bundle ordering correct.
670  if (moveNode.isDestinationOperation() &&
671  &moveNode.destinationOperation() ==
672  &headPO && !edge.isBackEdge()) {
673  maxCycle = std::min(maxCycle, inputMove.cycle());
674  } else {
675  // different operation.1 cycle war,to be sure,for now
676  maxCycle = std::min(maxCycle, inputMove.cycle()-1);
677  }
678  }
679 
683  maxCycle = std::min(maxCycle, inputMove.cycle()-1);
684  }
685  }
686  }
687  }
688 
689  return maxCycle;
690 }
691 
692 /**
693  * Returns the moves that are scheduled at the given cycle.
694  *
695  * @param cycle The cycle.
696  * @return Move that are scheduled at the given cycle.
697  */
700 
701  NodeSet moves;
702  for (int i = 0; i < nodeCount(); ++i) {
703  Node& n = node(i);
704  if (n.isPlaced() && n.cycle() == cycle)
705  moves.insert(&n);
706  }
707 
708  return moves;
709 }
710 
711 /**
712  * Returns the MoveNode that defines (writes the value of) the guard
713  * the given move node is predicated with. If there are multiple,
714  * returns the last.
715  *
716  * @param moveNode The move node of which guard defining move to find.
717  * @return The MoveNode that produces the guard value.
718  * If not found, returns NULL
719  */
720 MoveNode*
722  NodeSet guardDefs = guardDefMoves(moveNode);
723  MoveNode* last = NULL;
724  for (NodeSet::iterator i = guardDefs.begin();
725  i != guardDefs.end(); i++) {
726  if (last == NULL || last->cycle() < (*i)->cycle()) {
727  last = *i;
728  }
729  }
730  return last;
731 }
732 
733 /**
734  * Returns all movenodes that define (write the value of) the guard
735  * the given move node is predicated with.
736  *
737  * @param moveNode The move node of which guard defining move to find.
738  * @return The MoveNodes that produces the guard value.
739  * Can be multiple if the writes are predicated or in different BB.
740  * If not found, returns NULL
741  */
744 
746  EdgeSet inputEdges = inEdges(moveNode);
747  for (EdgeSet::iterator i = inputEdges.begin();
748  i != inputEdges.end(); i++) {
749  DataDependenceEdge &edge = **i;
750  if (edge.guardUse() &&
752  guardDefMoves.insert(&tailNode(edge));
753  }
754  }
755  return guardDefMoves;
756 }
757 
758 /**
759  * Returns the MoveNode with highest cycle that reads the given register.
760  *
761  * @param rf The register file.
762  * @param registerIndex Index of the register.
763  * @return The MoveNode, NULL, if not found.
764  */
765 MoveNode*
768  int registerIndex,
769  int lastCycleToTest) const {
770 
771  int lastCycle = -1;
772  MoveNode* lastFound = NULL;
773  for (int i = 0; i < nodeCount(); ++i) {
774  MoveNode& n = node(i);
775 
776  TTAProgram::Terminal& source = n.move().source();
777  if (!n.isPlaced() ||
778  !(source.isImmediateRegister() || source.isGPR()))
779  continue;
780 
781  const TTAMachine::BaseRegisterFile* currentRF = NULL;
782  if (source.isImmediateRegister())
783  currentRF = &source.immediateUnit();
784  else
785  currentRF = &source.registerFile();
786 
787  if (&rf == currentRF &&
788  source.index() == registerIndex &&
789  n.cycle() > lastCycle &&
790  n.cycle() <= lastCycleToTest) {
791  lastCycle = n.cycle();
792  lastFound = &n;
793  }
794  }
795  return lastFound;
796 }
797 
798 /**
799  * Returns the MoveNode with lowest cycle that reads the given register.
800  *
801  * @param rf The register file.
802  * @param registerIndex Index of the register.
803  * @param firstCycleToTest optional argument from which cycle to start
804  * search.
805  * @return The MoveNode, NULL, if not found.
806  */
807 MoveNode*
809  const TTAMachine::BaseRegisterFile& rf,
810  int registerIndex, int firstCycleToTest) const {
811 
812  int firstCycle = INT_MAX;
813  MoveNode* firstFound = NULL;
814  for (int i = 0; i < nodeCount(); ++i) {
815  MoveNode& n = node(i);
816 
817  TTAProgram::Terminal& source = n.move().source();
818  if (!n.isPlaced() ||
819  !(source.isImmediateRegister() || source.isGPR()))
820  continue;
821 
822  const TTAMachine::BaseRegisterFile* currentRF = NULL;
823  if (source.isImmediateRegister())
824  currentRF = &source.immediateUnit();
825  else
826  currentRF = &source.registerFile();
827 
828  if (&rf == currentRF &&
829  source.index() == registerIndex &&
830  n.cycle() < firstCycle &&
831  n.cycle() >= firstCycleToTest) {
832  firstCycle = n.cycle();
833  firstFound = &n;
834  }
835  }
836  return firstFound;
837 }
838 
839 /**
840  * Returns the MoveNode with lowest cycle that writes the given register.
841  *
842  * @param rf The register file.
843  * @param registerIndex Index of the register.
844  * @return The MoveNode, NULL, if not found.
845  */
846 MoveNode*
848  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
849 
850  int firstCycle = INT_MAX;
851  MoveNode* firstFound = NULL;
852  for (int i = 0; i < nodeCount(); ++i) {
853  MoveNode& n = node(i);
854 
855  TTAProgram::Terminal& destination = n.move().destination();
856  if (!n.isPlaced() || !destination.isGPR())
857  continue;
858 
859  const TTAMachine::BaseRegisterFile* currentRF = NULL;
860  currentRF = &destination.registerFile();
861 
862  if (&rf == currentRF &&
863  destination.index() == registerIndex &&
864  n.cycle() < firstCycle) {
865  firstCycle = n.cycle();
866  firstFound = &n;
867  }
868  }
869  return firstFound;
870 }
871 
872 /**
873  * Returns the highest cycle where accesses the given register.
874  * If unscheudled moves accessing the register, returns INT_MAX;
875  * If none found, returns -1.
876  *
877  * @param rf The register file.
878  * @param registerIndex Index of the register.
879  * @return cycle, or INT_MAX if some unscheduled found.
880  */
881 int
883  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
884 
885  int lastCycle = -1;
886  for (int i = 0; i < nodeCount(); ++i) {
887  MoveNode& n = node(i);
888  TTAProgram::Move& move = n.move();
889  const TTAMachine::BaseRegisterFile* currentRF = NULL;
890 
891  // check source
892  TTAProgram::Terminal& source = move.source();
893  bool sourceImmReg = source.isImmediateRegister();
894  bool sourceGPR = source.isGPR();
895 
896  if (sourceImmReg || sourceGPR) {
897 
898  if (sourceImmReg)
899  currentRF = &source.immediateUnit();
900  else
901  currentRF = &source.registerFile();
902 
903  if (&rf == currentRF && source.index() == registerIndex) {
904  if (!n.isPlaced()) {
905  return INT_MAX;
906  }
907  if (n.cycle() > lastCycle) {
908  lastCycle = n.cycle();
909  }
910  }
911  }
912 
913  // check destination
914  TTAProgram::Terminal& destination = move.destination();
915  if (destination.isGPR()) {
916  currentRF = &destination.registerFile();
917 
918  if (&rf == currentRF && destination.index() == registerIndex) {
919  if (!n.isPlaced()) {
920  return INT_MAX;
921  }
922  if (n.cycle() > lastCycle) {
923  lastCycle = n.cycle();
924  }
925 
926  if (move.isUnconditional()) {
927  if (outDegree(n) == 0) {
928  assert(lastCycle == n.cycle());
929  return lastCycle;
930  }
931  }
932  }
933  }
934 
935  // check guard.
936  if (!move.isUnconditional()) {
937  const TTAMachine::Guard& guard = move.guard().guard();
938  const TTAMachine::RegisterGuard* rg =
939  dynamic_cast<const TTAMachine::RegisterGuard*>(&guard);
940  if (rg != NULL) {
941  if (rg->registerFile() == &rf &&
942  rg->registerIndex() == registerIndex) {
943  if (!n.isPlaced()) {
944  return INT_MAX;
945  }
946  if (n.cycle() > lastCycle) {
947  lastCycle = n.cycle();
948  }
949  }
950  }
951  }
952  if (move.isFunctionCall()) {
953  const TTAMachine::RegisterFile* rrf =
954  dynamic_cast<const TTAMachine::RegisterFile*>(&rf);
955  assert(rrf != NULL);
956  TCEString reg =
957  DisassemblyRegister::registerName(*rrf, registerIndex);
958  if (allParamRegs_.find(reg) != allParamRegs_.end()) {
959  if (!n.isPlaced()) {
960  return INT_MAX;
961  }
962  if (n.cycle() + delaySlots_> lastCycle) {
963  lastCycle = n.cycle() + delaySlots_ ;
964  }
965  }
966  }
967  }
968  return lastCycle;
969 }
970 
971 /**
972  * Returns the lowest cycle where accesses the given register.
973  * If unscheudled moves accessing the register, returns -1.
974  * If none found, return INT_MAX
975  *
976  * @param rf The register file.
977  * @param registerIndex Index of the register.
978  * @return cycle, or -1 if some unscheduled found, or INT_MAX if none found.
979  */
980 int
982  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
983 
984  int firstCycle = INT_MAX;
985  for (int i = nodeCount()-1; i >= 0; --i) {
986  MoveNode& n = node(i);
987  TTAProgram::Move& move = n.move();
988  const TTAMachine::BaseRegisterFile* currentRF = NULL;
989 
990  // check source
991  TTAProgram::Terminal& source = move.source();
992  bool sourceImmReg = source.isImmediateRegister();
993  bool sourceGPR = source.isGPR();
994 
995  if (sourceImmReg || sourceGPR) {
996 
997  if (sourceImmReg)
998  currentRF = &source.immediateUnit();
999  else
1000  currentRF = &source.registerFile();
1001 
1002  if (&rf == currentRF && source.index() == registerIndex) {
1003  if (!n.isPlaced()) {
1004  return -1;
1005  }
1006  if (n.cycle() < firstCycle) {
1007  firstCycle = n.cycle();
1008  }
1009  }
1010  }
1011 
1012  // check destination
1013  TTAProgram::Terminal& destination = move.destination();
1014  if (destination.isGPR()) {
1015  currentRF = &destination.registerFile();
1016 
1017  if (&rf == currentRF && destination.index() == registerIndex) {
1018  if (!n.isPlaced()) {
1019  return -1;
1020  }
1021  if (n.cycle() < firstCycle) {
1022  firstCycle = n.cycle();
1023  }
1024  // this is a write of (constant) into reg, and no antideps in?
1025  if (move.isUnconditional()) {
1026  if (inDegree(n) == 0) {
1027  assert(firstCycle == n.cycle());
1028  return firstCycle;
1029  }
1030  }
1031  }
1032  }
1033 
1034  // check guard.
1035  if (!move.isUnconditional()) {
1036  const TTAMachine::Guard& guard = move.guard().guard();
1037  const TTAMachine::RegisterGuard* rg =
1038  dynamic_cast<const TTAMachine::RegisterGuard*>(&guard);
1039  if (rg != NULL) {
1040  if (rg->registerFile() == &rf &&
1041  rg->registerIndex() == registerIndex) {
1042  if (!n.isPlaced()) {
1043  return -1;
1044  }
1045  if (n.cycle() < firstCycle) {
1046  firstCycle = n.cycle();
1047  }
1048  }
1049  }
1050  }
1051  if (move.isFunctionCall()) {
1052  const TTAMachine::RegisterFile* rrf =
1053  dynamic_cast<const TTAMachine::RegisterFile*>(&rf);
1054  assert(rrf != NULL);
1055  TCEString reg =
1056  DisassemblyRegister::registerName(*rrf, registerIndex);
1057  if (allParamRegs_.find(reg) != allParamRegs_.end()) {
1058  if (!n.isPlaced()) {
1059  return -1;
1060  }
1061  if (n.cycle() + delaySlots_ < firstCycle) {
1062  firstCycle = n.cycle() + delaySlots_ ;
1063  }
1064  }
1065  }
1066  }
1067  return firstCycle;
1068 }
1069 
1070 
1071 /**
1072  * Returns the set of MoveNodes which reads given register after
1073  * last unconditional scheduled write to the register.
1074  *
1075  * @param rf The register file.
1076  * @param registerIndex Index of the register.
1077  * @return The set of movenodes.
1078  */
1081  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
1082 
1083  MoveNode* lastKill = lastScheduledRegisterKill(rf, registerIndex);
1084  int killCycle = lastKill == NULL ? -1 : lastKill->cycle();
1085  NodeSet lastReads;
1086 
1087  int nodeCounter = nodeCount();
1088  // first search last kill.
1089  for (int i = 0; i < nodeCounter; ++i) {
1090  MoveNode& n = node(i);
1091 
1092  TTAProgram::Terminal& source = n.move().source();
1093  if (!n.isPlaced() ||
1094  !(source.isImmediateRegister() || source.isGPR()))
1095  continue;
1096 
1097  const TTAMachine::BaseRegisterFile* currentRF = NULL;
1098  if (source.isImmediateRegister())
1099  currentRF = &source.immediateUnit();
1100  else
1101  currentRF = &source.registerFile();
1102 
1103  if (&rf == currentRF &&
1104  source.index() == registerIndex) {
1105  if (n.cycle() > killCycle) {
1106  lastReads.insert(&n);
1107  }
1108  }
1109  }
1110  return lastReads;
1111 }
1112 /**
1113  * Returns the set of MoveNodes which reads given register before
1114  * first unconditional scheduled write to the register.
1115  *
1116  * @param rf The register file.
1117  * @param registerIndex Index of the register.
1118  * @return The set of movenodes.
1119  */
1122  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
1123 
1124  MoveNode* firstKill = firstScheduledRegisterKill(rf, registerIndex);
1125  int killCycle = firstKill == NULL ? -1 : firstKill->cycle();
1126  NodeSet firstReads;
1127 
1128  // first search last kill.
1129  for (int i = 0; i < nodeCount(); ++i) {
1130  MoveNode& n = node(i);
1131 
1132  TTAProgram::Terminal& source = n.move().source();
1133  if (!n.isPlaced() ||
1134  !(source.isImmediateRegister() || source.isGPR()))
1135  continue;
1136 
1137  const TTAMachine::BaseRegisterFile* currentRF = NULL;
1138  if (source.isImmediateRegister())
1139  currentRF = &source.immediateUnit();
1140  else
1141  currentRF = &source.registerFile();
1142 
1143  if (&rf == currentRF &&
1144  source.index() == registerIndex) {
1145  if (n.cycle() < killCycle) {
1146  firstReads.insert(&n);
1147  }
1148  }
1149  }
1150  return firstReads;
1151 }
1152 
1153 
1154 /**
1155  * Returns the set of MoveNodes which reads given register as guard after
1156  * last unconditional scheduled write to the register.
1157  *
1158  * @param rf The register file.
1159  * @param registerIndex Index of the register.
1160  * @return The set of movenodes.
1161  */
1164  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
1165 
1166  MoveNode* lastKill = lastScheduledRegisterKill(rf, registerIndex);
1167  int killCycle = lastKill == NULL ? -1 : lastKill->cycle();
1168  NodeSet lastGuards;
1169 
1170  int nodeCounter = nodeCount();
1171  // first search last kill.
1172  for (int i = 0; i < nodeCounter; ++i) {
1173  MoveNode& n = node(i);
1174  TTAProgram::Move& move = n.move();
1175  if (move.isUnconditional() || !n.isPlaced()) {
1176  continue;
1177  }
1178 
1179  const TTAMachine::Guard* guard = &move.guard().guard();
1180  const TTAMachine::RegisterGuard* rg =
1181  dynamic_cast<const TTAMachine::RegisterGuard*>(guard);
1182  if (rg == NULL) {
1183  continue;
1184  }
1185  const TTAMachine::BaseRegisterFile* currentRF = rg->registerFile();
1186  if (&rf == currentRF &&
1187  rg->registerIndex() == registerIndex) {
1188  if (n.cycle() > killCycle) {
1189  lastGuards.insert(&n);
1190  }
1191  }
1192  }
1193  return lastGuards;
1194 }
1195 
1196 /**
1197  * Returns the set of MoveNodes which writes given register after
1198  * last unconditional scheduled write to the register,
1199  * and the last unconditional write.
1200  *
1201  * @param rf The register file.
1202  * @param registerIndex Index of the register.
1203  * @return The set of movenodes.
1204  */
1207  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
1208 
1209  MoveNode* lastKill = lastScheduledRegisterKill(rf, registerIndex);
1210  int killCycle = lastKill == NULL ? -1 : lastKill->cycle();
1211  NodeSet lastReads;
1212 
1213  int nodeCounter = nodeCount();
1214  // first search last kill.
1215  for (int i = 0; i < nodeCounter; ++i) {
1216  MoveNode& n = node(i);
1217 
1218  TTAProgram::Terminal& dest = n.move().destination();
1219  if (!n.isPlaced() || !dest.isGPR())
1220  continue;
1221 
1222  const TTAMachine::BaseRegisterFile* currentRF = NULL;
1223  currentRF = &dest.registerFile();
1224 
1225  if (&rf == currentRF &&
1226  dest.index() == registerIndex) {
1227  if (n.cycle() >= killCycle) {
1228  lastReads.insert(&n);
1229  }
1230  }
1231  }
1232  return lastReads;
1233 }
1234 
1235 /**
1236  * Returns the set of MoveNodes which writes given register after
1237  * last unconditional scheduled write to the register,
1238  * and the last unconditional write.
1239  *
1240  * @param rf The register file.
1241  * @param registerIndex Index of the register.
1242  * @return The set of movenodes.
1243  */
1246  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
1247 
1248  // TODO: should this be able to be calculated from LR bookkeeping?
1249 
1250  MoveNode* firstKill = firstScheduledRegisterKill(rf, registerIndex);
1251  int killCycle = firstKill == NULL ? INT_MAX : firstKill->cycle();
1252  NodeSet firstWrites;
1253 
1254  int nodeCounter = nodeCount();
1255  // first search last kill.
1256  for (int i = 0; i < nodeCounter; ++i) {
1257  MoveNode& n = node(i);
1258 
1259  TTAProgram::Terminal& dest = n.move().destination();
1260  if (!n.isPlaced() || !dest.isGPR())
1261  continue;
1262 
1263  const TTAMachine::BaseRegisterFile* currentRF = NULL;
1264  currentRF = &dest.registerFile();
1265 
1266  if (&rf == currentRF &&
1267  dest.index() == registerIndex) {
1268  if (n.cycle() <= killCycle) {
1269  firstWrites.insert(&n);
1270  }
1271  }
1272  }
1273  return firstWrites;
1274 }
1275 
1276 
1277 /**
1278  * Returns the MoveNode of unconditional move with highest cycle that writes the given register.
1279  *
1280  * @param rf The register file.
1281  * @param registerIndex Index of the register.
1282  * @return The MoveNode, NULL, if not found.
1283  */
1284 MoveNode*
1286  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
1287 
1288  int lastCycle = -1;
1289  MoveNode* lastFound = NULL;
1290  int nodeCounter = nodeCount();
1291  for (int i = 0; i < nodeCounter; ++i) {
1292  MoveNode& n = node(i);
1293 
1294  TTAProgram::Terminal& dest = n.move().destination();
1295  if (!n.isPlaced() || !dest.isGPR())
1296  continue;
1297 
1298  const TTAMachine::BaseRegisterFile* currentRF = NULL;
1299  currentRF = &dest.registerFile();
1300 
1301  if (&rf == currentRF &&
1302  dest.index() == registerIndex &&
1303  n.cycle() > lastCycle &&
1304  n.move().isUnconditional()) {
1305  lastCycle = n.cycle();
1306  lastFound = &n;
1307  }
1308  }
1309  return lastFound;
1310 }
1311 
1312 /**
1313  * Returns the MoveNode of unconditional move with highest cycle that writes the given register.
1314  *
1315  * @param rf The register file.
1316  * @param registerIndex Index of the register.
1317  * @return The MoveNode, NULL, if not found.
1318  */
1319 MoveNode*
1321  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const {
1322 
1323  int firstCycle = INT_MAX;
1324  MoveNode* firstFound = NULL;
1325  int nodeCounter = nodeCount();
1326  for (int i = 0; i < nodeCounter; ++i) {
1327  MoveNode& n = node(i);
1328 
1329  TTAProgram::Terminal& dest = n.move().destination();
1330  if (!n.isPlaced() || !dest.isGPR())
1331  continue;
1332 
1333  const TTAMachine::BaseRegisterFile* currentRF = NULL;
1334  currentRF = &dest.registerFile();
1335 
1336  if (&rf == currentRF &&
1337  dest.index() == registerIndex &&
1338  n.cycle() < firstCycle &&
1339  n.move().isUnconditional()) {
1340  firstCycle = n.cycle();
1341  firstFound = &n;
1342  }
1343  }
1344  return firstFound;
1345 }
1346 
1347 
1348 /**
1349  * Returns all unscheduled moves.
1350  *
1351  * @param cycle The cycle.
1352  * @return Unscheduled moves.
1353  */
1356 
1357  NodeSet moves;
1358  int nodeCounter = nodeCount();
1359  for (int i = 0; i < nodeCounter; ++i) {
1360  Node& n = node(i);
1361  if (!n.isPlaced())
1362  moves.insert(&n);
1363  }
1364 
1365  return moves;
1366 }
1367 
1368 /**
1369  * Returns all scheduled moves.
1370  *
1371  * @param cycle The cycle.
1372  * @return Scheduled moves.
1373  */
1376 
1377  NodeSet moves;
1378  int nodeCounter = nodeCount();
1379  for (int i = 0; i < nodeCounter; ++i) {
1380  Node& n = node(i);
1381  if (n.isPlaced())
1382  moves.insert(&n);
1383  }
1384 
1385  return moves;
1386 }
1387 
1388 /**
1389  * Checks that the DDG is sane.
1390  *
1391  * Goes through all edges in the DDG and ensures they make sense, for example,
1392  * in case of R_RAW, the head should really read the register written by
1393  * the tail.
1394  *
1395  * @exception In case the graph contains failures. Exception message contains
1396  * the reason.
1397  */
1398 void
1400  for (int i = 0; i < edgeCount(); ++i) {
1401  DataDependenceEdge& e = edge(i);
1402  MoveNode& tail = tailNode(e);
1403  const TTAProgram::Terminal& tailSource = tail.move().source();
1404  const TTAProgram::Terminal& tailDestination = tail.move().destination();
1405 
1406  MoveNode& head = headNode(e);
1407  const TTAProgram::Terminal& headSource = head.move().source();
1408  const TTAProgram::Terminal& headDestination = head.move().destination();
1409 
1410  switch (e.dependenceType()) {
1412  if (tailDestination.isFUPort() && headSource.isFUPort())
1413  break; // operation dependency is marked with DEP_UNKNOWN
1414  throw Exception(
1415  __FILE__, __LINE__, __func__,
1416  ((boost::format(
1417  "DEP_UNKNOWN in edge between %s and %s."))
1418  % tail.toString() % head.toString()).str());
1419  break;
1421  // the normal case
1422  if (tailDestination.equals(headSource))
1423  break;
1424 
1425  // memory RAW
1427  tailDestination.isFUPort() &&
1428  tailDestination.hintOperation().writesMemory() &&
1429  headDestination.isFUPort() &&
1430  headDestination.hintOperation().readsMemory())
1431  break;
1432 
1433  // W:gcu.ra R:ra
1434  if (tailDestination.isFUPort() &&
1435  &tailDestination.functionUnit() ==
1436  tailDestination.functionUnit().machine()->controlUnit() &&
1437  headSource.isFUPort())
1438  break;
1439 
1440  // tail writes a reg the head is guarded with
1441  if (!head.move().isUnconditional() && tailDestination.isGPR() &&
1442  dynamic_cast<const TTAMachine::RegisterGuard*>(
1443  &head.move().guard().guard()) != NULL) {
1444  const TTAMachine::RegisterGuard& g =
1445  dynamic_cast<const TTAMachine::RegisterGuard&>(
1446  head.move().guard().guard());
1447  if (g.registerFile() == &tailDestination.registerFile())
1448  break; // TODO: check also the register index
1449  }
1450 
1451  // return value register on procedure return
1452  if (tailDestination.isGPR() &&
1453  headDestination.isFUPort() &&
1454  head.move().isControlFlowMove())
1455  break;
1456 
1457  writeToDotFile("faulty_raw_ddg.dot");
1458  throw Exception(
1459  __FILE__, __LINE__, __func__,
1460  ((boost::format(
1461  "DEP_RAW in edge between %s and %s."))
1462  % tail.toString() % head.toString()).str());
1463  break;
1465  if (headDestination.equals(tailSource))
1466  break;
1467 
1468  // memory WAR
1470  tailDestination.isFUPort() &&
1471  tailDestination.hintOperation().readsMemory() &&
1472  headDestination.isFUPort() &&
1473  headDestination.hintOperation().writesMemory())
1474  break;
1475 
1476  // memory WAR between memory op and call
1478  tailDestination.isFUPort() &&
1479  tailDestination.hintOperation().readsMemory() &&
1480  headDestination.isFUPort() &&
1481  head.move().isFunctionCall())
1482  break;
1483 
1484  // call parameter register
1485  if (tailDestination.isFUPort() &&
1486  tailSource.isGPR() &&
1487  head.move().isFunctionCall())
1488  break;
1489 
1490  // return value register has WaR to 'call'
1491  // no better heuristics yet as we don't know the register RV is
1492  // mapped to
1493  if (tailSource.isGPR() && head.move().isFunctionCall())
1494  break;
1495 
1496  // a use (probably a store) of RA has a WaR to 'call'
1497  if (tailSource.isFUPort() && head.move().isFunctionCall())
1498  break;
1499 
1500  writeToDotFile("faulty_war_ddg.dot");
1501  throw Exception(
1502  __FILE__, __LINE__, __func__,
1503  ((boost::format(
1504  "DEP_WAR in edge between %s and %s."))
1505  % tail.toString() % head.toString()).str());
1506  break;
1508  if (headDestination.equals(tailDestination))
1509  break;
1510 
1511  // memory WAW - can also point to call?
1513  tailDestination.isFUPort() &&
1514  (tailDestination.hintOperation().writesMemory() &&
1515  ((headDestination.isFUPort() &&
1516  headDestination.hintOperation().writesMemory()) ||
1517  (headDestination.isFUPort() &&
1518  head.move().isFunctionCall()))))
1519  break;
1520 
1521  // memory WAW between memory op and call
1523  tailDestination.isFUPort() &&
1524  tailDestination.hintOperation().writesMemory() &&
1525  headDestination.isFUPort() &&
1526  head.move().isFunctionCall())
1527  break;
1528 
1529  // function parameter registers
1530  if (tailDestination.isGPR() &&
1531  headDestination.isFUPort() &&
1532  head.move().isFunctionCall())
1533  break;
1534 
1535  writeToDotFile("faulty_waw_ddg.dot");
1536  throw Exception(
1537  __FILE__, __LINE__, __func__,
1538  ((boost::format(
1539  "DEP_WAW in edge between %s and %s."))
1540  % tail.toString() % head.toString()).str());
1541  break;
1542  default:
1543  throw Exception(
1544  __FILE__, __LINE__, __func__,
1545  ((boost::format(
1546  "Unknown edge type: %d in edge between %s and %s."))
1547  % e.dependenceType() % tail.toString() % head.toString()).
1548  str());
1549  }
1550  }
1551 }
1552 
1553 /**
1554  * Returns the graph as a string formatted in GraphViz Dot format.
1555  *
1556  * This version is able to order the nodes according to their cycles to
1557  * make the output more readable.
1558  *
1559  * @return Graph represented as a Dot string.
1560  */
1561 TCEString
1563 
1564  // TODO group based on both BB and cycle
1565  std::ostringstream s;
1566  s << "digraph " << name() << " {" << std::endl;
1567 
1569  // print the "time line"
1570  s << "\t{" << std::endl
1571  << "\t\tnode [shape=plaintext];" << std::endl
1572  << "\t\t";
1573  const int smallest = smallestCycle();
1574  const int largest = largestCycle();
1575  for (int c = smallest; c <= largest; ++c) {
1576  s << "\"cycle " << c << "\" -> ";
1577  }
1578  s << "\"cycle " << largest + 1 << "\"; "
1579  << std::endl << "\t}" << std::endl;
1580 
1581  // print the nodes that have cycles
1582  for (int c = smallest; c <= largest; ++c) {
1583  NodeSet moves = movesAtCycle(c);
1584  if (moves.size() > 0) {
1585  s << "\t{ rank = same; \"cycle " << c << "\"; ";
1586  for (NodeSet::iterator i = moves.begin();
1587  i != moves.end(); ++i) {
1588  Node& n = **i;
1589  s << "n" << n.nodeID() << "; ";
1590  }
1591  s << "}" << std::endl;
1592  }
1593  }
1594  }
1595 
1596  // print all the nodes and their properties
1597  for (int i = 0; i < nodeCount(); ++i) {
1598  Node& n = node(i);
1599 
1600  // in PONode mode, print the node for a single move only if
1601  // it doesn't belong to an operation
1603  continue;
1604 
1605  TCEString nodeStr(n.dotString());
1606  if (false && isInCriticalPath(n)) {
1607  // convert critical path node shapes to invtriangle to make
1608  // the path stand out in the graph, this slows down the
1609  // printout probably quite a bit, TODO: optimize by caching
1610  // critical path data
1611  nodeStr.replaceString("shape=box", "shape=invtriangle");
1612  nodeStr.replaceString("shape=ellipse", "shape=invtriangle");
1613  }
1614  s << "\tn" << n.nodeID() << " [" << nodeStr << "]; " << std::endl;
1615  }
1616 
1617  typedef std::set<ProgramOperation*> POSet;
1618  POSet programOps;
1619 
1620  // edges. optimized low-level routines.
1621  typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
1622  EdgeIterPair edges = boost::edges(graph_);
1623  for (EdgeIter i = edges.first; i != edges.second; i++) {
1624  EdgeDescriptor ed = *i;
1625  Edge& e = *graph_[ed];
1626  Node& tail = *graph_[boost::source(ed, graph_)];
1627  Node& head = *graph_[boost::target(ed, graph_)];
1628 
1629  TCEString tailNodeId;
1630  TCEString headNodeId;
1631 
1633  if (tail.isSourceOperation()) {
1634  tailNodeId << "po" << tail.sourceOperation().poId();
1635  programOps.insert(&tail.sourceOperation());
1636  } else {
1637  tailNodeId << "po" << tail.destinationOperation().poId();
1638  programOps.insert(&tail.destinationOperation());
1639  }
1640  } else {
1641  tailNodeId << "n" << tail.nodeID();
1642  }
1643 
1645  if (head.isSourceOperation()) {
1646  headNodeId << "po" << head.sourceOperation().poId();
1647  programOps.insert(&head.sourceOperation());
1648  } else {
1649  headNodeId << "po" << head.destinationOperation().poId();
1650  programOps.insert(&head.destinationOperation());
1651  }
1652  } else {
1653  headNodeId << "n" << head.nodeID();
1654  }
1655 
1656  if (tailNodeId == headNodeId) continue;
1657 
1658  float weight = 1.0f;
1659  s << "\t" << tailNodeId
1660  << " -> " << headNodeId << "[";
1661 
1662  if (e.isFalseDep()) {
1663  weight = 0.3f;
1664  s << "color=\"red\", ";
1665  }
1666 
1667  if (e.isBackEdge()) {
1668  s << "constraint=false,";
1669  weight = 0.1f;
1670  }
1671 
1673  weight = 10.0f;
1674  }
1675 
1677  weight /= 2.0f;
1678  }
1679 
1680  s << "label=\""
1681  << e.toString(tail)
1682  << "\",weight=" << weight << "];" << std::endl;
1683  }
1684 
1685  // implicit operand to trigger edges
1686  for (int i = 0; i < nodeCount() && !dotProgramOperationNodes_; ++i) {
1687  Node& n = node(i);
1688  if (n.isMove() && n.move().isTriggering() &&
1689  n.isDestinationOperation()) {
1691  for (int j = 0; j < dst.inputMoveCount(); ++j) {
1692  if (dst.inputMove(j).nodeID() != n.nodeID()) {
1693  s << "\tn" << dst.inputMove(j).nodeID()
1694  << " -> n" << n.nodeID() << "["
1695  << "label=\"T\", weight=10.0" << "];" << std::endl;
1696  }
1697  }
1698  }
1699  }
1700 
1702  for (POSet::iterator i = programOps.begin();
1703  i != programOps.end(); ++i) {
1704  const ProgramOperation& po = **i;
1705  TCEString label;
1706 
1707  int lineNo = -1;
1708 
1709  for (int i = 0; i < po.inputMoveCount(); ++i) {
1710  label += po.inputMove(i).toString() + "\\n";
1711  if (po.inputMove(i).move().hasSourceLineNumber())
1712  lineNo = po.inputMove(i).move().sourceLineNumber();
1713  }
1714  label += "\\n";
1715  for (int i = 0; i < po.outputMoveCount(); ++i) {
1716  label += po.outputMove(i).toString() + "\\n";
1717  }
1718 
1719  if (lineNo != -1)
1720  label << "src line: " << lineNo << "\\n";
1721 
1722  s << "\tpo" << po.poId() << " [label=\""
1723  << label << "\",shape=box];" << std::endl;
1724  }
1725  }
1726 
1727  s << "}" << std::endl;
1728 
1729  return s.str();
1730 }
1731 
1732 /**
1733  * Sets the "cycle grouping" mode of the Dot printout.
1734  *
1735  * If set, moves are grouped according to their scheduled cycles (if any).
1736  */
1737 void
1739  cycleGrouping_ = flag;
1740 }
1741 
1742 /**
1743  * Writes the graph into an XML file.
1744  *
1745  */
1746 void
1747 DataDependenceGraph::writeToXMLFile(std::string fileName) const {
1748 
1749  XMLSerializer serializer;
1750  ObjectState topOS = ObjectState("dependenceinfo");
1751  ObjectState* labelOS = new ObjectState("label", &topOS);
1752  ObjectState* nodesOS = new ObjectState("nodes", &topOS);
1753  ObjectState* edgesOS = new ObjectState("edges", &topOS);
1754 
1755  // Name of the unit
1756  labelOS->setValue(name());
1757 
1758  // Populate the nodes element
1759  for (int i = 0; i < nodeCount(); ++i) {
1760  ObjectState* nodeOS = new ObjectState("node", nodesOS);
1761  ObjectState* idOS = new ObjectState("id", nodeOS);
1762  ObjectState* labelOS = new ObjectState("label", nodeOS);
1763 
1764  Node& n = node(i);
1765 
1766  idOS->setValue(n.nodeID());
1767  labelOS->setValue(n.toString());
1768 
1769  if (n.isPlaced()) {
1770  ObjectState* cycleOS = new ObjectState("cycle", nodeOS);
1771  ObjectState* busOS = new ObjectState("slot", nodeOS);
1772 
1773  cycleOS->setValue(Conversion::toString(n.cycle()));
1774  busOS->setValue(n.move().bus().name());
1775  }
1776  }
1777 
1778  // Populate the edges element
1779  typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
1780  EdgeIterPair edges = boost::edges(graph_);
1781  for (EdgeIter i = edges.first; i != edges.second; i++) {
1782  Edge& e = *graph_[*i];
1783  Node& tail = *graph_[boost::source(*i, graph_)];
1784  Node& head = *graph_[boost::target(*i, graph_)];
1785  edgesOS->addChild(e.saveState(tail, head));
1786  }
1787 
1788  // Implicit operand to trigger edges
1789  for (int i = 0; i < nodeCount(); ++i) {
1790  Node& n = node(i);
1791  if (n.isPlaced() && n.isMove() && n.move().isTriggering() &&
1792  n.isDestinationOperation()) {
1794  for (int j = 0; j < dst.inputMoveCount(); ++j) {
1795  if (dst.inputMove(j).nodeID() != n.nodeID()) {
1796 
1797  // Create a dummy edge and dump it
1800  edgesOS->addChild(e.saveState(dst.inputMove(j), n));
1801  }
1802  }
1803  }
1804  }
1805 
1806  serializer.setDestinationFile(fileName);
1807  serializer.writeState(&topOS);
1808 }
1809 
1810 /**
1811  * Returns the smallest cycle of a move in the DDG.
1812  *
1813  * Current implementation is quite slow, so don't call in critical places.
1814  *
1815  * @return The smallest cycle of a move.
1816  */
1817 int
1819 
1820  int minCycle = INT_MAX;
1821  for (int i = 0; i < nodeCount(); ++i) {
1822  Node& n = node(i);
1823  if (n.isPlaced())
1824  minCycle = std::min(minCycle, n.cycle());
1825  }
1826 
1827  return minCycle;
1828 }
1829 
1830 /**
1831  * Returns the largest cycle of a move in the DDG.
1832  *
1833  * Current implementation is quite slow, so don't call in critical places.
1834  *
1835  * @return The largest cycle of a move.
1836  */
1837 int
1839 
1840  int maxCycle = 0;
1841  for (int i = 0; i < nodeCount(); ++i) {
1842  Node& n = node(i);
1843  if (n.isPlaced()) {
1844  maxCycle = std::max(maxCycle, n.cycle());
1845  }
1846  }
1847 
1848  return maxCycle;
1849 }
1850 
1851 /**
1852  * Returns the count of nodes in the graph that have been scheduled.
1853  *
1854  * Current implementation is quite slow, so don't call in critical places.
1855  *
1856  * @return The count of scheduled nodes.
1857  */
1858 int
1860 
1861  int scheduledCount = 0;
1862  for (int i = 0; i < nodeCount(); ++i) {
1863  Node& n = node(i);
1864  if (n.isPlaced())
1865  ++scheduledCount;
1866  }
1867 
1868  return scheduledCount;
1869 }
1870 
1871 /**
1872  * Checks if software bypassing is allowed without causing a
1873  * deadlock through some circlar ddg dependence.
1874  *
1875  * @param sourceNode node writing the value which is bypassed
1876  * @param userNode node using the value, source of this node will be updated.
1877  *
1878 */
1879 bool
1881 
1882  // check against to WAR's to each others caused by
1883  // A->B ; B-A trying to be bypassed to same cycle. don't allow this.
1884  // TODO: this does not handle/detect: A -> B ; C -> A; D -> C where
1885  // B -> D is being bypassed from A. creates a loop.
1886 
1887  for (int i = 0; i < outDegree(sourceNode); i++) {
1888  DataDependenceEdge& edge = outEdge(sourceNode,i);
1891  !edge.tailPseudo()) {
1892  MoveNode& target = headNode(edge);
1893  if (!exclusingGuards(userNode, target)) {
1894  if (&target != &userNode && hasPath(target, userNode)) {
1895  return false;
1896  }
1897  }
1898  }
1899  }
1900 
1901  if (!hasEdge(sourceNode, userNode)) {
1902  writeToDotFile("no_edge_on_merge.dot");
1903  throw Exception(
1904  __FILE__,__LINE__,__func__,"No edge between nodes being merged "
1905  + sourceNode.toString() + " " + userNode.toString());
1906  }
1907 
1908  if (!sourceNode.isMove() || !userNode.isMove()) {
1909  throw Exception(
1910  __FILE__,__LINE__,__func__,"Cannot merge entry/exit node!");
1911  }
1912 
1913  return true;
1914 }
1915 
1917  EdgeSet edges = connectingEdges(
1918  sourceNode, userNode);
1919 
1920  for (EdgeSet::iterator i = edges.begin();
1921  i != edges.end(); i++ ) {
1922  DataDependenceEdge* edge = *i;
1924  edge->isBackEdge()) {
1925  return true;
1926  }
1927  }
1928  return false;
1929 }
1930 
1931 
1932 /**
1933  * Removes raw edged between nodes.
1934  *
1935  * Returns the register associated with the raw dependency
1936  */
1938 
1939  TCEString regName;
1940  EdgeSet edges = connectingEdges(sourceNode, userNode);
1941 
1942  for (auto edge: edges) {
1944  regName = edge->data();
1945  removeEdge(*edge, &sourceNode, &userNode);
1946  }
1947  }
1948 
1949  // there must have been a register raw edge between source and user node
1950  if (regName == "") {
1951  std::cerr << "Missing RAW edge between: " << sourceNode.toString()
1952  << " and " << userNode.toString() << " on removeRawEdges."
1953  << " Wrote missing_raw.dot" << std::endl;
1954  writeToDotFile("missing_raw.dot");
1955  assert(false);
1956  }
1957 
1958  return regName;
1959 }
1960 
1961 bool
1963  MoveNode& sourceNode, MoveNode& userNode, bool force) {
1964 
1965  if (!force && !mergeAndKeepAllowed(sourceNode, userNode)) {
1966  return false;
1967  }
1968 
1969  // update the move
1970  sourceNode.move().setDestination(userNode.move().destination().copy());
1971 
1972  bool userIsRegToItselfCopy = false;
1973  // If source is an operation, set programOperation
1974  if (userNode.isDestinationOperation()) {
1975  // TODO: operand sharing, multiple users?
1976  ProgramOperationPtr dstOp = userNode.destinationOperationPtr();
1977  dstOp->addInputNode(sourceNode);
1978  sourceNode.addDestinationOperationPtr(dstOp);
1979  // TODO: remove the source node operand fromt he operatioN!
1980 
1981  // set fu annotations
1982  for (int j = 0; j < userNode.move().annotationCount(); j++) {
1983  TTAProgram::ProgramAnnotation anno = userNode.move().annotation(j);
1985  sourceNode.move().addAnnotation(
1988  }
1990  sourceNode.move().addAnnotation(
1993  }
1994  }
1995  } else {
1996  // bypassing from stupid reg-to-itself needs extra handling.
1997  if (userNode.move().source().equals(
1998  userNode.move().destination())) {
1999  userIsRegToItselfCopy = true;
2000  }
2001  }
2002 
2003  bool loopBypass = isLoopBypass(sourceNode, userNode);
2004 
2005  // remove RAW deps between source and user.
2006  TCEString regName = removeRAWEdges(sourceNode, userNode);
2007 
2008 
2009  for (int i = 0; i < rootGraphOutDegree(userNode); i++) {
2010  DataDependenceEdge& edge = rootGraphOutEdge(userNode,i);
2011 
2012  // skip antidependencies due bypassed register.. these are no more
2014  edge.data() == regName) {
2017  continue;
2018  }
2019  }
2020 
2021  // copy other edges.
2022  MoveNode& dst = rootGraph()->headNode(edge);
2023  DataDependenceEdge* newEdge = new DataDependenceEdge(edge, loopBypass);
2024 
2025  // it the edge is a loop edge, put it only in root/parent graph.
2026  if (parentGraph_ != NULL) {
2027  static_cast<DataDependenceGraph*>(rootGraph())->
2028  connectNodes(sourceNode, dst, *newEdge,
2029  (edge.isBackEdge()?this:NULL));
2030  } else {
2031  connectNodes(sourceNode, dst, *newEdge);
2032  }
2033  }
2034 
2035  // copy antideps over these two nodes
2036  copyDepsOver(sourceNode, userNode, true, false);
2037 
2038  // fix WAR antidependencies to WaW
2039  for (int i = 0; i < inDegree(sourceNode); i++) {
2040  DataDependenceEdge& edge = inEdge(sourceNode,i);
2041 
2042  // create new WaW in place of old WaR
2045  edge.data() == regName) {
2046 
2047  // if stupid reg to itself copy, keep to in edges..
2048  if (!userIsRegToItselfCopy) {
2049  // and remove the old WaR
2050  removeEdge(edge, NULL, &sourceNode);
2051  i--; // don't skip one edge here!
2052  }
2053  }
2056  edge.data() == regName) {
2057  removeEdge(edge, NULL, &sourceNode);
2058  i--; // don't skip one edge here!
2059  }
2060  }
2061 
2062  for (int i = 0; i < rootGraphInDegree(userNode); i++) {
2063  DataDependenceEdge& e = rootGraphInEdge(userNode,i);
2064 
2065  // do not copy guard use edges - the user already ahs them.
2066  // copying them leads to exponential increase in guard ege counts.
2068  continue;
2069  }
2070  if (&rootGraph()->tailNode(e) != &sourceNode) {
2071  rootGraph()->copyInEdge(sourceNode, e);
2072  }
2073  }
2074 
2075  return true;
2076 }
2077 
2078 bool
2080  MoveNode& sourceNode, MoveNode& userNode, bool force) {
2081 
2082  if (!force && !mergeAndKeepAllowed(sourceNode, userNode)) {
2083  return false;
2084  }
2085 
2086 // writeToDotFile("before_merge.dot");
2087 
2088  bool loopBypass = isLoopBypass(sourceNode, userNode);
2089 
2090  // Cannot bypass over multiple loop iterations. even with force flag.
2091  if (loopBypass) {
2092  for (int i = 0; i < inDegree(sourceNode); i++) {
2093  DataDependenceEdge& edge = inEdge(sourceNode,i);
2094  if (!edge.isFalseDep() && edge.isBackEdge()) {
2095  return false;
2096  }
2097  }
2098  }
2099 
2100  // update the move
2101  userNode.move().setSource(sourceNode.move().source().copy());
2102 
2103  bool sourceIsRegToItselfCopy = false;
2104  // If source is an operation, set programOperation
2105  if (sourceNode.isSourceOperation()) {
2106  ProgramOperationPtr srcOp = sourceNode.sourceOperationPtr();
2107  srcOp->addOutputNode(userNode);
2108  userNode.setSourceOperationPtr(srcOp);
2109 
2110  // set fu annotations
2111  for (int j = 0; j < sourceNode.move().annotationCount(); j++) {
2112  TTAProgram::ProgramAnnotation anno = sourceNode.move().annotation(j);
2114  userNode.move().addAnnotation(
2117  }
2119  userNode.move().addAnnotation(
2122  }
2124  userNode.move().addAnnotation(
2127  }
2128  }
2129  } else {
2130  // bypassing from stupid reg-to-itself needs extra handling.
2131  if (sourceNode.move().source().equals(
2132  sourceNode.move().destination())) {
2133  sourceIsRegToItselfCopy = true;
2134  }
2135  }
2136 
2137  // remove RAW deps between source and user.
2138  TCEString regName = removeRAWEdges(sourceNode, userNode);
2139 
2140 
2141  // if we are bypassign from a register-to-register copy, we'll have to
2142  // copy incoming raw edges also in rootgraph level to preserve inter-bb
2143  // -dependencies.
2144  for (int i = 0; i < rootGraphInDegree(sourceNode); i++) {
2145  DataDependenceEdge& edge = rootGraphInEdge(sourceNode,i);
2146 
2147  // skip antidependencies due bypassed register.. these are no more
2149  edge.data() == regName) {
2152  continue;
2153  }
2154  }
2155 
2156  // do not copy guard use edges - the user already ahs them.
2157  // copying them leads to exponential increase in guard ege counts.
2158  if (edge.guardUse()) {
2159  continue;
2160  }
2161 
2162  // copy other edges.
2163  MoveNode& source = rootGraph()->tailNode(edge);
2164  DataDependenceEdge* newEdge = new DataDependenceEdge(edge, loopBypass);
2165  rootGraph()->connectNodes(source, userNode, *newEdge);
2166  }
2167 
2168  if (sourceNode.isSourceVariable() || sourceNode.isSourceRA()) {
2169  // if bypassing reg-to-reg this copy anti edges resulting from the
2170  // read of the other register.
2171  for (int i = 0; i < rootGraphOutDegree(sourceNode); i++) {
2172  DataDependenceEdge& edge = rootGraphOutEdge(sourceNode,i);
2176  !edge.tailPseudo()) {
2177 
2178  MoveNode& target = rootGraph()->headNode(edge);
2179 
2180  if (!(static_cast<DataDependenceGraph*>(rootGraph()))
2181  ->exclusingGuards(userNode, target) &&
2182  &userNode != &target) {
2183  DataDependenceEdge* newEdge = new DataDependenceEdge(edge, loopBypass);
2184  // TODO: loop here!
2185  rootGraph()->connectNodes(userNode, target, *newEdge);
2186  }
2187  }
2188  }
2189  }
2190 
2191  // fix WAR antidependencies to WaW
2192  for (int i = 0; i < rootGraphOutDegree(userNode); i++) {
2193  DataDependenceEdge& edge = rootGraphOutEdge(userNode,i);
2194 
2195  // create new WaW in place of old WaR
2198  edge.data() == regName) {
2199 
2200  // if stupid reg to itself copy, keep to in edges..
2201  if (!sourceIsRegToItselfCopy) {
2202  // and remove the old WaR
2203  (static_cast<DataDependenceGraph*>(rootGraph()))->
2204  removeEdge(edge, &userNode, NULL);
2205  i--; // don't skip one edge here!
2206  }
2207  }
2208  }
2209  return true;
2210 }
2211 
2212 void
2214  for (int i = 0; i < outDegree(mergedNode); i++) {
2215  DataDependenceEdge& edge = outEdge(mergedNode,i);
2218  edge.data() == reg) {
2219  return;
2220  }
2221  }
2222  DataDependenceEdge* newEdge =
2225  reg, false, false, false, false, false);
2226  connectNodes(mergedNode, sourceNode, *newEdge);
2227 }
2228 
2229 
2230 /**
2231  * Reverses work done by mergeAndKeep routine
2232  *
2233  * changes node to read it's data from register and returns the original
2234  * edges.
2235  *
2236  * @param sourceNode node which writes to the register mergedNode should read.
2237  * @param mergedNode node being changed
2238  */
2239 void
2240 DataDependenceGraph::unMergeUser(MoveNode &sourceNode, MoveNode& mergedNode, bool loopBypass) {
2241 
2242 
2243  // name of the bypass reg.
2244  TTAProgram::Terminal& dest = sourceNode.move().destination();
2245  assert(dest.isGPR());
2247 
2248  // if this is not rootgraph, do it there. allows this to work even if
2249  // source node being deleted from this this sub-ddg.
2250  if (rootGraph() != this) {
2251  static_cast<DataDependenceGraph*>(rootGraph())->
2252  unMergeUser(sourceNode, mergedNode, loopBypass);
2253  if (loopBypass) {
2254  fixAntidepsAfterLoopUnmergeUser(sourceNode, mergedNode, regName);
2255  }
2256  return;
2257  }
2258 
2259  // unset programoperation from bypassed
2260  if (mergedNode.isSourceOperation()) {
2261  ProgramOperation& srcOp = mergedNode.sourceOperation();
2262  srcOp.removeOutputNode(mergedNode);
2263  mergedNode.unsetSourceOperation();
2264 
2265  // unset fu annotations
2269  }
2270 
2271  // All incoming RAW and operation dependencies were created by
2272  // the bypassing, originally there was just one RAW edge which was removed.
2273  // so remove the incoming edges merge routine copied to here.
2274  // these can be operation edges or ordinary register RaWs.
2275  // these should only go to source node.
2276  for (int i = 0; i < inDegree(mergedNode); i++) {
2277  DataDependenceEdge& edge = inEdge(mergedNode,i);
2278  // removes operation edges and
2282  !edge.headPseudo() && !edge.guardUse())) {
2283  removeEdge(edge, NULL, &mergedNode);
2284  i--; // do not skip next edge which now has same index
2285  }
2286  }
2287 
2288  // do the actual unmerge by returning source to original register.
2289  mergedNode.move().setSource(sourceNode.move().destination().copy());
2290 
2291  bool nodeRegToItselfCopy = false;
2292  if (mergedNode.move().source().equals(mergedNode.move().destination())) {
2293  nodeRegToItselfCopy = true;
2294  }
2295 
2296  // create register edge between nodes.
2297  // this was removed by the merge.
2300  DataDependenceEdge::DEP_RAW, regName,
2301  false, false, false, false, loopBypass);
2302  connectNodes(sourceNode, mergedNode, *dde);
2303 
2304  // remove war antidependence edges that should
2305  // come from source. these should only come from the
2306  if (sourceNode.isSourceVariable()) {
2307  for( int i = 0; i < outDegree(mergedNode); i++) {
2308  DataDependenceEdge& edge = outEdge(mergedNode,i);
2311  edge.data() != regName && !edge.tailPseudo() &&
2312  !edge.guardUse()) {
2313  removeEdge(edge, &mergedNode, NULL);
2314  i--; // do not skip next edge which now has same index
2315  }
2316  }
2317  }
2318 
2319  // All all outgoing WAR's to merged node. The war's go to
2320  // all same places where WAW's fo from source node.
2321  for (int i = 0; i < outDegree(sourceNode); i++) {
2322  DataDependenceEdge& edge = outEdge(sourceNode,i);
2325  edge.data() == regName) {
2326  MoveNode& dest = headNode(edge);
2327  // skip nodes with exclusive guard.
2328  if (!exclusingGuards(dest, mergedNode)) {
2329  DataDependenceEdge* newEdge = new DataDependenceEdge(
2331  DataDependenceEdge::DEP_WAR, regName, false, false,
2332  false, edge.headPseudo(), edge.loopDepth() - loopBypass +
2333  nodeRegToItselfCopy);
2334  connectNodes(mergedNode, dest, *newEdge);
2335  }
2336  }
2337  }
2338 }
2339 
2340 
2341 /**
2342  * Checks whether a result is used later or if the result move can be
2343  * dropped.
2344  *
2345  * @param resultNode node being checked for nonused results.
2346  */
2347 bool
2349  return resultUsed(resultNode, NULL);
2350 }
2351 
2352 /**
2353  * Checks whether a result is used later or if the result move can be
2354  * dropped.
2355  *
2356  * @param resultNode node being checked for nonused results.
2357  * @param regCopy Register copy to be removed that might use the result
2358  */
2359 bool
2361  //naming of this variabl si reverse logic, ok if not used
2362  bool killingWrite = true;
2363  if (!isRootGraphProcedureDDG()) {
2364  killingWrite = false;
2365  }
2366  bool hasRAW = false;
2367  bool hasOtherEdge = false;
2368 
2369  EdgeSet edges = rootGraphOutEdges(resultNode);
2370  EdgeSet::iterator edgeIter = edges.begin();
2371  while (edgeIter != edges.end()) {
2372 
2373  DataDependenceEdge& edge = *(*edgeIter);
2374  MoveNode& head =
2375  (static_cast<const DataDependenceGraph*>
2376  (rootGraph()))->headNode(edge);
2377  if (regCopy != NULL && &head == regCopy) {
2378  edgeIter++;
2379  continue;
2380  }
2381 
2382  // don't case about operation edges.
2384  edgeIter++;
2385  continue;
2386  }
2387 
2390  // result is still going to be used
2391  hasRAW = true;
2392  break;
2393  }
2394 
2395  if (killingWrite == false) {
2396  // TODO: does this break if the waw dest unconditional?
2398  !edge.headPseudo()) {
2399  if (head.isMove() && head.move().isUnconditional()) {
2400  killingWrite = true;
2401  }
2402  }
2403  }
2404 
2405  } else {
2406  // there are some other outgoing edges
2407  hasOtherEdge = true;
2408  }
2409  edgeIter++;
2410  }
2411  return (!killingWrite || hasRAW || hasOtherEdge );
2412 }
2413 
2414 
2415 /**
2416  * Copies dependencies over the node, like when the node is being deleted.
2417  *
2418  * Converts WaR + WaW to WaR and WaW + WaW to WaW.
2419  * @param node node whose in- and outgoing antideps are being combined/copied.
2420  */
2422 DataDependenceGraph::copyDepsOver(MoveNode& node, bool anti, bool raw) {
2423 
2424  EdgeSet createdEdges;
2425 
2427 
2428  EdgeSet iEdges = inEdges(node);
2429  EdgeSet oEdges = outEdges(node);
2430 
2431  // Loop thru all outedges.
2432  for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
2433  DataDependenceEdge& oEdge = **i;
2434 
2435  // Care about WaW edges. (WaW+Waw -> Waw, WaR+WaW->War)
2436  // Also raw edges (raw+raw -> raw)
2438  || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
2439  (((oEdge.dependenceType() == DataDependenceEdge::DEP_WAW && anti)||
2440  (oEdge.dependenceType() == DataDependenceEdge::DEP_RAW && raw)))){
2441 
2442  // Then loop all incoming edges.
2443  for (EdgeSet::iterator j = iEdges.begin();
2444  j != iEdges.end(); j++) {
2445  DataDependenceEdge& iEdge = **j;
2446 
2447  // if WAW and same register, copy edge
2448  if (iEdge.dependenceType() == oEdge.dependenceType() &&
2451  iEdge.data() == oEdge.data()) {
2452 
2453  MoveNode& tail = tailNode(iEdge,nd);
2454  MoveNode& head = headNode(oEdge,nd);
2455 
2456  if (!exclusingGuards(tail, head) ||
2457  (oEdge.dependenceType() ==
2459  oEdge.guardUse())) {
2460  // create new edge
2461  // same other properties but sum loop depth
2463  new DataDependenceEdge(
2464  iEdge.edgeReason(),
2465  iEdge.dependenceType(),
2466  iEdge.data(),
2467  iEdge.guardUse(),
2468  false,
2469  iEdge.tailPseudo(),
2470  oEdge.headPseudo(),
2471  iEdge.loopDepth() + oEdge.loopDepth());
2472 
2473  if (connectOrDeleteEdge(tail, head, edge)) {
2474  createdEdges.insert(edge);
2475  }
2476  }
2477  }
2478 
2479  // if WAR and same register, and oedge was waw, copy edge.
2484  iEdge.data() == oEdge.data()) {
2485 
2486  MoveNode& tail = tailNode(iEdge,nd);
2487  MoveNode& head = headNode(oEdge,nd);
2488 
2489  if (!exclusingGuards(tail, head) || iEdge.guardUse()) {
2490  // create new edge
2491  // same other properties but sum loop depth
2493  new DataDependenceEdge(
2494  iEdge.edgeReason(),
2495  iEdge.dependenceType(),
2496  iEdge.data(),
2497  iEdge.guardUse(),
2498  false,
2499  iEdge.tailPseudo(),
2500  oEdge.headPseudo(),
2501  iEdge.loopDepth() + oEdge.loopDepth());
2502 
2503  if (connectOrDeleteEdge(tail, head, edge)) {
2504  createdEdges.insert(edge);
2505  }
2506  }
2507  }
2508  }
2509  }
2510  }
2511  return createdEdges;
2512 }
2513 
2514 void
2516  MoveNode& node1, MoveNode& node2, bool anti, bool raw) {
2517 
2520 
2521  EdgeSet iEdges1 = inEdges(node1);
2522  EdgeSet oEdges1 = outEdges(node1);
2523  EdgeSet iEdges2 = inEdges(node2);
2524  EdgeSet oEdges2 = outEdges(node2);
2525 
2526  // Loop through all outedges of last one
2527  for (EdgeSet::iterator i = oEdges2.begin(); i != oEdges2.end(); i++) {
2528  DataDependenceEdge& oEdge = **i;
2529 
2530  // only care about register edges
2532  || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA)) {
2533  continue;
2534  }
2535 
2536  // are we copying this type edges?
2537  if (!(((oEdge.dependenceType() == DataDependenceEdge::DEP_WAW||
2538  oEdge.dependenceType() == DataDependenceEdge::DEP_WAR) && anti) ||
2539  (oEdge.dependenceType() == DataDependenceEdge::DEP_RAW && raw))) {
2540  continue;
2541  }
2542 
2543  MoveNode& head = headNode(oEdge, nd2);
2544 
2545  if (oEdge.dependenceType() == DataDependenceEdge::DEP_RAW && raw) {
2546  // Then loop all incoming edges for raw deps
2547  for (EdgeSet::iterator j = iEdges1.begin();
2548  j != iEdges1.end(); j++) {
2549  DataDependenceEdge& iEdge = **j;
2550 
2551  // RAW going over node.
2552  if (iEdge.dependenceType() == oEdge.dependenceType() &&
2556  iEdge.data() == oEdge.data()) {
2557 
2558  MoveNode& tail = tailNode(iEdge, nd1);
2559 
2560  if (!exclusingGuards(tail, head) ||
2561  (oEdge.dependenceType() == oEdge.guardUse())) {
2562 
2563  // create new edge
2564  // same other properties but sum loop depth
2566  new DataDependenceEdge(
2567  iEdge.edgeReason(),
2568  iEdge.dependenceType(),
2569  iEdge.data(),
2570  iEdge.guardUse() || oEdge.guardUse(),
2571  false,
2572  iEdge.tailPseudo(),
2573  oEdge.headPseudo(),
2574  iEdge.loopDepth() + oEdge.loopDepth());
2575 
2576  connectOrDeleteEdge(tail, head, edge);
2577  }
2578  }
2579  }
2580  }
2581 
2582  if (!anti) {
2583  continue;
2584  }
2585 
2587  // Then loop all incoming edges for waw deps
2588  for (EdgeSet::iterator j = iEdges2.begin();
2589  j != iEdges2.end(); j++) {
2590  DataDependenceEdge& iEdge = **j;
2591 
2592  // WAW going over node.
2593  if (iEdge.dependenceType() == oEdge.dependenceType() &&
2597  iEdge.data() == oEdge.data()) {
2598 
2599  MoveNode& tail = tailNode(iEdge);
2600 
2601  if (!exclusingGuards(tail, head) && &tail != &node1) {
2602 
2603  // create new edge
2604  // same other properties but sum loop depth
2606  new DataDependenceEdge(
2607  iEdge.edgeReason(),
2608  iEdge.dependenceType(),
2609  iEdge.data(),
2610  iEdge.guardUse(),
2611  false,
2612  iEdge.tailPseudo(),
2613  oEdge.headPseudo(),
2614  iEdge.loopDepth() + oEdge.loopDepth());
2615 
2616  connectOrDeleteEdge(tail, head, edge);
2617  }
2618  }
2619 
2620  // if WAR and same register, and oedge was waw, copy edge.
2625  iEdge.data() == oEdge.data()) {
2626 
2627  MoveNode& tail = tailNode(iEdge,nd2);
2628 
2629  if (!exclusingGuards(tail, head)) {
2630  // create new edge
2631  // same other properties but sum loop depth
2633  new DataDependenceEdge(
2634  iEdge.edgeReason(),
2635  iEdge.dependenceType(),
2636  iEdge.data(),
2637  iEdge.guardUse(),
2638  false,
2639  iEdge.tailPseudo(),
2640  oEdge.headPseudo(),
2641  iEdge.loopDepth() + oEdge.loopDepth());
2642 
2643  if (&tail == &head) {
2644  std::cerr << "copydeps over copying edge same node(1)!" << tail.toString() << " edge: " << edge->toString()
2645  << std::endl;
2646  }
2647 
2648  connectOrDeleteEdge(tail, head, edge);
2649  }
2650  }
2651  }
2652  }
2653 
2654  // last one reads interesting register
2656  for (EdgeSet::iterator j = iEdges1.begin();
2657  j != iEdges1.end(); j++) {
2658  DataDependenceEdge& iEdge = **j;
2659  if ((iEdge.dependenceType() == DataDependenceEdge::DEP_WAR ||
2663  iEdge.data() == oEdge.data()) {
2664  MoveNode& tail = tailNode(iEdge,nd2);
2665 
2666  if (!exclusingGuards(tail, head)) {
2667  // create new edge
2668  // same other properties but sum loop depth
2670  new DataDependenceEdge(
2671  iEdge.edgeReason(),
2672  iEdge.dependenceType(),
2673  iEdge.data(),
2674  iEdge.guardUse(),
2675  false,
2676  iEdge.tailPseudo(),
2677  oEdge.headPseudo(),
2678  iEdge.loopDepth() + oEdge.loopDepth());
2679 
2680  if (&tail == &head) {
2681  std::cerr << "copydeps over copying edge same node(2)!" << tail.toString() << " edge: " << edge->toString()
2682  << std::endl;
2683  }
2684  connectOrDeleteEdge(tail, head, edge);
2685  }
2686  }
2687  }
2688  }
2689  }
2690 
2691  if (!anti) {
2692  return;
2693  }
2694 
2695  // copy WARs over.
2696  for (EdgeSet::iterator i = oEdges1.begin(); i != oEdges1.end(); i++) {
2697  DataDependenceEdge& oEdge = **i;
2698 
2699  // only care about register edges
2701  || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA)) {
2702  continue;
2703  }
2704 
2706 
2707  MoveNode& head = headNode(oEdge,nd1);
2708  if (&head == &node2) {
2709  continue;
2710  }
2711 
2712  // Then loop all incoming edges for waw deps
2713  for (EdgeSet::iterator j = iEdges2.begin();
2714  j != iEdges2.end(); j++) {
2715  DataDependenceEdge& iEdge = **j;
2716 
2717  // WAW going over node.
2721  iEdge.data() == oEdge.data()) {
2722 
2723  MoveNode& tail = tailNode(iEdge,nd2);
2724  if (!exclusingGuards(tail, head) && &tail != &node1) {
2725  // create new edge
2726  // same other properties but sum loop depth
2728  new DataDependenceEdge(
2729  iEdge.edgeReason(),
2730  iEdge.dependenceType(),
2731  iEdge.data(),
2732  iEdge.guardUse(),
2733  false,
2734  iEdge.tailPseudo(),
2735  oEdge.headPseudo(),
2736  iEdge.loopDepth() + oEdge.loopDepth());
2737 
2738  connectOrDeleteEdge(tail, head, edge);
2739  }
2740  }
2741  }
2742  }
2744  MoveNode& head = headNode(oEdge,nd1);
2745  if (&head == &node2) {
2746  continue;
2747  }
2748 
2749  for (EdgeSet::iterator j = iEdges1.begin();
2750  j != iEdges1.end(); j++) {
2751  DataDependenceEdge& iEdge = **j;
2752  if ((iEdge.dependenceType() == DataDependenceEdge::DEP_WAR ||
2756  iEdge.data() == oEdge.data()) {
2757  MoveNode& tail = tailNode(iEdge,nd2);
2758 
2759  if (!exclusingGuards(tail, head)) {
2760  // create new edge
2761  // same other properties but sum loop depth
2763  new DataDependenceEdge(
2764  iEdge.edgeReason(),
2765  iEdge.dependenceType(),
2766  iEdge.data(),
2767  iEdge.guardUse(),
2768  false,
2769  iEdge.tailPseudo(),
2770  oEdge.headPseudo(),
2771  iEdge.loopDepth() + oEdge.loopDepth());
2772 
2773  connectOrDeleteEdge(tail, head, edge);
2774  }
2775  }
2776  }
2777  }
2778  }
2779 }
2780 
2781 void
2783  MoveNode& node1, MoveNode& node2, MoveNode& destination) {
2784 
2787 
2788  moveOutEdges(node2, destination);
2789  moveInEdges(node1, destination);
2790 
2791  EdgeSet oEdges1 = outEdges(node1);
2792  EdgeSet iEdges2 = inEdges(node2);
2793 
2794  // copy WARs over.
2795  for (EdgeSet::iterator i = oEdges1.begin(); i != oEdges1.end(); i++) {
2796  DataDependenceEdge& oEdge = **i;
2797 
2799  || oEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
2801 
2802  MoveNode& head = headNode(oEdge,nd1);
2803  if (&head == &node2) {
2804  continue;
2805  }
2806  moveOutEdge(node1, destination, oEdge);
2807  }
2808  }
2809 
2810  for (EdgeSet::iterator i = iEdges2.begin(); i != iEdges2.end(); i++) {
2811  DataDependenceEdge& iEdge = **i;
2812 
2814  || iEdge.edgeReason() == DataDependenceEdge::EDGE_RA) &&
2817 
2818  MoveNode& tail = tailNode(iEdge,nd2);
2819  if (&tail == &node1) {
2820  continue;
2821  }
2822  moveInEdge(node2, destination, iEdge);
2823  }
2824  }
2825 }
2826 
2827 
2828 
2829 
2830 
2831 /**
2832  * Removes MoveNode from graph and ProgramOperations.
2833  *
2834  * Does not delete the movenode.
2835  *
2836  * This does NOT update overgoing antideps - consider calling
2837  * copyAntidepsOver(node);
2838  * before calling this.
2839  *
2840  * @param node MoveNode being removed.
2841  */
2842 void
2844  // remove move -> movenode mapping.
2845  if (node.isMove()) {
2846  TTAProgram::Move* move = &node.move();
2847  auto i = nodesOfMoves_.find(move);
2848  if (i != nodesOfMoves_.end()) {
2849  nodesOfMoves_.erase(i);
2850  }
2851  }
2852 
2853  // remove node from program operations
2854  if (node.isMove()) {
2855  if (node.isSourceOperation()) {
2857  srcOp.removeOutputNode(node);
2859  }
2860 
2861  if (node.isDestinationOperation()) {
2862  for (int i = node.destinationOperationCount() - 1; i >= 0; i--) {
2864  dstOp.removeInputNode(node);
2865  }
2867  }
2868  }
2869 
2870 // copyAntidepsOver(node);
2871 
2872  // remove node from graph
2874 }
2875 
2876 /**
2877  * Removes a MoveNode from a graph and deletes it.
2878  *
2879  * @param node MoveNode being deleted.
2880  */
2881 void
2883  removeNode(node);
2884  delete &node;
2885 }
2886 
2887 /**
2888  * Calculates a weight value for edges, to be used for
2889  * path weight calculation for selector
2890  *
2891  * Current implementation quite simple to have something better than
2892  * fixed weight without having to analyze the machine.
2893  * 3 equals about one cycle.
2894  *
2895  * In order to use a version that computes the weight strictly using only
2896  * the operation latencies, thus gives the minimum achievable schedule
2897  * length given enough resources (with operation latencies as in the
2898  * machine), call setEdgeWeightHeuristics(EWH_REAL) before calling this.
2899  * To get back to the default one, call setEdgeWeightHeuristics(EWH_DEFAULT).
2900  *
2901  * @todo EWH_HEURISTIC is incomplete. It should take in account the number
2902  * of resources in the current target machine and not assume a "generic
2903  * machine".
2904  *
2905  * @param e edge whose weight is being measured
2906  * @param n head node of the edge.
2907  * @return weigth of the edge.
2908  */
2909 int
2911  DataDependenceEdge& e, const MoveNode& n) const {
2912 
2913  if (e.weight() != -1) {
2914  return e.weight();
2915  }
2916 
2918 
2919  if (e.headPseudo()) {
2920  // pseudo deps do not really limit the scheduling.
2921  e.setWeight(0);
2922  return 0;
2923  }
2924 
2925  switch (e.edgeReason()) {
2927  int ew = getOperationLatency(e.data()) * 3;
2928  e.setWeight(ew);
2929  return ew;
2930  }
2932 
2934  // the number 9 seems to work well on most benchmarks.
2935  // big weight for these makes stores to be scheduled earlier,
2936  // which both helps register pressure and helps stores to
2937  // come earlier, as memory is often worse bottleneck than
2938  // registers or calculation.
2939  e.setWeight(9);
2940  return 9;
2941  }
2942  // for memory WaR's and WaW's this seem to work quite well,
2943  // forces memory ops to be scheduled before other ops.
2944  e.setWeight(5);
2945  return 5;
2946  }
2947 
2949  switch (e.dependenceType()) {
2950  // TODO: some connectivity heuristics
2952  // push guards a bit earlier.
2953  int latency = 0;
2954 
2955  if (e.guardUse()) {
2956  int glat = n.guardLatency();
2957  // jump guard?
2958 
2959  // for predicated control flow ops the edge weight is
2960  // guard latency + delay slots, as the predicated cflow
2961  // ins has to be scehduled delay slots cycles before end.
2962  if (n.isMove() && n.move().isControlFlowMove()) {
2963  int ew = std::max(1, 3*(glat + delaySlots_));
2964  e.setWeight(ew);
2965  return ew;
2966  }
2967  // some other predicated operation
2968  int ew = std::max(1, 3 * glat);
2969  e.setWeight(ew);
2970  return ew;
2971  } else {
2972  // jump address of indirect branch
2973  // indirect control flow ops the delay slots is added
2974  // to the edgeweight, as the indirect control flow ins
2975  // has to be scehduled delay slots cycles before end.
2976  if (n.isMove() && n.move().isControlFlowMove()) {
2977  latency += 3*delaySlots_;
2978  }
2979  }
2980  // rrcost is heurictic on how often we usually can bypass,
2981  // and how often we have to add extra regcopy.
2982  // it's anaylyzed from the machine.
2983  int ew = latency + rrCost_;
2984  e.setWeight(ew);
2985  return ew;
2986  }
2988  e.setWeight(1);
2989  return 1; // can be scheduled to same cycle. but put 1 still.
2990  }
2992  // 3 means 1 cycle. Keeps the order, but no extra delay.
2993  e.setWeight(3);
2994  return 3;
2995  }
2996  default: {
2997  // 3 means 1 cycle. Keeps the order, but no extra delay.
2998  e.setWeight(3);
2999  return 3;
3000  }
3001  }
3002  }
3004  if (n.isMove() && n.move().isJump()) {
3005  int ew = delaySlots_ != 0 ?
3006  (delaySlots_*3)+rrCost_ :
3007  3;
3008  e.setWeight(ew);
3009  return ew;
3010  } else {
3011  e.setWeight(rrCost_);
3012  return rrCost_;
3013  }
3014  }
3015  default:
3016  // 3 means 1 cycle. Keeps the order, but no extra delay.
3017  e.setWeight(3);
3018  return 3;
3019  }
3020  } else if (edgeWeightHeuristics_ == EWH_REAL) {
3021 // return edgeLatency(e, ii, tail, head);
3022 // }
3023 
3024  if (e.headPseudo()) {
3025  // pseudo deps do not really limit the scheduling.
3026  e.setWeight(0);
3027  return 0;
3028  }
3029 
3030  switch (e.edgeReason()) {
3032  return getOperationLatency(e.data());
3033  }
3036  // allowed to write a new value at the same cycle
3037  // another reads it (the load gets the old value)
3038  // TODO: this is a bug. this should be WAR, not RAW
3039  e.setWeight(0);
3040  return 0;
3041  } else {
3042  e.setWeight(1);
3043  return 1;
3044  }
3045  }
3048  switch (e.dependenceType()) {
3049  // TODO: some connectivity heuristics
3051  if (e.guardUse()) {
3052  int glat = n.guardLatency();
3053  // jump guard?
3054 
3055  // for predicated control flow ops the edge weight is
3056  // guard latency + delay slots, as the predicated cflow
3057  // ins has to be scehduled delay slots cycles before end.
3058  if (n.isMove() && n.move().isControlFlowMove()) {
3059  int ew = std::max(1, glat + delaySlots_);
3060  e.setWeight(ew);
3061  return ew;
3062  }
3063  // some other predicated operation
3064  int ew = std::max(1, glat);
3065  e.setWeight(ew);
3066  return ew;
3067  } else {
3068  // jump address of indirect branch
3069  // indirect control flow ops the delay slots is added
3070  // to the edgeweight, as the indirect control flow ins
3071  // has to be scehduled delay slots cycles before end.
3072  if (n.isMove() && n.move().isControlFlowMove()) {
3073  int ew = delaySlots_ +1;
3074  e.setWeight(ew);
3075  return ew;
3076  }
3077  }
3078  e.setWeight(1);
3079  return 1;
3080 
3081  }
3083  e.setWeight(0);
3084  return 0; // can be scheduled to same cycle
3085  }
3086  default: {
3087  e.setWeight(1);
3088  return 1;
3089  }
3090  }
3091  }
3092  default:
3093  e.setWeight(1);
3094  return 1; // can be scheduled to the next cycle (default)
3095  }
3096 
3097  } else {
3098  abortWithError("Unknown edge weight heuristics.");
3099  }
3100  e.setWeight(1);
3101  return 1;
3102 }
3103 
3104 /**
3105  * Sets a machine into DDG.
3106  *
3107  * This machine is used to some heuristics and helper functions that
3108  * selector uses, for example path length calculation and earliestCycle.
3109  *
3110  * If no machine is set, these functions will still work but will
3111  * give non-optimal results.
3112  *
3113  * @param machine machine to be used for heristics
3114  */
3115 void
3117 
3118  if (machine_ == &machine) {
3119  return;
3120  }
3121 
3122  // nullify edge weights to recalc them
3123  typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
3124  EdgeIterPair edges = boost::edges(graph_);
3125  for (EdgeIter i = edges.first; i != edges.second; i++) {
3126  GraphEdge* e = graph_[*i];
3127  e->setWeight(-1);
3128  }
3129 
3130  machine_ = &machine;
3133 
3134  if (&machine == &UniversalMachine::instance()) {
3135  rrCost_ = 3;
3136  } else {
3137  // heuristic value about connectivity delays.
3138  rrCost_ = int(
3139  std::max(2.0,
3140  3.0*((3-ma.bypassability()-(ma.connectivity()*2)))));
3141  }
3144 
3145  operationLatencies_.clear();
3146  for (int i = 0; i < fuNav.count(); i++) {
3147  const TTAMachine::FunctionUnit* fu = fuNav.item(i);
3148  for (int j = 0; j < fu->operationCount(); j++) {
3149  TTAMachine::HWOperation* hwop = fu->operation(j);
3150  int latency = hwop->latency();
3152  // if does not exist or is existing is bigger update
3154  || latency < operationLatencies_[name]) {
3155  operationLatencies_[name] = latency;
3156  }
3157  }
3158  }
3159  height_ = -1; // force path recalculation
3160  sourceDistances_.clear();
3161  sinkDistances_.clear();
3162  loopingSinkDistances_.clear();
3163  loopingSourceDistances_.clear();
3164 }
3165 
3166 /**
3167  * Checks whether the given node has all its predcessors scheduled.
3168  *
3169  * Ignores intra operation edges, thus if the predecessors belongs to the
3170  * same operation, it need not be scheduled for the node to be considered
3171  * ready.
3172  *
3173  * @return True in case all predecessors are scheduled.
3174  */
3175 bool
3177 
3178  // use the internal data structures to make this fast.
3179  // edgeset has too much set overhead,
3180  // inedge(n,i) is O(n^2) , this is linear with no overhead
3182  std::pair<InEdgeIter, InEdgeIter> edges =
3183  boost::in_edges(nd, graph_);
3184 
3185  bool srcOp = node.isSourceOperation();
3186  bool dstOp = node.isDestinationOperation();
3187 
3188  for (InEdgeIter ei = edges.first; ei != edges.second; ei++) {
3189  EdgeDescriptor ed = *ei;
3190  DataDependenceEdge& edge = *graph_[ed];
3191  if (edge.isBackEdge()) {
3192  continue;
3193  }
3194  const MoveNode& m = *graph_[boost::source(ed, graph_)];
3195 
3196  if (srcOp) {
3197  // operand move of same operation
3198  if ((m.isDestinationOperation() &&
3200  (m.isSourceOperation() &&
3201  &node.sourceOperation() == &m.sourceOperation())) {
3202  continue;
3203  }
3204  }
3205 
3206  if (dstOp && m.isDestinationOperation() &&
3208  continue;
3209  }
3210  if (!m.isPlaced()) {
3211  return false;
3212  }
3213  }
3214  return true;
3215 
3216 }
3217 
3218 /**
3219  * Checks whether the given node has all its successors scheduled.
3220  *
3221  * Ignores intra operation edges, thus if the successor belongs to the
3222  * same operation, it need not be scheduled for the node to be considered
3223  * ready.
3224  *
3225  * @return True in case all successors are scheduled.
3226  */
3227 bool
3229 
3230  // use the internal data structures to make this fast.
3231  // edgeset has too much set overhead,
3232  // inedge(n,i) is O(n^2) , this is linear with no overhead
3234  std::pair<OutEdgeIter, OutEdgeIter> edges =
3235  boost::out_edges(nd, graph_);
3236 
3237  for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
3238  EdgeDescriptor ed = *ei;
3239  DataDependenceEdge& edge = *graph_[ed];
3240  if (edge.isBackEdge()) {
3241  continue;
3242  }
3243  const MoveNode& m = *graph_[boost::target(ed, graph_)];
3244 
3245  const bool operandMoveOfSameOperation =
3248  const bool resultMoveOfSameOperation =
3250  &node.sourceOperation() == &m.sourceOperation());
3251  const bool operandsOfSameOperation =
3254  if (operandMoveOfSameOperation || resultMoveOfSameOperation ||
3255  operandsOfSameOperation) {
3256  continue;
3257  }
3258  if (!m.isPlaced()) {
3259  return false;
3260  }
3261  }
3262  return true;
3263 }
3264 
3265 bool
3266 DataDependenceGraph::otherSuccessorsScheduled(MoveNode& node, const NodeSet& ignoredNodes) const {
3267  // use the internal data structures to make this fast.
3268  // edgeset has too much set overhead,
3269  // inedge(n,i) is O(n^2) , this is linear with no overhead
3271  std::pair<OutEdgeIter, OutEdgeIter> edges =
3272  boost::out_edges(nd, graph_);
3273 
3274  for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
3275  EdgeDescriptor ed = *ei;
3276  DataDependenceEdge& edge = *graph_[ed];
3277  if (edge.isBackEdge()) {
3278  continue;
3279  }
3280  MoveNode* m = graph_[boost::target(ed, graph_)];
3281  if (!m->isPlaced()) {
3282  if (!AssocTools::containsKey(ignoredNodes, m)) {
3283  return false;
3284  }
3285  }
3286  }
3287  return true;
3288 }
3289 
3290 
3291 
3292 /**
3293  * Gets the lowest instruction latency for given operation.
3294  *
3295  * If latency is not known (no machine is given) does some simple
3296  * heuristics.
3297  *
3298  * This function should propably be on somewhere else.
3299  *
3300  * @param op operation whose minimum latency is being searched
3301  * @return minimum latency of given operation.
3302  */
3303 int
3305  std::map<TCEString, int>::const_iterator iter =
3306  operationLatencies_.find(name);
3307  if (iter != operationLatencies_.end()) {
3308  return iter->second;
3309  } else {
3310  return 1;
3311  }
3312 }
3313 
3314 /**
3315  * Checks if the graph already has an edge with same properties from same
3316  * node to same node.
3317  *
3318  * @param tailNode tail node of edge
3319  * @param headNode head node of edge
3320  * @param edge edge which for to test equality
3321  * @return true if equal edge exists, false if not exist
3322  */
3323 bool
3325  const MoveNode& tailNode, const MoveNode& headNode,
3326  const DataDependenceEdge& edge)
3327  const {
3328 
3329  typedef GraphTraits::out_edge_iterator outEdgeIter;
3330  std::pair<outEdgeIter, outEdgeIter> edges = boost::out_edges(
3333 
3334  for (outEdgeIter ei = edges.first; ei != edges.second; ei++) {
3335  if (boost::target(*ei, graph_) == hnd) {
3336  DataDependenceEdge* dde = graph_[(*ei)];
3337  if (*dde == edge) {
3338  return true;
3339  }
3340  }
3341  }
3342  return false;
3343 }
3344 
3345 /**
3346  * Connects nodes with an edge if equal edge between nodes not exists.
3347  * If equal edge already exists, deletes the given edge.
3348  *
3349  * @param tailNode tail node of edge
3350  * @param headNode head node of edge
3351  * @param edge edge which is added to graph or deleted.
3352  * @return true if connected, false if already existed.
3353  */
3354 bool
3356  const MoveNode& tailNode, const MoveNode& headNode,
3357  DataDependenceEdge* edge) {
3358  if (hasEqualEdge(tailNode, headNode, *edge)) {
3359  delete edge;
3360  return false;
3361  } else {
3363  return true;
3364  }
3365 }
3366 
3367 /**
3368  * Creates a subgraph of a ddg from set of cede snippets
3369  * which contains instructions which contains moves
3370  * in this graph.
3371  *
3372  * @param nodes code being included in the subgraph
3373  * @param includeLoops whether to include loop-carried dependencies
3374  * @return the created subgraph
3375  */
3378  NodeSet& nodes, bool includeLoops) {
3379  DataDependenceGraph* subGraph =
3380  new DataDependenceGraph(
3381  allParamRegs_, "", registerAntidependenceLevel_, NULL, false,
3382  !includeLoops);
3383 
3384  if (machine_ != NULL) {
3385  subGraph->setMachine(*machine_);
3386  }
3387 
3388  constructSubGraph(*subGraph, nodes);
3389 
3390  typedef std::set<ProgramOperationPtr, ProgramOperationPtrComparator> POSet;
3391  POSet subgraphPOs;
3392 
3393  // copy the node -> bbn mapping.
3394  // also find POs to copy.
3395  for (int i = 0, nc = subGraph->nodeCount(); i < nc; i++) {
3396  MoveNode& mn = subGraph->node(i);
3397  BasicBlockNode* bbn = moveNodeBlocks_[&mn];
3398  subGraph->moveNodeBlocks_[&mn] = bbn;
3399  if (mn.isSourceOperation()) {
3400  subgraphPOs.insert(mn.sourceOperationPtr());
3401  }
3402 
3403  if (mn.isDestinationOperation()) {
3404  subgraphPOs.insert(mn.destinationOperationPtr());
3405  }
3406  }
3407  for (auto i: subgraphPOs) {
3408  subGraph->programOperations_.push_back(i);
3409  }
3410  return subGraph;
3411 }
3412 
3413 /**
3414  * Returns a version of the graph with only true dependence edges.
3415  */
3418  bool removeMemAntideps, bool ignoreMemDeps) {
3419  DataDependenceGraph* subGraph =
3420  new DataDependenceGraph(
3422  NULL, false, false);
3423  NodeSet nodes;
3424  for (int i = 0; i < nodeCount(); ++i) {
3425  nodes.insert(&node(i));
3426  }
3427  if (machine_ != NULL)
3428  subGraph->setMachine(*machine_);
3429 
3430  constructSubGraph(*subGraph, nodes);
3431 
3432  for (int i = 0; i < nodeCount(); i++) {
3433  MoveNode& tail = node(i);
3434  for (int e = 0; e < subGraph->outDegree(tail);) {
3435  DataDependenceEdge& edge = subGraph->outEdge(tail,e);
3437  isNotAvoidable(edge)) {
3438  e++;
3439  continue;
3440  }
3441  // consider the memory dependencies
3443  (ignoreMemDeps || (edge.isFalseDep() && removeMemAntideps))) {
3444  subGraph->dropEdge(edge);
3445  } else {
3446  e++;
3447  }
3448  }
3449  }
3450  return subGraph;
3451 }
3452 
3453 /**
3454  * Returns a version of the graph with only nodes that are in the
3455  * critical path.
3456  */
3459  DataDependenceGraph* subGraph =
3460  new DataDependenceGraph(
3461  allParamRegs_, "critical path DDG",
3462  registerAntidependenceLevel_, NULL, false, false);
3463 
3464  if (machine_ != NULL)
3465  subGraph->setMachine(*machine_);
3466 
3467  NodeSet nodes;
3468  for (int i = 0; i < nodeCount(); ++i) {
3469  if (isInCriticalPath(node(i)))
3470  nodes.insert(&node(i));
3471  }
3472  constructSubGraph(*subGraph, nodes);
3473 
3474  return subGraph;
3475 }
3476 
3477 /**
3478  * Returns a version of the graph with only nodes and edges that
3479  * present memory dependencies.
3480  */
3483  DataDependenceGraph* subGraph =
3484  new DataDependenceGraph(
3485  allParamRegs_, "memory DDG",
3486  registerAntidependenceLevel_, NULL, false, false);
3487 
3488  if (machine_ != NULL)
3489  subGraph->setMachine(*machine_);
3490 
3491  NodeSet nodes;
3492  for (int i = 0; i < nodeCount(); ++i) {
3493 
3494  MoveNode& mn = node(i);
3495  EdgeSet outEdg = outEdges(mn);
3496  bool found = false;
3497  for (EdgeSet::iterator ei = outEdg.begin(); ei != outEdg.end(); ei++) {
3498  Edge& edge = **ei;
3500  nodes.insert(&node(i));
3501  found = true;
3502  break;
3503  }
3504  }
3505 
3506  if (found) continue;
3507  EdgeSet inEdg = inEdges(mn);
3508  for (EdgeSet::iterator ei = inEdg.begin(); ei != inEdg.end(); ei++) {
3509  Edge& edge = **ei;
3511  nodes.insert(&node(i));
3512  break;
3513  }
3514  }
3515 
3516  }
3517  constructSubGraph(*subGraph, nodes);
3518 
3519  return subGraph;
3520 }
3521 
3522 /**
3523  * Creates a subgraph of a ddg from set of cede snippets
3524  * which contains instructions which contains moves
3525  * in this graph.
3526  *
3527  * @param cs code being included in the subgraph
3528  * @param includeLoops whether to include loop-carried dependencies
3529  * @return the created subgraph
3530  */
3533  TTAProgram::CodeSnippet& cs, bool includeLoops) {
3534  NodeSet moveNodes;
3535  int nc = nodeCount();
3536  for (int i = 0; i < nc; i++) {
3537  MoveNode& mn = node(i,false);
3538  if (mn.isMove()) {
3539  TTAProgram::Move& move = mn.move();
3540  if (move.isInInstruction()) {
3541  TTAProgram::Instruction& parentIns = move.parent();
3542  if (parentIns.isInProcedure()) { // is in code snippet
3543  if (&parentIns.parent() == &cs) {
3544  moveNodes.insert(&mn);
3545  }
3546  }
3547  }
3548  }
3549  }
3550  return createSubgraph(moveNodes, includeLoops);
3551 }
3552 
3553 /**
3554  * Creates a subgraph of a ddg from set of cede snippets
3555  * which contains instructions which contains moves
3556  * in this graph.
3557  *
3558  * @param codeSnippets code being included in the subgraph
3559  * @param includeLoops whether to include loop-carried dependencies
3560  * @return the created subgraph
3561  */
3564  std::list<TTAProgram::CodeSnippet*>& codeSnippets, bool includeLoops) {
3565  NodeSet moveNodes;
3566 
3567  int nc = nodeCount();
3568  for (int i = 0; i < nc; i++) {
3569  MoveNode& mn = node(i,false);
3570  if (mn.isMove()) {
3571  TTAProgram::Move& move = mn.move();
3572  TTAProgram::Instruction& parentIns = move.parent();
3573  if (parentIns.isInProcedure()) { // is in code snippet
3574  for (std::list<TTAProgram::CodeSnippet*>::iterator iter =
3575  codeSnippets.begin();
3576  iter != codeSnippets.end(); iter++) {
3577  TTAProgram::CodeSnippet& cs = **iter;
3578  if (&move.parent().parent() == &cs) {
3579  moveNodes.insert(&mn);
3580  }
3581  }
3582  }
3583  }
3584  }
3585  return createSubgraph(moveNodes, includeLoops);
3586 }
3587 
3588 /**
3589  *
3590  * Gets a node of a move.
3591  *
3592  * Warning: this operations is currently O(n).
3593  * Smarter data structure needed for faster operation,
3594  * propably should be implemented.
3595  *
3596  * @param move move.
3597  * @return MoveNode of the given move
3598  */
3599 MoveNode&
3601 
3602  auto i = nodesOfMoves_.find(&move);
3603  if (i != nodesOfMoves_.end()) {
3604  return *(i->second);
3605  }
3606 
3607  TCEString msg = "move not in ddg: " +
3608  Conversion::toString(reinterpret_cast<long>(&move)) + " " +
3610  throw InstanceNotFound(__FILE__,__LINE__,__func__, msg);
3611 }
3612 
3613 /**
3614  * Drops loop edges from a sub-DDG.
3615  *
3616  * This works only with simple control structures;
3617  * Only works for edges marked as loop edges.
3618  * Currently loop edges spanning over multiple basic blocks may be missing.
3619  */
3621  const int nc = nodeCount();
3622 
3623  // first loop thru all nodes.
3624  for (int n = 0; n < nc; n++) {
3625  NodeDescriptor nd = boost::vertex(n, graph_);
3626 
3627  // the thru all output edges of the node.
3628  // this is propably the fastest way to iterate over
3629  // all edges of a graph. (or is just all edges faster?)
3630  std::pair<OutEdgeIter, OutEdgeIter> edges =
3631  boost::out_edges(nd, graph_);
3632 
3633  for (OutEdgeIter ei = edges.first; ei != edges.second;) {
3634  DataDependenceEdge* e = graph_[(*ei)];
3635  if (e->isBackEdge()) {
3636  // remove from internal bookkeeping
3637  boost::remove_edge(*ei, graph_);
3638 
3639  // iterators must be resetted when deleted something.
3640  edges = boost::out_edges(nd, graph_);
3641  ei = edges.first;
3642 
3643  // remove from edge descriptor cache
3644  DataDependenceGraph::EdgeDescMap::iterator
3645  edIter = edgeDescriptors_.find(e);
3646  if (edIter != edgeDescriptors_.end()) {
3647  edgeDescriptors_.erase(edIter);
3648  }
3649 
3650  for (unsigned int i = 0; i < childGraphs_.size(); i++) {
3651  childGraphs_.at(i)->dropEdge(*e);
3652  }
3653  } else {
3654  ei++;
3655  }
3656  }
3657  }
3658 }
3659 
3660 /**
3661  * Tells whether the root graph is a procedure-wide ddg or created from
3662  * a smaller piece of code.
3663  *
3664  * This is needed for dead result elimination.
3665  *
3666  * @return if root graph of the subgraph tree contains whole procedure.
3667  */
3668 bool
3670  if (parentGraph_ == NULL) {
3671  return procedureDDG_;
3672  } else {
3673  return static_cast<DataDependenceGraph*>(parentGraph_)
3675  }
3676 }
3677 
3678 /**
3679  * Addds inter-BB-Anti edges between the the basic blocks.
3680  *
3681  * currently quite a heavy routine
3682  *
3683  * @param bbn1 first basic block, executed first, sources of antidependence
3684  * edges
3685  * @param bbn2 second basic block, executed later, targets of antidependence
3686  * edges
3687  */
3688 void
3690  BasicBlockNode& bbn1, BasicBlockNode& bbn2, bool loopEdges) {
3691  std::map<TCEString, TTAProgram::Move*> firstWrites2;
3692  std::map<TCEString, TTAProgram::Move*> lastReads1;
3693  std::map<TCEString, TTAProgram::Move*> lastWrites1;
3694  std::map<TCEString, TTAProgram::Move*> lastGuards1;
3695 
3696  TTAProgram::BasicBlock& bb1 = bbn1.basicBlock();
3697  TTAProgram::BasicBlock& bb2 = bbn2.basicBlock();
3698 
3699  // find the first writes in the next BB.
3700  for (int i2 = 0; i2 < bb2.instructionCount(); i2++) {
3702  for (int j2 = 0; j2 < ins.moveCount(); j2++) {
3703  TTAProgram::Move& move = ins.move(j2);
3704  TTAProgram::Terminal& dest = move.destination();
3705  if (dest.isGPR()) {
3707 
3708  std::map<TCEString, TTAProgram::Move*>::iterator iter2 =
3709  firstWrites2.find(reg2);
3710  if (iter2 == firstWrites2.end()) {
3711  firstWrites2[reg2] = &move;
3712  }
3713  }
3714  }
3715  }
3716 
3717  // find the last reads, writes and guard uses from first BB.
3718  for (int i1 = bb1.instructionCount()-1; i1 >= 0 ; i1--) {
3720  for (int j1 = 0; j1 < ins.moveCount(); j1++) {
3721  TTAProgram::Move& move = ins.move(j1);
3722  TTAProgram::Terminal& dest = move.destination();
3723  TTAProgram::Terminal& src = move.source();
3724  // Writes for WaWs
3725  if (dest.isGPR()) {
3727 
3728  std::map<TCEString, TTAProgram::Move*>::iterator iter1 =
3729  lastWrites1.find(reg1);
3730  if (iter1 == lastWrites1.end()) {
3731  lastWrites1[reg1] = &move;
3732  }
3733  }
3734  // reads for WaRs
3735  if (src.isGPR()) {
3737 
3738  std::map<TCEString, TTAProgram::Move*>::iterator iter1 =
3739  lastReads1.find(reg1);
3740  if (iter1 == lastReads1.end()) {
3741  lastReads1[reg1] = &move;
3742  }
3743  }
3744  // guard uses
3745  if (!move.isUnconditional()) {
3746  const TTAMachine::Guard& g = move.guard().guard();
3747  const TTAMachine::RegisterGuard* rg =
3748  dynamic_cast<const TTAMachine::RegisterGuard*>(&g);
3749  if (rg != NULL) {
3751  *rg->registerFile(), rg->registerIndex());
3752 
3753  std::map<TCEString, TTAProgram::Move*>::iterator iter2 =
3754  lastGuards1.find(reg1);
3755  if (iter2 == lastGuards1.end()) {
3756  lastGuards1[reg1] = &move;
3757  }
3758  }
3759  }
3760  }
3761  }
3762 
3763  // then go thru them
3764  for (std::map<TCEString, TTAProgram::Move*>::iterator iter2 =
3765  firstWrites2.begin();
3766  iter2 != firstWrites2.end(); iter2++) {
3767  const TCEString& reg2 = iter2->first;
3768  MoveNode& mn2 = nodeOfMove(*(iter2->second));
3769 
3770  // WaRs
3771  TTAProgram::Move* move1 = lastReads1[reg2];
3772  if (move1 != NULL) {
3774  new DataDependenceEdge(
3776  DataDependenceEdge::DEP_WAR, reg2, false, false, false,
3777  false, loopEdges);
3778  connectOrDeleteEdge(nodeOfMove(*move1), mn2, edge);
3779  }
3780 
3781  // WaWs
3782  move1 = lastWrites1[reg2];
3783  if (move1 != NULL) {
3785  new DataDependenceEdge(
3787  DataDependenceEdge::DEP_WAW, reg2, false, false, false,
3788  false, loopEdges);
3789  connectOrDeleteEdge(nodeOfMove(*move1), mn2, edge);
3790  }
3791 
3792  // guard WaRs
3793  move1 = lastGuards1[reg2];
3794  if (move1 != NULL) {
3796  new DataDependenceEdge(
3798  DataDependenceEdge::DEP_WAR, reg2, true, false, false,
3799  false, loopEdges);
3800  connectOrDeleteEdge(nodeOfMove(*move1), mn2, edge);
3801  }
3802  }
3803 }
3804 
3805 /**
3806  * Copies all dependencies going to and from a movenode to another
3807  *
3808  * Creates copy of all edges going to and from an movenode and
3809  * make them to point to and fro another movenode.
3810  *
3811  * @param src movenode to copy dependencies from
3812  * @param dst movenode to copy dependencies to
3813  * @todo should this method be in base class? would require graphedge.clone()
3814  */
3815 void
3817  const MoveNode& src, MoveNode& dst, bool ignoreSameBBBackedges,
3818  bool moveOverLoopEdge) {
3819  // performance optimization
3820  NodeDescriptor nd = descriptor(src);
3821 
3822  // use the internal data structures to make this fast.
3823  // edgeset has too much set overhead,
3824  // inedge(n,i) is O(n^2) , this is linear with no overhead
3825  std::pair<InEdgeIter, InEdgeIter> iEdges =
3826  boost::in_edges(nd, graph_);
3827 
3828  for (InEdgeIter ii = iEdges.first; ii != iEdges.second; ii++) {
3829  EdgeDescriptor ed = *ii;
3831  MoveNode* tail = graph_[boost::source(ed, graph_)];
3832  if (ignoreSameBBBackedges && edge->isBackEdge() &&
3833  &getBasicBlockNode(src) == &getBasicBlockNode(*tail)) {
3834  continue;
3835  }
3836  DataDependenceEdge* newEdge = new DataDependenceEdge(
3837  *edge, (moveOverLoopEdge && tail != &src && tail != &dst));
3838  connectNodes(*tail, dst, *newEdge);
3839  }
3840 
3841  std::pair<OutEdgeIter, OutEdgeIter> oEdges =
3842  boost::out_edges(nd, graph_);
3843 
3844  for (OutEdgeIter oi = oEdges.first; oi != oEdges.second; oi++) {
3845  EdgeDescriptor ed = *oi;
3847  MoveNode* head = graph_[boost::target(ed, graph_)];
3848  if (ignoreSameBBBackedges && edge->isBackEdge() &&
3849  &getBasicBlockNode(src) == &getBasicBlockNode(*head)) {
3850  continue;
3851  }
3852  DataDependenceEdge* newEdge = new DataDependenceEdge(
3853  *edge, (moveOverLoopEdge && head != &src && head != &dst));
3854  connectNodes(dst, *head, *newEdge);
3855  }
3856 }
3857 
3858 /**
3859  * Copies all incoming guard dependencies going to a movenode to another
3860  *
3861  * @param src movenode to copy dependencies from
3862  * @param dst movenode to copy dependencies to
3863  */
3864 void
3866  const MoveNode& src, MoveNode& dst) {
3867 
3868  // performance optimization
3869  NodeDescriptor nd = descriptor(src);
3870 
3871  // use the internal data structures to make this fast.
3872  // edgeset has too much set overhead,
3873  // inedge(n,i) is O(n^2) , this is linear with no overhead
3874  std::pair<InEdgeIter, InEdgeIter> iEdges =
3875  boost::in_edges(nd, graph_);
3876 
3877  for (InEdgeIter ii = iEdges.first; ii != iEdges.second; ii++) {
3878  EdgeDescriptor ed = *ii;
3882  edge->guardUse()) {
3883  DataDependenceEdge* newEdge = new DataDependenceEdge(*edge);
3884  MoveNode& tail = *graph_[boost::source(ed, graph_)];
3885  connectNodes(tail, dst, *newEdge);
3886  }
3887  }
3888 }
3889 
3890 /**
3891  * Copies all outgoing guard war dependencies going to a movenode to another
3892  *
3893  * @param src movenode to copy dependencies from
3894  * @param dst movenode to copy dependencies to
3895  */
3896 void
3898  const MoveNode& src, MoveNode& dst) {
3899 
3900  // performance optimization
3901  NodeDescriptor nd = descriptor(src);
3902 
3903  // use the internal data structures to make this fast.
3904  // edgeset has too much set overhead,
3905  // inedge(n,i) is O(n^2) , this is linear with no overhead
3906  std::pair<OutEdgeIter, OutEdgeIter> oEdges =
3907  boost::out_edges(nd, graph_);
3908 
3909  for (OutEdgeIter oi = oEdges.first; oi != oEdges.second; oi++) {
3910  EdgeDescriptor ed = *oi;
3914  edge->guardUse()) {
3915  DataDependenceEdge* newEdge = new DataDependenceEdge(*edge);
3916  MoveNode& head = *graph_[boost::target(ed, graph_)];
3917  connectNodes(dst, head, *newEdge);
3918  }
3919  }
3920 }
3921 
3922 /**
3923  * Calculates number of register WAR antidependecies originating from
3924  * given node
3925  *
3926  * @param mn Movenodes whose dependencies to calculate
3927  * @return number of register WAR antidependencies originating
3928  * from given node
3929  */
3931  int count = 0;
3932  EdgeSet oEdges = outEdges(mn);
3933  for (EdgeSet::iterator iter =
3934  oEdges.begin(); iter != oEdges.end(); iter++) {
3935  if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
3936  (*iter)->dependenceType() == DataDependenceEdge::DEP_WAR) {
3937  count++;
3938  }
3939  }
3940  return count;
3941 }
3942 
3943 /**
3944  * Calculates number of register RAW dependecies originating from
3945  * given node
3946  *
3947  * @param mn Movenodes whose dependencies to calculate
3948  * @param onlySchedules only care about dependencies to Scheduled nodes.
3949  * @return number of register RAW dependencies originating
3950  * from given node
3951  */
3953  const MoveNode& mn, bool onlyScheduled) {
3954  int count = 0;
3955  EdgeSet oEdges = outEdges(mn);
3956  for (EdgeSet::iterator iter =
3957  oEdges.begin(); iter != oEdges.end(); iter++) {
3958  if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
3959  (*iter)->dependenceType() == DataDependenceEdge::DEP_RAW) {
3960  MoveNode& mn = headNode(**iter);
3961  if (!onlyScheduled || mn.isPlaced()) {
3962  count++;
3963  }
3964  }
3965  }
3966  return count;
3967 }
3968 
3969 /**
3970  * Calculates number of register antidependecies originating from
3971  * given node
3972  *
3973  * @param mn Movenodes whose dependencies to calculate
3974  * @return number of register antidependencies originating
3975  * from given node
3976  */
3977 
3979  EdgeSet oEdges = outEdges(mn);
3980  for (EdgeSet::iterator iter =
3981  oEdges.begin(); iter != oEdges.end(); iter++) {
3982  if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
3983  (((*iter)->dependenceType() == DataDependenceEdge::DEP_RAW) ||
3984  ((*iter)->dependenceType() == DataDependenceEdge::DEP_WAW))) {
3985  MoveNode& head = headNode(**iter);
3986  if (head.move().isUnconditional()) {
3987  return true;
3988  }
3989  }
3990  }
3991  return false;
3992 
3993 }
3994 
3995 /**
3996  * Counts all incoming antidependence edges to a movenode.
3997  *
3998  * @param mn MoveNode whose edges we are counting
3999  * @return number of incoming antidependence edges.
4000  */
4002  EdgeSet iEdges = inEdges(mn);
4003  int count = 0;
4004  for (EdgeSet::iterator iter =
4005  iEdges.begin(); iter != iEdges.end(); iter++) {
4006  if ((*iter)->edgeReason() == DataDependenceEdge::EDGE_REGISTER &&
4007  (((*iter)->dependenceType() == DataDependenceEdge::DEP_WAR) ||
4008  ((*iter)->dependenceType() == DataDependenceEdge::DEP_WAW))) {
4009  count++;
4010  }
4011  }
4012  return count;
4013 }
4014 
4015 /**
4016  * Returns the only incoming guard edge to given node
4017  *
4018  * if there are multiple incoming guard edges, return NULL.
4019  *
4020  * @param mn MoveNode whose incoming edges we are searching.
4021  * @return only guard edge to mn or NULL if no or multiple.
4022  */
4025  const MoveNode& mn) const {
4026  DataDependenceEdge* guard = NULL;
4028 
4029  for (DataDependenceGraph::EdgeSet::iterator i = iEdges.begin();
4030  i != iEdges.end(); i++) {
4031  DataDependenceEdge* iEdge = *i;
4032  if (iEdge->guardUse() && iEdge->dependenceType() ==
4034  if (guard == NULL) {
4035  guard = iEdge;
4036  } else {
4037  if (!(*guard == *iEdge) ||
4038  &tailNode(*iEdge) != &tailNode(*guard)) {
4039  return NULL; // too complicated guard
4040  }
4041  }
4042  }
4043  }
4044  return guard;
4045 }
4046 
4049  NodeSet preds;
4051  for (DataDependenceGraph::EdgeSet::iterator i = iEdges.begin();
4052  i != iEdges.end(); i++) {
4053  DataDependenceEdge* iEdge = *i;
4054  if (iEdge->guardUse() && iEdge->dependenceType() ==
4056  preds.insert(&tailNode(*iEdge));
4057  }
4058  }
4059  return preds;
4060 }
4061 
4062 
4063 /**
4064  * Returns the source of only ordinary register RAW edge to given node,
4065  * ie the only move which writes the value this move reads.
4066  *
4067  * backEdges: 0: do not care
4068  * 1: only backedges
4069  * 2: no backedges
4070  *
4071  * guardEdges: 0: do not care
4072  * 1: only guard edges
4073  * 2: no guard edges
4074  *
4075  * if there are multiple nodes where the value may come, return NULL,
4076  * or if none found.
4077  *
4078  * @param mn MoveNode whose predecessor noves we are searching.
4079  * @return only move writing reg this reads or NULL if no or multiple.
4080  */
4081 
4082 MoveNode*
4084  const MoveNode& mn, int guardEdges, int backEdges)
4085  const {
4086  MoveNode* source = NULL;
4087  NodeDescriptor nd = descriptor(mn);
4088 
4089  // use the internal data structures to make this fast.
4090  // edgeset has too much set overhead,
4091  // inedge(n,i) is O(n^2) , this is linear with no overhead
4092  std::pair<InEdgeIter, InEdgeIter> edges =
4093  boost::in_edges(nd, graph_);
4094 
4095  for (InEdgeIter ei = edges.first; ei != edges.second; ei++) {
4096  EdgeDescriptor ed = *ei;
4098  if (backEdges == 1 && !edge->isBackEdge()) continue;
4099  if (backEdges == 2 && edge->isBackEdge()) continue;
4100  if (guardEdges == 1 && !edge->guardUse()) continue;
4101  if (guardEdges == 2 && edge->guardUse()) continue;
4104  !edge->headPseudo() && !edge->tailPseudo()) {
4105  if (source == NULL) {
4106  source = graph_[boost::source(ed, graph_)];
4107  } else {
4108  return NULL;
4109  }
4110  }
4111  }
4112  return source;
4113 }
4114 
4115 /**
4116  * Returns the destinations of ordinary register RAW edge to given node,
4117  * ie the moves which reads the value this move writes.
4118  *
4119  * @param mn MoveNode whose succssor moves we are searching.
4120  * @return only move reading reg this writes or NULL if no or multiple.
4121  */
4122 
4123 std::map<DataDependenceEdge*, MoveNode*, DataDependenceEdge::Comparator>
4125  const MoveNode& mn, bool allowBackEdges) const {
4126  std::map<DataDependenceEdge*, MoveNode*, DataDependenceEdge::Comparator>
4127  destination;
4128  NodeDescriptor nd = descriptor(mn);
4129 
4130  // use the internal data structures to make this fast.
4131  // edgeset has too much set overhead,
4132  // inedge(n,i) is O(n^2) , this is linear with no overhead
4133  std::pair<OutEdgeIter, OutEdgeIter> edges =
4134  boost::out_edges(nd, graph_);
4135 
4136  for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
4137  EdgeDescriptor ed = *ei;
4141  !edge->tailPseudo()) {
4142  if (!edge->headPseudo() && (allowBackEdges || !edge->isBackEdge())) {
4143  destination.insert(std::make_pair(edge, graph_[boost::target(ed, graph_)]));
4144  } else {
4145  destination.clear();
4146  break;
4147  }
4148  }
4149  }
4150  return destination;
4151 }
4152 
4153 
4154 /**
4155  * Returns the destinations of ordinary register RAW edge to given node,
4156  * ie the moves which reads the value this move writes.
4157  *
4158  * @param mn MoveNode whose succssor moves we are searching.
4159  * @return only move reading reg this writes or NULL if no or multiple.
4160  */
4161 
4164  const MoveNode& mn, bool allowGuardEdges, bool allowBackEdges) const {
4165  NodeSet destination;
4166  NodeDescriptor nd = descriptor(mn);
4167 
4168  // use the internal data structures to make this fast.
4169  // edgeset has too much set overhead,
4170  // inedge(n,i) is O(n^2) , this is linear with no overhead
4171  std::pair<OutEdgeIter, OutEdgeIter> edges =
4172  boost::out_edges(nd, graph_);
4173 
4174  for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
4175  EdgeDescriptor ed = *ei;
4179  (allowGuardEdges || !edge->guardUse())
4180  && !edge->tailPseudo()) {
4181  if (!edge->headPseudo() && (allowBackEdges || !edge->isBackEdge())) {
4182  destination.insert(graph_[boost::target(ed, graph_)]);
4183  } else {
4184  destination.clear();
4185  break;
4186  }
4187  }
4188  }
4189  return destination;
4190 }
4191 
4192 /**
4193  * Tracks the origin of the data a movenode reads. Goes back thru DDG
4194  * and tracks register-to register reads.
4195  *
4196  * If data comes from operation, returns the operation result read.
4197  * If data comes from stack pointer, returns the stack pointer read.
4198  * If the data may come from multiple places (conditional writes to reg,
4199  * or writes to same reg in multiple BB's), return the move which read the
4200  * value from the reg.
4201  */
4202 const MoveNode*
4204  const MoveNode& mn, const std::string& sp) const {
4205  const MoveNode* node = &mn;
4206 
4207  while(true) {
4208  if (node->isSourceReg(sp)) {
4209  return node;
4210  }
4212  if (src == NULL) {
4213  return node;
4214  } else {
4215  // this should not be needed if incoming code were sensible
4216  // but it often is not. extra check to prevetn forever loop.
4217  if (node == src) {
4218  return node;
4219  }
4220  node = src;
4221  }
4222  }
4223 }
4224 
4225 
4226 /**
4227  * Returns the register war successors of the given node.
4228  *
4229  * If node has no register war successors, an empty set is returned.
4230  * Note: the node can also be a successor of itself.
4231  * Register war successor means successor which is
4232  * connected by register or ra war edge
4233  *
4234  * @param node The node of which successors to find.
4235  * @return Set of root nodes, can be empty.
4236  */
4237 
4240 
4241  NodeSet succ;
4242 
4244  EdgeSet out = outEdges(node);
4245  typedef EdgeSet::iterator EdgeIterator;
4246 
4247  for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
4248  DataDependenceEdge& e = **i;
4252  succ.insert(&headNode(**i, nd));
4253  }
4254  }
4255 
4256  return succ;
4257 }
4258 
4259 /**
4260  * Returns the register raw successors of the given node.
4261  *
4262  * If node has no register raw successors, an empty set is returned.
4263  * Note: the node can also be a successor of itself.
4264  * Register raw successor means successor which is
4265  * connected by register or ra raw edge
4266  *
4267  * @param node The node of which successors to find.
4268  * @return Set of root nodes, can be empty.
4269  */
4270 
4273 
4274  NodeSet succ;
4275 
4277  EdgeSet out = outEdges(node);
4278  typedef EdgeSet::iterator EdgeIterator;
4279 
4280  for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
4281  DataDependenceEdge& e = **i;
4285  succ.insert(&headNode(**i, nd));
4286  }
4287  }
4288 
4289  return succ;
4290 }
4291 
4292 /**
4293  * Returns the register raw predecessors of the given node.
4294  *
4295  * If node has no register raw predecessors, an empty set is returned.
4296  * Note: the node can also be a predecessor of itself.
4297  * Register raw predecessor means predecessor which is
4298  * connected by register or ra raw edge
4299  *
4300  * backEdges: 0: do not care
4301  * 1: only backedges
4302  * 2: no backedges
4303  *
4304  *
4305  * @param node The node of which successors to find.
4306  * @return Set of root nodes, can be empty.
4307  */
4308 
4310 DataDependenceGraph::regRawPredecessors(const MoveNode& node, int backedges) const {
4311 
4312  NodeSet pred;
4313 
4315  EdgeSet in = inEdges(node);
4316  typedef EdgeSet::iterator EdgeIterator;
4317 
4318  for (EdgeIterator i = in.begin(); i != in.end(); ++i) {
4319  DataDependenceEdge& e = **i;
4320  if (backedges == 1 && !e.isBackEdge()) {
4321  continue;
4322  } else if (backedges == 2 && e.isBackEdge()) {
4323  continue;
4324  }
4328  pred.insert(&tailNode(**i, nd));
4329  }
4330  }
4331  return pred;
4332 }
4333 
4334 /**
4335  * Returns the register waw successors of the given node.
4336  *
4337  * If node has no reg waw successors, an empty set is returned.
4338  * Note: the node can also be a successor of itself.
4339  * register waw successor means successor which is
4340  * connected by register waw edge.
4341  *
4342  * @param node The node of which successors to find.
4343  * @return Set of root nodes, can be empty.
4344  */
4345 
4348 
4349  NodeSet succ;
4350 
4352  EdgeSet out = outEdges(node);
4353  typedef EdgeSet::iterator EdgeIterator;
4354 
4355  for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
4356  DataDependenceEdge& e = **i;
4357 
4358  // if we would bypass also over ra, then allow also ra in following
4361  succ.insert(&headNode(**i, nd));
4362  }
4363  }
4364 
4365  return succ;
4366 }
4367 
4368 
4369 /**
4370  * Creates antidependencies between certains nodes of a ddg.
4371  *
4372  * This is used after regcopyadded to insert antideps between the
4373  * temp registers added by the regcopyadder.
4374  *
4375  * All nodes given to the method should be scheduled.
4376  * The nodes should have already been added to the graph.
4377  *
4378  * @param nodes nodes whose antidependencies to add.
4379  */
4380 void
4383 
4384  typedef std::map<int, NodeSet >
4385  MovesByCycles;
4386  MovesByCycles movesInCycles;
4387  typedef std::map<TCEString, NodeSet> NodeSetMap;
4388 
4389  NodeSetMap reads;
4390  NodeSetMap writes;
4391  // insert all moves int correct cycle in bookkeeping
4392  for (NodeSet::iterator nsIter = nodes.begin();
4393  nsIter != nodes.end(); nsIter++) {
4394  MoveNode* mn = *nsIter;
4395  assert(mn->isPlaced());
4396  movesInCycles[mn->cycle()].insert(mn);
4397  }
4398 
4399  // loop thru all cycles
4400  for (MovesByCycles::iterator i = movesInCycles.begin();
4401  i != movesInCycles.end(); i++) {
4402 
4403  NodeSet& nodesInCycle = i->second;
4404  // then check sources of all nodes in the cycle
4405  for (NodeSet::iterator j = nodesInCycle.begin();
4406  j != nodesInCycle.end(); j++) {
4407  MoveNode* mn = *j;
4408  TTAProgram::Move& move = mn->move();
4409  TTAProgram::Terminal& src = move.source();
4410  if (src.isGPR()) {
4412  reads[reg].insert(mn);
4413  }
4414  }
4415 
4416  // then check destinations of all nodes in the cycle
4417  for (NodeSet::iterator j = nodesInCycle.begin();
4418  j != nodesInCycle.end(); j++) {
4419 
4420  MoveNode* mn = *j;
4421  TTAProgram::Move& move = mn->move();
4422  TTAProgram::Terminal& dst = move.destination();
4423  if (dst.isGPR()) {
4425 
4426  NodeSet& readsFromReg = reads[reg];
4427  NodeSet& writesToReg = writes[reg];
4428 
4429  // create the dependencies.
4430  // WaRs
4431  for (NodeSet::iterator k = readsFromReg.begin();
4432  k != readsFromReg.end(); k++) {
4433  MoveNode& prevMN = **k;
4434  if (!exclusingGuards(prevMN, *mn)) {
4436  new DataDependenceEdge(
4439  connectOrDeleteEdge(**k, *mn, edge);
4440  }
4441  }
4442 
4443  // WaWs.
4444  for (NodeSet::iterator k = writesToReg.begin();
4445  k != writesToReg.end(); k++) {
4446  MoveNode& prevMN = **k;
4447  if (!exclusingGuards(prevMN, *mn)) {
4449  new DataDependenceEdge(
4452  connectOrDeleteEdge(**k, *mn, edge);
4453  }
4454  }
4455 
4456  // if this is unconditional, kills previous writes to the reg
4457  if (move.isUnconditional()) {
4458  writes[reg].clear();
4459  reads[reg].clear();
4460  }
4461  writes[reg].insert(mn);
4462  }
4463  }
4464  }
4465 }
4466 
4467 
4468 
4469 /*
4470  * Checks whether two movenodes have exclusive guard, ie
4471  * same guard but inverted on one of them.
4472  *
4473  * If not sure returns false
4474  *
4475  * @param mn1 first movenode to check.
4476  * @param mn2 second movenode to check.
4477  * @return true if they have same guard inverted, false otherwise.
4478  */
4479 bool
4481  const MoveNode& mn1, const MoveNode& mn2) const {
4482  if (!mn1.isMove() || !mn2.isMove()) {
4483  return false;
4484  }
4485  const TTAProgram::Move& move1 = mn1.move();
4486  const TTAProgram::Move& move2 = mn2.move();
4487  if (move1.isUnconditional() || move2.isUnconditional()) {
4488  return false;
4489  }
4490  TTAProgram::MoveGuard& mg1 = move1.guard();
4491  TTAProgram::MoveGuard& mg2 = move2.guard();
4492  if (mg1.isInverted() == mg2.isInverted()) {
4493  return false;
4494  }
4495  NodeSet incomingGuards1 =
4496  guardRawPredecessors(mn1);
4497 
4498  NodeSet incomingGuards2 =
4499  guardRawPredecessors(mn2);
4500 
4501  return !incomingGuards1.empty() &&
4502  incomingGuards1 == incomingGuards2;
4503 }
4504 
4505 bool
4507  const MoveNode& mn1, const MoveNode& mn2) const {
4508  if (!mn1.isMove() || !mn2.isMove()) {
4509  return false;
4510  }
4511  const TTAProgram::Move& move1 = mn1.move();
4512  const TTAProgram::Move& move2 = mn2.move();
4513 
4514  if (move1.isUnconditional() && move2.isUnconditional()) {
4515  return true;
4516  }
4517 
4518  if (move1.isUnconditional() || move2.isUnconditional()) {
4519  return false;
4520  }
4521  TTAProgram::MoveGuard& mg1 = move1.guard();
4522  TTAProgram::MoveGuard& mg2 = move2.guard();
4523  if (mg1.isInverted() != mg2.isInverted()) {
4524  return false;
4525  }
4526  NodeSet incomingGuards1 =
4527  guardRawPredecessors(mn1);
4528 
4529  NodeSet incomingGuards2 =
4530  guardRawPredecessors(mn2);
4531 
4532  return !incomingGuards1.empty() &&
4533  incomingGuards1 == incomingGuards2;
4534 }
4535 
4536 /**
4537  * Checks whether guards allow bypassing.
4538  *
4539  * @param defNode node defining a value, bypass source.
4540  * @param useNode node using the value, node being bypassed.
4541  * @return true if guards do not prevent bypassing.
4542  */
4544  const MoveNode& defNode, const MoveNode& useNode, bool loopBypass) {
4545 
4546  // can always bypass from unconditional
4547  if (defNode.move().isUnconditional()) {
4548  return true;
4549  }
4550 
4551  // cannot bypass from conditional to unconditional
4552  if (useNode.move().isUnconditional()) {
4553  return false;
4554  }
4555 
4556  NodeSet defGuardDefMoves = guardDefMoves(defNode);
4557  NodeSet useGuardDefMoves = guardDefMoves(useNode);
4558 
4559  // guard value changed between iterations, cannot trust same src!
4560  // could check the backedge property from the guard edges,
4561  // this is suboptimal and safe
4562  if (loopBypass && !defGuardDefMoves.empty()) {
4563  return false;
4564  }
4565 
4566  // if guards defined in different place,
4567  // we do now know if they are equal.
4568  if (defGuardDefMoves != useGuardDefMoves) {
4569  return false;
4570  }
4571 
4572  // if guards are equal, bypass allowed.
4573  return defNode.move().guard().guard().isEqual(
4574  useNode.move().guard().guard());
4575 }
4576 
4577 /**
4578  * Finds (only) node which writes the guard value of a move.
4579  * If none or multiple, return NULL
4580  */
4582  NodeSet guardDefs = guardDefMoves(moveNode);
4583  if (guardDefs.size() != 1) {
4584  return NULL;
4585  }
4586  return *guardDefs.begin();
4587 }
4588 
4589 /**
4590  * Returns true if the node writes a value to a predicate register
4591  * which is used as a guard of a jump.
4592  */
4594  NodeSet succs = successors(moveNode);
4595  for (auto n: succs) {
4596  if (n->move().isJump()) {
4597  if (onlyGuardDefOfMove(*n) == &moveNode) {
4598  return true;
4599  }
4600  }
4601  }
4602  return false;
4603 }
4604 
4605 /**
4606  * Finds the move which writes the loop limit comparison value into
4607  * the loop comparison operation.
4608  *
4609  * If cannot find, returs null.
4610  *
4611  * Assumes positively-gworing loop with ne (or eq + xor 1) as end condition.
4612  * (llvm creates this kind of loops)
4613  *
4614  * @param jumpMove jump move of a loop.
4615  * @return loop limit move or NULL of not found.
4616  */
4617 std::pair<MoveNode*, MoveNode*>
4619 
4620  MoveNode* guardDef = onlyGuardDefOfMove(jumpMove);
4621  if (guardDef == NULL) {
4622  return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
4623  }
4624  while (guardDef->isSourceVariable()) {
4625  guardDef = onlyRegisterRawSource(*guardDef);
4626  if (guardDef == NULL) {
4627  return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
4628  }
4629  }
4630  if (guardDef->isSourceOperation()) {
4631  ProgramOperation* gdpo = &guardDef->sourceOperation();
4632  bool inverted = jumpMove.move().guard().isInverted();
4633 
4634  // machine does not have ne operation so eq + xor used.
4635  if (gdpo->operation().name() == "XOR") {
4636  MoveNodeSet& input1Set = gdpo->inputNode(1);
4637  MoveNodeSet& input2Set = gdpo->inputNode(2);
4638  if (input1Set.count() != 1 || input2Set.count() != 1) {
4639  return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
4640  }
4641  MoveNode& input1 = input1Set.at(0);
4642  MoveNode& input2 = input2Set.at(0);
4643 
4644  MoveNode *regMove = NULL;
4645  if (input1.move().source().isGPR() &&
4646  input2.move().source().isImmediate()) {
4647  regMove = &input1;
4648  }
4649 
4650  if (input2.move().source().isGPR() &&
4651  input1.move().source().isImmediate()) {
4652  regMove = &input2;
4653  }
4654 
4655  // bypassed directly from eq?
4656  if (input1.isSourceOperation() &&
4657  input2.move().source().isImmediate()) {
4658  gdpo = &input1.sourceOperation();
4659  } else {
4660  if (input2.isSourceOperation() &&
4661  input1.move().source().isImmediate()) {
4662  gdpo = &input2.sourceOperation();
4663  } else { // not bypassed.
4664  if (regMove != NULL) {
4665  MoveNode* xorSrc = onlyRegisterRawSource(*regMove);
4666  if (xorSrc != NULL && xorSrc->isSourceOperation()) {
4667  inverted = !inverted;
4668  gdpo = &xorSrc->sourceOperation();
4669  } else {
4670  return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
4671  }
4672  } else {
4673  return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
4674  }
4675  }
4676  }
4677  }
4678 
4679  if ((gdpo->operation().name() == "NE" && !inverted) ||
4680  (gdpo->operation().name() == "EQ" && inverted)) {
4681  MoveNodeSet& input1Set = gdpo->inputNode(1);
4682  MoveNodeSet& input2Set = gdpo->inputNode(2);
4683  if (input1Set.count() != 1 || input2Set.count() != 1) {
4684  return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
4685  }
4686  MoveNode& input1 = input1Set.at(0);
4687  MoveNode& input2 = input2Set.at(0);
4688  if ((input1.move().source().isGPR() ||
4689  input1.isSourceOperation()) &&
4690  input2.move().source().isImmediate()) {
4691  return std::pair<MoveNode*, MoveNode*>(&input2, &input1);
4692  }
4693  if ((input2.move().source().isGPR() ||
4694  input2.isSourceOperation()) &&
4695  input1.move().source().isImmediate()) {
4696  return std::pair<MoveNode*, MoveNode*>(&input1, &input2);
4697  }
4698  }
4699  }
4700  return std::pair<MoveNode*, MoveNode*>(NULL, NULL);
4701 }
4702 
4703 std::pair<MoveNode*, int>
4705  while (indexMove->isSourceVariable()) {
4706  indexMove = onlyRegisterRawSource(*indexMove);
4707  if (indexMove == NULL) {
4708  return std::pair<MoveNode*, int>(NULL,0);
4709  }
4710  }
4711  if (indexMove->isSourceOperation()) {
4712  ProgramOperation* po = &indexMove->sourceOperation();
4713  if (po->operation().name() == "ADD" ||
4714  po->operation().name() == "SUB") {
4715  MoveNodeSet& input1Set = po->inputNode(1);
4716  MoveNodeSet& input2Set = po->inputNode(2);
4717  if (input1Set.count() != 1 || input2Set.count() != 1) {
4718  return std::pair<MoveNode*, int>(NULL,0);
4719  //return NULL;
4720  }
4721  MoveNode& input1 = input1Set.at(0);
4722  MoveNode& input2 = input2Set.at(0);
4723  MoveNode* oldIndex = NULL;
4724  MoveNode* val = NULL;
4725  if (input1.move().source().isGPR() &&
4726  input2.move().source().isImmediate()) {
4727  oldIndex = &input1;
4728  val = &input2;
4729  } else if (input2.move().source().isGPR() &&
4730  input1.move().source().isImmediate()) {
4731  oldIndex = &input2;
4732  val = &input1;
4733  } else {
4734  return std::pair<MoveNode*, int>(NULL,0);
4735  }
4736  while (oldIndex->isSourceVariable()) {
4737  oldIndex = onlyRegisterRawSource(*oldIndex);
4738  if (oldIndex == NULL) {
4739  return std::pair<MoveNode*, int>(NULL,0);
4740  }
4741  }
4742  if (oldIndex->isSourceOperation()) {
4743  if (&oldIndex->sourceOperation() == po) {
4744  int value = (po->operation().name() == "SUB") ?
4745  -val->move().source().value().intValue() :
4746  val->move().source().value().intValue();
4747  return std::pair<MoveNode*, int>(oldIndex, value);
4748  }
4749  }
4750  }
4751  }
4752  return std::pair<MoveNode*, int>(NULL,0);
4753 }
4754 
4756 
4757  DataDependenceEdge* initEdge = NULL;
4758  EdgeSet iEdges = rootGraphInEdges(updateMove);
4759  for (EdgeSet::iterator i=iEdges.begin(); i != iEdges.end(); i++) {
4760  DataDependenceEdge* e = *i;
4763  !e->isBackEdge()) {
4764  if (initEdge != NULL) {
4765  return NULL;
4766  } else {
4767  initEdge = e;
4768  }
4769  }
4770  }
4771  if (initEdge == NULL) {
4772  return NULL;
4773  }
4774  return &rootGraph()->tailNode(*initEdge);
4775 }
4776 
4777 
4778 
4779 /**
4780  * Trigger of an operation may change when scheduling.
4781  * This method updates fu state dependence edges to point to trigger instead of
4782  * some other node of an operation. (they should point to trigger).
4783  */
4784 void
4786  if (!trigger.isDestinationOperation()) {
4787  return;
4788  }
4789  ProgramOperation& po = trigger.destinationOperation();
4790 
4791  // move input edges.
4792  for (int i = 0; i < po.inputMoveCount(); i++) {
4793  MoveNode& node = po.inputMove(i);
4794  if (&node != &trigger) {
4795  EdgeSet iEdges = rootGraphInEdges(node);
4796  for (EdgeSet::iterator i=iEdges.begin(); i != iEdges.end(); i++) {
4797  DataDependenceEdge& e = **i;
4799  moveInEdge(node, trigger, e);
4800  }
4801  }
4802  }
4803  }
4804 
4805  // move output edges.
4806  for (int i = 0; i < po.inputMoveCount(); i++) {
4807  MoveNode& node = po.inputMove(i);
4808  if (&node != &trigger) {
4809  EdgeSet oEdges = rootGraphOutEdges(node);
4810  for (EdgeSet::iterator i=oEdges.begin(); i != oEdges.end(); i++) {
4811  DataDependenceEdge& e = **i;
4813  moveOutEdge(node, trigger, e);
4814  }
4815  }
4816  }
4817  }
4818 }
4819 
4820 /**
4821  * Finds a liverange, consisting of one (or multiple if guarded writes)
4822  * write and one or multiple reads to same registers.
4823  * if none found, returns empty pair.
4824  * @return first set contains writes, second set uses
4825  */
4826 LiveRange*
4828  MoveNode& moveNode, bool dest, bool guard) const {
4829 
4830  NodeSet queuedWrites;
4831  NodeSet queuedReads;
4832  NodeSet queuedGuards;
4833 
4834  typedef EdgeSet::iterator EdgeIterator;
4835 
4836  LiveRange* liveRange = new LiveRange;
4837 
4838  if (dest == true) {
4839  queuedWrites.insert(&moveNode);
4840  } else {
4841  if (guard) {
4842  assert(moveNode.move().isUnconditional());
4843  queuedGuards.insert(&moveNode);
4844  } else {
4845  queuedReads.insert(&moveNode);
4846  }
4847  }
4848 
4849  // loop as long as we have not checked successors of some
4850  // write or predecessors of some read.
4851 
4852  // this is done in double-while-loop. only stop when neither
4853  // loop wants to continue.
4854  while (!queuedWrites.empty() || !queuedReads.empty() ||
4855  !queuedGuards.empty()) {
4856  // first check writes.
4857  while (!queuedWrites.empty()) {
4858  MoveNode& write = **queuedWrites.begin();
4859 
4860  NodeDescriptor nd = descriptor(write);
4861  EdgeSet out = rootGraphOutEdges(write);
4862 
4863  for (EdgeIterator i = out.begin(); i != out.end(); ++i) {
4864  DataDependenceEdge& e = **i;
4865 
4866  // only register raws. pseudo deps not yet supported.
4869  MoveNode& succ =
4870  (static_cast<const DataDependenceGraph*>
4871  (rootGraph()))->headNode(e, nd);
4872 
4873  if (e.isBackEdge() || e.headPseudo() ||
4874  e.tailPseudo() ||
4875  !hasNode(succ)) {
4876  liveRange->clear();
4877  return liveRange;
4878  } else {
4879  if (e.guardUse()) {
4880  // not yet handled. queue it
4881  if (liveRange->guards.find(&succ) ==
4882  liveRange->guards.end()) {
4883  queuedGuards.insert(&succ);
4884  }
4885  } else {
4886  // not yet handled. queue it
4887  if (liveRange->reads.find(&succ) ==
4888  liveRange->reads.end()) {
4889  queuedReads.insert(&succ);
4890  }
4891  }
4892  }
4893  }
4894  }
4895  // this is fully checked. add to result, remove from queue
4896  liveRange->writes.insert(&write);
4897  queuedWrites.erase(&write);
4898  }
4899 
4900  if (!queueRawPredecessors(
4901  queuedReads, liveRange->reads, queuedWrites,
4902  liveRange->writes, false)) {
4903  liveRange->clear();
4904  return liveRange;
4905  }
4906 
4907  if (!queueRawPredecessors(
4908  queuedGuards, liveRange->guards, queuedWrites,
4909  liveRange->writes, true)) {
4910  liveRange->clear();
4911  return liveRange;
4912  }
4913  }
4914  return liveRange;
4915 }
4916 
4917 bool
4919  NodeSet& queue, NodeSet& finalDest, NodeSet& predQueue,
4920  NodeSet& predFinalDest, bool guard) const {
4921 
4922  typedef EdgeSet::iterator EdgeIterator;
4923 
4924  // check one read.
4925  while (!queue.empty()) {
4926  MoveNode& read = **queue.begin();
4927 
4928  NodeDescriptor nd = descriptor(read);
4929  EdgeSet in = rootGraphInEdges(read);
4930 
4931  for (EdgeIterator j = in.begin(); j != in.end(); j++) {
4932  DataDependenceEdge& e = **j;
4933 
4936  e.guardUse() == guard) {
4937  MoveNode& pred =
4938  (static_cast<const DataDependenceGraph*>
4939  (rootGraph()))->tailNode(e, nd);
4940  if (e.isBackEdge() || e.headPseudo() ||
4941  e.tailPseudo() || !hasNode(pred)) {
4942  return false;
4943  } else {
4944  if (predFinalDest.find(&pred) ==
4945  predFinalDest.end()) {
4946  predQueue.insert(&pred);
4947  }
4948  }
4949  }
4950  }
4951  // this is fully checked. add to result, remove from queue
4952  finalDest.insert(&read);
4953  queue.erase(&read);
4954  }
4955  return true;
4956 }
4957 
4958 
4959 /**
4960  * Source of a move is renamed to a register which is not used in
4961  * this ddg. Removes old edges not needed anymore.
4962  *
4963  * If destination of edge also renamed to this reg, keep the edge,
4964  * update the data of the edge.
4965  *
4966  * @param mn MoveNode whose source or guard is renamed.
4967  * @param guard true if renamed gaurd, not source.
4968  */
4971 
4972  UndoData undoData;
4973 
4974  TTAProgram::Terminal& term = mn.move().source();
4975  const TCEString newReg = DisassemblyRegister::registerName(term);
4976 
4977  for (int i = 0; i < outDegree(mn); i++) {
4978  DataDependenceEdge& oEdge = outEdge(mn,i);
4979 
4982  !oEdge.tailPseudo() && !oEdge.guardUse()) {
4983 
4984  MoveNode& head = headNode(oEdge);
4985  TTAProgram::Terminal& writeTerm = head.move().destination();
4986 
4987  // if this edge disappers because of the renaming?
4988  if (oEdge.headPseudo() ||
4989  (writeTerm.isGPR() && (
4990  writeTerm.index() != term.index() ||
4991  &writeTerm.registerFile() != &term.registerFile()))) {
4992  undoData.removedEdges.insert(RemovedEdgeDatum(mn, head, oEdge));
4993  removeEdge(oEdge, NULL, &mn);
4994  i--; // don't skip one edge here!
4995  } else {
4996  // update the edge. also other end changed
4997  undoData.changedDataEdges[&oEdge] = oEdge.data();
4998  oEdge.setData(newReg);
4999  }
5000  }
5001  }
5002  return undoData;
5003 }
5004 
5007 
5008  UndoData undoData;
5009 
5010  assert(!mn.move().isUnconditional());
5011  const TTAMachine::RegisterGuard* rg =
5012  dynamic_cast<const TTAMachine::RegisterGuard*>(
5013  &mn.move().guard().guard());
5014  assert(rg != NULL);
5015  const TCEString newReg = rg->registerFile()->name() +
5016  '.' + Conversion::toString(rg->registerIndex());
5017 
5018  for (int i = 0; i < outDegree(mn); i++) {
5019  DataDependenceEdge& oEdge = outEdge(mn,i);
5020 
5023  !oEdge.tailPseudo() && oEdge.guardUse()) {
5024 
5025  MoveNode& head = headNode(oEdge);
5026  TTAProgram::Terminal& writeTerm = head.move().destination();
5027 
5028  // if this edge disappers because of the renaming?
5029  if (oEdge.headPseudo() ||
5030  (writeTerm.isGPR() && (
5031  writeTerm.index() != rg->registerIndex() ||
5032  &writeTerm.registerFile() != rg->registerFile()))) {
5033  undoData.removedEdges.insert(RemovedEdgeDatum(mn, head, oEdge));
5034  removeEdge(oEdge, NULL, &mn);
5035  i--; // don't skip one edge here!
5036  } else {
5037  // update the edge. also other end changed
5038  undoData.changedDataEdges[&oEdge] = oEdge.data();
5039  oEdge.setData(newReg);
5040  }
5041  }
5042  }
5043  return undoData;
5044 }
5045 
5046 
5047 /**
5048  * Destination of a move is renamed to a register which is not used in
5049  * this ddg. Removes old edges not needed anymore and updates some edges.
5050  * Assumes all the RAW successors of this node are also udpated to read thr
5051  * new register.
5052  */
5053 
5056 
5057  UndoData undoData;
5058  undoData.newEdges = copyDepsOver(mn, true, false);
5059 
5060  TTAProgram::Terminal& term = mn.move().destination();
5061  const TCEString newReg = DisassemblyRegister::registerName(term);
5062 
5063  for (int i = 0 ; i < inDegree(mn); i++) {
5064  DataDependenceEdge& iEdge = inEdge(mn,i);
5065  MoveNode& tail = tailNode(iEdge);
5066 
5067  // WAR's
5070  !iEdge.headPseudo()) {
5071 
5072  TTAProgram::Terminal& writeTerm = tail.move().destination();
5073 
5074  // if this edge disappers because of the renaming?
5075  if (iEdge.tailPseudo() ||
5076  (writeTerm.isGPR() && (
5077  writeTerm.index() != term.index() ||
5078  &writeTerm.registerFile() != &term.registerFile()))) {
5079  undoData.removedEdges.insert(RemovedEdgeDatum(tail, mn, iEdge));
5080  removeEdge(iEdge, NULL, &mn);
5081  i--; // don't skip one edge here!
5082  } else {
5083  // update the edge. also other end changed
5084  undoData.changedDataEdges[&iEdge] = iEdge.data();
5085  iEdge.setData(newReg);
5086  }
5087  }
5088 
5091  !iEdge.headPseudo()) {
5092 
5093  bool removeE = false;
5094  if (iEdge.tailPseudo()) {
5095  removeE = true;
5096  continue;
5097  }
5098 
5099  if (!iEdge.guardUse()) {
5100  TTAProgram::Terminal& readTerm = tail.move().source();
5101  if (readTerm.isGPR() && (
5102  readTerm.index() != term.index() ||
5103  &readTerm.registerFile() != &term.registerFile())) {
5104  removeE = true;
5105  }
5106  }
5107 
5108  if (iEdge.guardUse()) {
5109  if (tail.move().isUnconditional()) {
5110  removeE = true;
5111 /* something is wrong. but ignore it for now
5112  std::cerr << "failing node: " << mn.toString() << std::endl;
5113  std::cerr << "failinf tail: " << tail.toString() << std::endl;
5114  std::cerr << "EDGE: " << iEdge.toString() << std::endl;
5115  writeToDotFile("uncond_gu_war.dot");
5116 */
5117 
5118  } else {
5119  const TTAMachine::RegisterGuard* rg =
5120  dynamic_cast<const TTAMachine::RegisterGuard*>(
5121  &tail.move().guard().guard());
5122  if (rg->registerFile() != &term.registerFile() ||
5123  rg->registerIndex() != term.index()) {
5124  removeE = true;
5125  }
5126  }
5127  }
5128  // if this edge disappers because of the renaming?
5129  if (removeE) {
5130  undoData.removedEdges.insert(RemovedEdgeDatum(tail, mn, iEdge));
5131  removeEdge(iEdge, NULL, &mn);
5132  i--; // don't skip one edge here!
5133  } else {
5134  // update the edge. also other end changed
5135  undoData.changedDataEdges[&iEdge] = iEdge.data();
5136  iEdge.setData(newReg);
5137  }
5138  }
5139  }
5140 
5141  for (int i = 0; i < outDegree(mn); i++) {
5142  DataDependenceEdge& edge = outEdge(mn,i);
5143 
5145  continue;
5146  }
5147 
5149  !edge.tailPseudo()) {
5150  // update the data!
5151  edge.setData(newReg);
5152 
5153  } else {
5155  MoveNode& head = headNode(edge);
5156  TTAProgram::Terminal& writeTerm = head.move().destination();
5157 
5158  // if this edge disappers because of the renaming?
5159  if (edge.tailPseudo()) {
5160  continue;
5161  }
5162  if (edge.headPseudo() ||
5163  (writeTerm.isGPR() && (
5164  writeTerm.index() != term.index() ||
5165  &writeTerm.registerFile() != &term.registerFile()))){
5166  undoData.removedEdges.insert(
5167  RemovedEdgeDatum(mn, head, edge));
5168  removeEdge(edge, &mn, NULL);
5169  i--;
5170  } else {
5171  // update the edge. also other end changed
5172  undoData.changedDataEdges[&edge] = edge.data();
5173  edge.setData(newReg);
5174  }
5175  }
5176  }
5177  }
5178  return undoData;
5179 }
5180 
5181 void
5183  MoveNode& src, MoveNode& dest, MoveNode& antidepPoint,
5184  DataDependenceEdge& connectingEdge,
5185  const TCEString& oldReg, const TCEString& newReg) {
5186 
5187  // if nothing changed, retuen
5188  if (oldReg == newReg) {
5189  return;
5190  }
5191 
5192  // copy antideps over these two nodes
5193  copyDepsOver(src, dest, true, false);
5194 
5195  NodeDescriptor ndADP = descriptor(antidepPoint);
5196  EdgeSet resultInEdges = inEdges(antidepPoint);
5197  EdgeSet firstInEdges = inEdges(src);
5198  EdgeSet firstOutEdges = outEdges(src);
5199  EdgeSet lastOutEdges = outEdges(dest);
5200 
5201  // move antideps coming to adeppoint into src
5202  for (EdgeSet::iterator i = resultInEdges.begin();
5203  i != resultInEdges.end(); i++) {
5204  DataDependenceEdge& e = **i;
5206  !e.headPseudo() &&
5209  assert(e.data() == newReg);
5210  MoveNode& tail = tailNode(e, ndADP);
5211  // do not create loop.
5212  if (e.loopDepth() == 0 && &tail == &src) {
5213  removeEdge(e);
5214  } else {
5215  moveInEdge(antidepPoint, src, e);
5216  }
5217  }
5218  }
5219 
5220  DataDependenceEdge* warEdge = new DataDependenceEdge(
5223  newReg, false, false, false, false, 0);
5224 
5225  DataDependenceEdge* wawEdge = new DataDependenceEdge(
5228  newReg, false, false, false, false, 0);
5229 
5230  connectNodes(src, antidepPoint, *wawEdge);
5231  connectNodes(dest, antidepPoint, *warEdge);
5232 
5233  assert(connectingEdge.data() == oldReg);
5234  connectingEdge.setData(newReg);
5235 
5236  // remove antidep edges that were removed because of this renameing
5237  for (EdgeSet::iterator i = firstInEdges.begin();
5238  i != firstInEdges.end(); i++) {
5239  DataDependenceEdge& e = **i;
5243  removeEdge(e, NULL, &src);
5244  }
5245  }
5246 
5247  for (EdgeSet::iterator i = firstOutEdges.begin();
5248  i != firstOutEdges.end(); i++) {
5249  DataDependenceEdge& e = **i;
5251  !e.tailPseudo() && e.data() == oldReg &&
5254  removeEdge(e, &src, NULL);
5255  }
5256  }
5257  for (EdgeSet::iterator i = lastOutEdges.begin();
5258  i != lastOutEdges.end(); i++) {
5259  DataDependenceEdge& e = **i;
5261  !e.tailPseudo() && e.data() == oldReg &&
5264  removeEdge(e, &src, NULL);
5265  }
5266  }
5267 }
5268 
5269 
5270 
5271 MoveNode*
5273  NodeDescriptor nd = descriptor(mn);
5274  MoveNode* limitingAntidep = NULL;
5275  EdgeSet iEdges = inEdges(mn);
5276  for (EdgeSet::iterator ie = iEdges.begin(); ie != iEdges.end(); ie++) {
5277  DataDependenceEdge& e = **ie;
5278  // TODO: WAW?
5281  !e.headPseudo() && !e.tailPseudo() && !e.guardUse()) {
5282  MoveNode& tail = tailNode(e,nd);
5283  if (tail.isPlaced() && (limitingAntidep == NULL ||
5284  tail.cycle()>limitingAntidep->cycle())){
5285  limitingAntidep = &tail;
5286  }
5287  }
5288  }
5289  return limitingAntidep;
5290 }
5291 
5292 MoveNode*
5294  NodeDescriptor nd = descriptor(mn);
5295  MoveNode* limitingAntidep = NULL;
5296  EdgeSet oEdges = outEdges(mn);
5297  for (EdgeSet::iterator oe = oEdges.begin(); oe != oEdges.end(); oe++) {
5298  DataDependenceEdge& e = **oe;
5299  // TODO: WAW?
5300 
5301 
5304  !e.headPseudo() && !e.tailPseudo() && !e.guardUse()) {
5305  MoveNode& head = headNode(e,nd);
5306  if (head.isPlaced() && (limitingAntidep == NULL ||
5307  head.cycle()<limitingAntidep->cycle())){
5308  limitingAntidep = &head;
5309  }
5310  }
5311  }
5312  return limitingAntidep;
5313 }
5314 
5315 /**
5316  * Copies incoming edges which come from nodes on other BB's to a node
5317  * into another node. If an edge comes from inside same BB, does not copy.
5318  *
5319  * @param source node containing original incoming edges.
5320  * @param nodeCopy node where to copy the inedges to.
5321  */
5322 void
5324  MoveNode& nodeCopy, const MoveNode& source) {
5325  const BasicBlockNode* origBB = &getBasicBlockNode(source);
5326 
5327  EdgeSet edges = inEdges(source);
5328  for (EdgeSet::iterator i = edges.begin(); i != edges.end(); i++) {
5329  Edge& edge = **i;
5330  MoveNode& tail = tailNode(edge);
5331  if (&getBasicBlockNode(tail) != origBB) {
5332  DataDependenceEdge* newEdge = new DataDependenceEdge(edge);
5333  connectNodes(tail, nodeCopy, *newEdge);
5334  }
5335  }
5336 }
5337 
5338 /**
5339  * Copies outgoing edges which goes from a node to nodes in other BB's
5340  * into another node. If an edge goes to a node inside same BB, does not copy.
5341  *
5342  * @param source node containing original outgoingcoming edges.
5343  * @param nodeCopy node where to copy the outedges to.
5344  */
5345 void
5347  MoveNode& nodeCopy, const MoveNode& source) {
5348  const BasicBlockNode* origBB = &getBasicBlockNode(source);
5349 
5350  EdgeSet edges = outEdges(source);
5351  for (EdgeSet::iterator i = edges.begin(); i != edges.end(); i++) {
5352  Edge& edge = **i;
5353  MoveNode& head = headNode(edge);
5354  if (&getBasicBlockNode(head) != origBB) {
5355  DataDependenceEdge* newEdge = new DataDependenceEdge(edge);
5356  connectNodes(nodeCopy, head, *newEdge);
5357  }
5358  }
5359 }
5360 
5361 /**
5362  * Creates dependencies from incoming definitions in other BB's to a reg use.
5363  *
5364  * @param mnd data about the register usage.
5365  */
5366 void
5368  const MoveNodeUse& mnd, const TCEString& reg, TTAProgram::BasicBlock& bb) {
5369 
5370  // create RAW's from definitions in previous BBs.
5371  std::set<MoveNodeUse>& defReaches =
5372  bb.liveRangeData_->regDefReaches_[reg];
5373  for (std::set<MoveNodeUse>::iterator i = defReaches.begin();
5374  i != defReaches.end(); i++) {
5375 
5376  const MoveNodeUse& source = *i;
5377  if (hasNode(*source.mn())) {
5378  DataDependenceEdge* dde =
5379  // create dependency edge
5380  new DataDependenceEdge(
5383  DataDependenceEdge::DEP_RAW, reg, mnd.guard(), false,
5384  source.pseudo(), mnd.pseudo(), source.loop());
5385 
5386  // and connect.
5387  connectOrDeleteEdge(*source.mn(), *mnd.mn(), dde);
5388  }
5389  }
5390 }
5391 
5392 /**
5393  * Creates dependencies to a register write from MN's in other BBs.
5394  *
5395  * @param mnd movenode which writes to a register
5396  * @param reg register wrere the movenode writes to
5397  * @param createAllAntideps whether to create antideps from all BB's
5398  * or just from same bb in case of single-bb loop.
5399  */
5402  const MoveNodeUse& mnd, const TCEString& reg, TTAProgram::BasicBlock& bb) {
5403  // WaWs
5404 
5405  DataDependenceGraph::EdgeSet addedEdges;
5406 
5407  std::set<MoveNodeUse>& defReaches =
5408  bb.liveRangeData_->regDefReaches_[reg];
5409  for (std::set<MoveNodeUse>::iterator i = defReaches.begin();
5410  i != defReaches.end(); i++) {
5411 
5412  const MoveNodeUse& source = *i;
5413  if (hasNode(*source.mn()) && source.mn()->isMove() &&
5415  &getBasicBlockNode(*source.mn()) ==
5416  &getBasicBlockNode(*mnd.mn()))) {
5417  // create dependency edge
5418  DataDependenceEdge* dde =
5419  new DataDependenceEdge(
5422  DataDependenceEdge::DEP_WAW, reg, false, false,
5423  source.pseudo(), mnd.pseudo(), source.loop());
5424  // and connect.
5425  if (connectOrDeleteEdge(*source.mn(), *mnd.mn(), dde)) {
5426  addedEdges.insert(dde);
5427  }
5428  }
5429  }
5430 
5431  // WaRs
5432  std::set<MoveNodeUse>& useReaches =
5433  bb.liveRangeData_->regUseReaches_[reg];
5434  for (std::set<MoveNodeUse>::iterator i = useReaches.begin();
5435  i != useReaches.end(); i++) {
5436 
5437  const MoveNodeUse& source = *i;
5438  if (hasNode(*source.mn()) && source.mn()->isMove() &&
5440  &getBasicBlockNode(*source.mn()) ==
5441  &getBasicBlockNode(*mnd.mn()))) {
5442  // create dependency edge
5443  DataDependenceEdge* dde =
5444  new DataDependenceEdge(
5447  DataDependenceEdge::DEP_WAR, reg, source.guard(), false,
5448  source.pseudo(), mnd.pseudo(), source.loop());
5449  // and connect.
5450  if (connectOrDeleteEdge(*source.mn(), *mnd.mn(), dde)) {
5451  addedEdges.insert(dde);
5452  }
5453  }
5454  }
5455  return addedEdges;
5456 }
5457 
5458 /**
5459  * Removes guard raw edges coming to some node.
5460  *
5461  * This is called if the guard is removed from the node.
5462  *
5463  * @param node The node.
5464  */
5465 void
5468  std::pair<InEdgeIter, InEdgeIter> edges =
5469  boost::in_edges(nd, graph_);
5470 
5471  // loop thru all edges
5472  for (InEdgeIter ei = edges.first; ei != edges.second; ) {
5473  EdgeDescriptor ed = *ei;
5474  DataDependenceEdge& edge = *graph_[ed];
5475  if (edge.guardUse() && edge.dependenceType() ==
5477  boost::remove_edge(*ei, graph_);
5478 
5479  // removing messes up the iterator. start again from first.
5480  edges = boost::in_edges(nd, graph_);
5481  ei = edges.first;
5482  } else {
5483  ei++;
5484  }
5485  }
5486 }
5487 
5488 /**
5489  * Removes guard raw edges coming to some node.
5490  *
5491  * This is called if the guard is removed from the node.
5492  *
5493  * @param node The node.
5494  */
5495 void
5498  std::pair<OutEdgeIter, OutEdgeIter> edges =
5499  boost::out_edges(nd, graph_);
5500 
5501  // loop thru all edges
5502  for (OutEdgeIter ei = edges.first; ei != edges.second; ) {
5503  EdgeDescriptor ed = *ei;
5504  DataDependenceEdge& edge = *graph_[ed];
5505  if (edge.guardUse() && edge.dependenceType() ==
5507  boost::remove_edge(*ei, graph_);
5508 
5509  // removing messes up the iterator. start again from first.
5510  edges = boost::out_edges(nd, graph_);
5511  ei = edges.first;
5512  } else {
5513  ei++;
5514  }
5515  }
5516 }
5517 
5519  const MoveNodeUse& mnu, std::set<MoveNodeUse> targets) const {
5520  NodeDescriptor nd = descriptor(*mnu.mn());
5521 
5522  std::pair<OutEdgeIter, OutEdgeIter> edges =
5523  boost::out_edges(nd, graph_);
5524 
5525  // loop thru all edges
5526  for (OutEdgeIter ei = edges.first; ei != edges.second; ei++ ) {
5527  EdgeDescriptor ed = *ei;
5528  DataDependenceEdge& edge = *graph_[ed];
5531  !edge.isBackEdge()) {
5532 
5533  MoveNode* target = graph_[boost::target(ed, graph_)];
5534  if (AssocTools::containsKey(targets, MoveNodeUse(*target))) {
5535  return true;
5536  }
5537  }
5538  }
5539  return false;
5540 }
5541 
5542 /**
5543  * Returns true in case the given dependency cannot be (currently) avoided by
5544  * techniques such as register renaming or speculation.
5545  *
5546  * If the edge is "avoidable", it doesn't meen it always is. E.g., sometimes
5547  * the register renamer can find a better register to remove the dependency,
5548  * sometimes it cannot. That is, this method returns true only if it's *certain*
5549  * we cannot do anything about the dependency with the current compiler backend
5550  * or by, e.g., adding more registers to the machine.
5551  */
5552 bool
5554 
5555  if (!edge.isFalseDep()) return true;
5556  MoveNode& tail = tailNode(edge);
5557  MoveNode& head = headNode(edge);
5558 
5559  /* The control dependency caused antidep case. In case the antidep
5560  overwrites the register with a different predicate than the other,
5561  it is not possible to simply rename the other register, but, e.g.,
5562  speculative execution has to be added with a final write to the
5563  original register.
5564 
5565  Example:
5566 
5567  a) p1: foo -> r1
5568  b) p1: r1 -> X
5569  c) p2: foo -> r1
5570  d) p2 r1 -> Y jne
5571  e) r1 -> foo
5572 
5573  In case p2 = !p1 then we can parallelize freely. In case
5574  p2 = p1 then we can parallelize after a reg rename of r1.
5575  Otherwise, speculative or similar transformation has to be
5576  done, which currently is not supported by tcecc.
5577  */
5579  (!tail.move().isUnconditional() && !head.move().isUnconditional()) &&
5580  !(tail.move().guard().guard().isEqual(head.move().guard().guard()) ||
5581  tail.move().guard().guard().isOpposite(head.move().guard().guard())))
5582  return true;
5583 
5585  ((tail.move().isUnconditional() && !head.move().isUnconditional()) ||
5586  (!tail.move().isUnconditional() && head.move().isUnconditional())))
5587  return true;
5588 
5589 
5590  return false;
5591 }
5592 
5593 bool
5595 
5597  for (DataDependenceGraph::NodeSet::iterator i = pred.begin();
5598  i != pred.end(); ++i) {
5599  if (!(**i).isPlaced()) {
5600  return true;
5601  }
5602  }
5603  return false;
5604 }
5605 
5606 bool
5608 
5610  for (DataDependenceGraph::NodeSet::iterator i = succ.begin();
5611  i != succ.end(); ++i) {
5612  if (!(**i).isPlaced()) {
5613  return true;
5614  }
5615  }
5616  return false;
5617 }
5618 
5621 
5622  NodeSet potentialSiblings;
5623  NodeSet siblings;
5624  NodeSet regDepSources;
5625 
5626  EdgeSet ins = inEdges(mn);
5627  int edgeCounter = 0;
5628  for (auto e: ins) {
5629  if ((e->edgeReason() != DataDependenceEdge::EDGE_REGISTER &&
5630  e->edgeReason() != DataDependenceEdge::EDGE_RA) ||
5631  e->headPseudo() || e->tailPseudo() || e->guardUse()) {
5632  continue;
5633  }
5634  edgeCounter++;
5635 
5636  MoveNode& tail = tailNode(*e);
5637  regDepSources.insert(&tail);
5638  const EdgeSet& outs = outEdges(tail);
5639  for (auto f: outs) {
5640  if ((f->edgeReason() != DataDependenceEdge::EDGE_REGISTER &&
5641  f->edgeReason() != DataDependenceEdge::EDGE_RA) ||
5642  f->headPseudo() || f->tailPseudo() || f->guardUse()) {
5643  continue;
5644  }
5645  if (e != f && *e == *f) {
5646  MoveNode& head = headNode(*f);
5647  if (&head != &mn) {
5648  potentialSiblings.insert(&head);
5649  }
5650  }
5651  }
5652  }
5653 
5654  for (auto n : potentialSiblings) {
5655  bool ok = true;
5656  EdgeSet ins2 = inEdges(*n);
5657  int edgeCounter2 = 0;
5658  for (auto e: ins2) {
5659  if ((e->edgeReason() != DataDependenceEdge::EDGE_REGISTER &&
5660  e->edgeReason() != DataDependenceEdge::EDGE_RA) ||
5661  e->headPseudo() || e->tailPseudo() || e->guardUse()) {
5662  continue;
5663  }
5664 
5665  bool foundSame = false;
5666  const MoveNode& tail = tailNode(*e);
5667  for (auto f : ins) {
5668  if (*e == *f && &tailNode(*f) == &tail) {
5669  foundSame = true;
5670  break;
5671  }
5672  }
5673 
5674  // did not find similar edge from the inputs of the original node
5675  if (!foundSame) {
5676  ok = false;
5677  break;
5678  }
5679  edgeCounter2++;
5680  }
5681  if (ok && edgeCounter2 == edgeCounter) {
5682  siblings.insert(n);
5683  }
5684  }
5685  return siblings;
5686 }
5687 
5689  EdgeSet iEdges = inEdges(mn);
5690  for (EdgeSet::iterator i = iEdges.begin(); i != iEdges.end(); i++) {
5691  DataDependenceEdge& e = **i;
5694  !e.guardUse()) {
5695  return false;
5696  }
5697  }
5698  return true;
5699 }
5700 
5702  EdgeSet iEdges = inEdges(mn);
5703  for (auto e: iEdges) {
5704  if (e->edgeReason() != DataDependenceEdge::EDGE_REGISTER ||
5705  e->dependenceType() != DataDependenceEdge::DEP_WAW) {
5706  continue;
5707  }
5708  MoveNode& tail = tailNode(*e);
5709  if (&tail != &mn) {
5710  return true;
5711  }
5712  }
5713  return false;
5714 }
5715 
5717  if (edgeWeightHeuristics_ != ewh) {
5718  // force path recalculation
5719  height_ = -1;
5720  sourceDistances_.clear();
5721  sinkDistances_.clear();
5722  // nullify edge weights to recalc them
5723  typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
5724  EdgeIterPair edges = boost::edges(graph_);
5725  for (EdgeIter i = edges.first; i != edges.second; i++) {
5726  GraphEdge* e = graph_[*i];
5727  e->setWeight(-1);
5728  }
5729  }
5730  edgeWeightHeuristics_ = ewh;
5731 }
5732 
5733 MoveNode*
5735 
5737  DataDependenceGraph::EdgeSet::iterator edgeIter = edges.begin();
5738  DataDependenceEdge* bypassEdge = NULL;
5739 
5740  // find one incoming raw edge. if multiple, cannot bypass.
5741  while (edgeIter != edges.end()) {
5742 
5743  DataDependenceEdge& edge = *(*edgeIter);
5744  // if the edge is not a real reg/ra raw edge, skip to next edge
5747  edge.guardUse() || edge.headPseudo()) {
5748  edgeIter++;
5749  continue;
5750  }
5751 
5752  if (bypassEdge == NULL) {
5753  bypassEdge = &edge;
5754  } else {
5755  // cannot bypass if multiple inputs
5756  return 0;
5757  }
5758  edgeIter++;
5759  }
5760 
5761  // if no bypassable edge found, cannot bypass
5762  if (bypassEdge == NULL || bypassEdge->isBackEdge()) {
5763  return 0;
5764  }
5765 
5766  MoveNode& source = tailNode(*bypassEdge);
5767  return &source;
5768 }
5769 
5771 
5772  // performance optimization
5773  NodeDescriptor nd = descriptor(src);
5774 
5775  // use the internal data structures to make this fast.
5776  // edgeset has too much set overhead,
5777  // inedge(n,i) is O(n^2) , this is linear with no overhead
5778  std::pair<InEdgeIter, InEdgeIter> iEdges =
5779  boost::in_edges(nd, graph_);
5780 
5781  for (InEdgeIter ii = iEdges.first; ii != iEdges.second; ii++) {
5782  EdgeDescriptor ed = *ii;
5787  !edge->guardUse()) {
5788  DataDependenceEdge* newEdge = new DataDependenceEdge(*edge);
5789  MoveNode& tail = *graph_[boost::source(ed, graph_)];
5790  connectNodes(tail, dst, *newEdge);
5791  }
5792  }
5793 }
5794 
5796  // similar than mergeAndKeepDestination
5797  ProgramOperationPtr srcPO = guardSrc.sourceOperationPtr();
5798  srcPO->addGuardOutputNode(dst);
5799  dst.setGuardOperationPtr(srcPO);
5800 
5801  TCEString regName = removeRAWEdges(guardSrc, dst);
5802 
5803  for (int i = 0; i < rootGraphInDegree(guardSrc); i++) {
5804  DataDependenceEdge& edge = rootGraphInEdge(guardSrc ,i);
5805  // skip antidependencies due bypassed register.. these are no more
5807  edge.data() == regName) {
5810  continue;
5811  }
5812  }
5813  assert(!edge.guardUse());
5815  std::cerr << "Warning: non-operation edge: " << edge.toString()
5816  << " on guard bypass" << std::endl;
5817  continue;
5818  }
5819 
5820  // copy other edges. (operation inputs)
5821  MoveNode& source = rootGraph()->tailNode(edge);
5822  DataDependenceEdge* newEdge =
5823  new DataDependenceEdge(
5826 
5827  rootGraph()->connectNodes(source, dst, *newEdge);
5828  }
5829 
5830 
5831  // remove WAR antideps out from this
5832  for (int i = 0; i < rootGraphOutDegree(dst); i++) {
5834 
5835  // create new WaW in place of old WaR
5838  edge.data() == regName && edge.guardUse()) {
5839 
5840  // and remove the old WaR
5841  (static_cast<DataDependenceGraph*>(rootGraph()))->
5842  removeEdge(edge, &dst, NULL);
5843  i--; // don't skip one edge here!
5844  }
5845  }
5846 }
5847 
5848 
5850  // similar than mergeAndKeepDestination
5851  ProgramOperation& srcPO = guardSrc.sourceOperation();
5852  srcPO.removeGuardOutputNode(dst);
5853  dst.unsetGuardOperation();
5854 
5855  // remove the incoming guard operation edges.
5856  for (int i = 0; i < inDegree(dst); i++) {
5857  DataDependenceEdge& edge = inEdge(dst,i);
5858  if (edge.guardUse() &&
5860  removeEdge(edge, &dst, NULL);
5861  i--;
5862  }
5863  }
5864 
5865  // name of the bypass reg.
5866  TTAProgram::Terminal& dest = guardSrc.move().destination();
5867  assert(dest.isGPR());
5869 
5870  // create register edge between nodes.
5871  // this was removed by the merge.
5874  DataDependenceEdge::DEP_RAW, regName,
5875  true, false, false, false);
5876  connectNodes(guardSrc, dst, *dde);
5877 
5878  // TODO: restore the guard antidep edges.
5879 
5880  // All all outgoing WAR's to merged node. The war's go to
5881  // all same places where WAW's fo from source node.
5882  for (int i = 0; i < outDegree(guardSrc); i++) {
5883  DataDependenceEdge& edge = outEdge(guardSrc,i);
5886  edge.data() == regName) {
5887  MoveNode& head = headNode(edge);
5888  // skip nodes with exclusive guard.
5889  DataDependenceEdge* newEdge = new DataDependenceEdge(
5891  DataDependenceEdge::DEP_WAR, regName, true, false,
5892  false, edge.headPseudo(), edge.loopDepth());
5893  connectNodes(dst, head, *newEdge);
5894  }
5895  }
5896 }
5897 
5899  for (auto i : undoData.changedDataEdges) {
5900  i.first->setData(i.second);
5901  }
5902 
5903  for (auto i: undoData.removedEdges) {
5904  connectNodes(i.nTail, i.nHead, i.edge);
5905  }
5906 
5907  for (auto i: undoData.newEdges) {
5908  removeEdge(*i);
5909  }
5910 }
5911 
5914  std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
5915  descriptor(node), graph_);
5916 
5917  EdgeSet result;
5918 
5919  for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
5920  DataDependenceEdge* edge = graph_[(*ei)];
5922  edgeDescriptors_[edge] = *ei;
5923  result.insert(edge);
5924  }
5925  }
5926  return result;
5927 }
5928 
5931  std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
5932  descriptor(node), graph_);
5933 
5934  EdgeSet result;
5935 
5936  for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
5937  DataDependenceEdge* edge = graph_[(*ei)];
5938  if (edge->isRegisterOrRA()) {
5939  edgeDescriptors_[edge] = *ei;
5940  result.insert(edge);
5941  }
5942  }
5943  return result;
5944 }
DataDependenceGraph::registerAndRAInEdges
EdgeSet registerAndRAInEdges(const MoveNode &node) const
Definition: DataDependenceGraph.cc:5930
TTAMachine::Guard
Definition: Guard.hh:55
ProgramOperation::operation
const Operation & operation() const
Definition: ProgramOperation.cc:590
DataDependenceGraph::predecessorsReady
bool predecessorsReady(MoveNode &node) const
Definition: DataDependenceGraph.cc:3176
TTAProgram::Terminal::isFUPort
virtual bool isFUPort() const
Definition: Terminal.cc:118
BoostGraph< MoveNode, DataDependenceEdge >::loopingSinkDistances_
std::map< const MoveNode *, int, typename MoveNode ::Comparator > loopingSinkDistances_
Definition: BoostGraph.hh:326
DataDependenceGraph::lastScheduledRegisterRead
MoveNode * lastScheduledRegisterRead(const TTAMachine::BaseRegisterFile &rf, int registerIndex, int lastCycleToTest=INT_MAX) const
Definition: DataDependenceGraph.cc:766
SimValue::intValue
int intValue() const
Definition: SimValue.cc:895
BoostGraph< MoveNode, DataDependenceEdge >::predecessors
virtual NodeSet predecessors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
DataDependenceGraph::onlyRegisterRawDestinationsWithEdges
std::map< DataDependenceEdge *, MoveNode *, DataDependenceEdge::Comparator > onlyRegisterRawDestinationsWithEdges(const MoveNode &mn, bool allowBackEdges) const
Definition: DataDependenceGraph.cc:4124
MachineAnalysis::bypassability
float bypassability() const
Definition: MachineAnalysis.hh:45
DataDependenceGraph::isLoopBypass
bool isLoopBypass(MoveNode &sourceNode, MoveNode &userNode)
Definition: DataDependenceGraph.cc:1916
BoostGraph< MoveNode, DataDependenceEdge >::connectNodes
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
BoostGraph< MoveNode, DataDependenceEdge >::outEdge
virtual Edge & outEdge(const Node &node, const int index) const
Operation::writesMemory
virtual bool writesMemory() const
Definition: Operation.cc:252
TTAProgram::Move::isTriggering
bool isTriggering() const
Definition: Move.cc:284
DataDependenceGraph::removeIncomingGuardEdges
void removeIncomingGuardEdges(MoveNode &node)
Definition: DataDependenceGraph.cc:5466
MoveNode::dotString
std::string dotString() const
Definition: MoveNode.cc:602
DataDependenceGraph::firstRegisterCycle
int firstRegisterCycle(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:981
DataDependenceGraph::lastScheduledRegisterWrites
NodeSet lastScheduledRegisterWrites(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1206
DataDependenceGraph::dotProgramOperationNodes_
bool dotProgramOperationNodes_
The moves belonging to the same program operation are merged to a single node. Reduces the complexity...
Definition: DataDependenceGraph.hh:445
TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_SRC
@ ANN_REJECTED_UNIT_SRC
Src. unit rejected.
Definition: ProgramAnnotation.hh:118
BoostGraph< MoveNode, DataDependenceEdge >::removeEdge
virtual void removeEdge(Edge &e)
DataDependenceGraph::regRawSuccessors
NodeSet regRawSuccessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4272
DataDependenceGraph::delaySlots_
int delaySlots_
Definition: DataDependenceGraph.hh:449
DataDependenceGraph::machine
const TTAMachine::Machine & machine() const
Definition: DataDependenceGraph.hh:260
MoveNodeUse::mn
const MoveNode * mn() const
Definition: MoveNodeUse.hh:39
BoostGraph< MoveNode, DataDependenceEdge >::sourceDistances_
std::map< const MoveNode *, int, typename MoveNode ::Comparator > sourceDistances_
Definition: BoostGraph.hh:318
BoostGraph< MoveNode, DataDependenceEdge >::tailNode
virtual Node & tailNode(const Edge &edge) const
ProgramOperation::removeInputNode
void removeInputNode(MoveNode &node)
Definition: ProgramOperation.cc:289
TTAMachine::Component::name
virtual TCEString name() const
Definition: MachinePart.cc:125
DataDependenceGraph::scheduledNodeCount
int scheduledNodeCount() const
Definition: DataDependenceGraph.cc:1859
DataDependenceGraph::programOperation
ProgramOperation & programOperation(int index)
Definition: DataDependenceGraph.cc:227
MoveNode::toString
std::string toString() const
Definition: MoveNode.cc:576
DataDependenceGraph::edgeLatency
int edgeLatency(const DataDependenceEdge &edge, int ii, const MoveNode *tail, const MoveNode *head) const
Definition: DataDependenceGraph.cc:311
TTAProgram::Instruction::move
Move & move(int i) const
Definition: Instruction.cc:193
TTAProgram::Terminal::index
virtual int index() const
Definition: Terminal.cc:274
BoostGraph< MoveNode, DataDependenceEdge >::hasEdge
virtual bool hasEdge(const Node &nTail, const Node &nHead) const
DataDependenceGraph::firstScheduledRegisterWrite
MoveNode * firstScheduledRegisterWrite(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:847
machine
TTAMachine::Machine * machine
the architecture definition of the estimated processor
Definition: EstimatorCmdLineUI.cc:59
DataDependenceGraph::renamedSimpleLiveRange
void renamedSimpleLiveRange(MoveNode &src, MoveNode &dest, MoveNode &antidepPoint, DataDependenceEdge &lrEdge, const TCEString &oldReg, const TCEString &newReg)
Definition: DataDependenceGraph.cc:5182
BoostGraph< MoveNode, DataDependenceEdge >::headNode
virtual Node & headNode(const Edge &edge) const
DataDependenceGraph::registerAntidependenceLevel_
AntidependenceLevel registerAntidependenceLevel_
Definition: DataDependenceGraph.hh:455
TTAMachine::HWOperation
Definition: HWOperation.hh:52
DataDependenceEdge::DEP_TRIGGER
@ DEP_TRIGGER
Definition: DataDependenceEdge.hh:50
TTAProgram::Move::isFunctionCall
bool isFunctionCall() const
Definition: Move.cc:219
BoostGraph< MoveNode, DataDependenceEdge >::node
Node & node(const int index) const
DataDependenceGraph::edgeWeight
int edgeWeight(DataDependenceEdge &e, const MoveNode &hNode) const
Definition: DataDependenceGraph.cc:2910
DataDependenceGraph::fixInterBBAntiEdges
void fixInterBBAntiEdges(BasicBlockNode &bbn1, BasicBlockNode &bbn2, bool loopEdges)
Definition: DataDependenceGraph.cc:3689
DataDependenceEdge::isBackEdge
bool isBackEdge() const
Definition: DataDependenceEdge.hh:118
TTAMachine::RegisterGuard::registerIndex
int registerIndex() const
BoostGraph< MoveNode, DataDependenceEdge >::hasPath
bool hasPath(MoveNode &src, const MoveNode &dest) const
BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInDegree
virtual int rootGraphInDegree(const Node &node) const
DataDependenceGraph::resultUsed
bool resultUsed(MoveNode &resultNode)
Definition: DataDependenceGraph.cc:2348
DataDependenceGraph::setBasicBlockNode
void setBasicBlockNode(const MoveNode &mn, BasicBlockNode &bbn)
Definition: DataDependenceGraph.cc:216
BoostGraph< MoveNode, DataDependenceEdge >::moveInEdges
virtual void moveInEdges(const Node &source, const Node &destination)
TTAProgram::Terminal::registerFile
virtual const TTAMachine::RegisterFile & registerFile() const
Definition: Terminal.cc:225
DataDependenceGraph::copyIncomingRawEdges
void copyIncomingRawEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:5770
MoveNode::isDestinationOperation
bool isDestinationOperation() const
TTAProgram::MoveGuard::isInverted
bool isInverted() const
Definition: MoveGuard.cc:76
DataDependenceGraph::findLimitingAntidependenceSource
MoveNode * findLimitingAntidependenceSource(MoveNode &mn)
Definition: DataDependenceGraph.cc:5272
DataDependenceGraph::sameGuards
bool sameGuards(const MoveNode &mn1, const MoveNode &mn2) const
Definition: DataDependenceGraph.cc:4506
DataDependenceGraph::findLoopLimitAndIndex
std::pair< MoveNode *, MoveNode * > findLoopLimitAndIndex(MoveNode &jumpMove)
Definition: DataDependenceGraph.cc:4618
AssocTools::containsKey
static bool containsKey(const ContainerType &aContainer, const KeyType &aKey)
BoostGraph< MoveNode, DataDependenceEdge >::NodeSet
std::set< MoveNode *, typename MoveNode ::Comparator > NodeSet
Definition: BoostGraph.hh:86
TTAProgram::Instruction
Definition: Instruction.hh:57
TTAProgram::Move::isUnconditional
bool isUnconditional() const
Definition: Move.cc:154
TTAProgram::Move::sourceLineNumber
int sourceLineNumber() const
Definition: Move.cc:459
MoveNodeUse::pseudo
bool pseudo() const
Definition: MoveNodeUse.hh:42
DataDependenceGraph::rWawRawEdgesOutUncond
bool rWawRawEdgesOutUncond(MoveNode &mn)
Definition: DataDependenceGraph.cc:3978
MoveNodeUse
Definition: MoveNodeUse.hh:20
TTAMachine::Guard::isEqual
virtual bool isEqual(const Guard &guard) const =0
MachineAnalysis
Definition: MachineAnalysis.hh:40
LiveRangeData::regUseReaches_
MoveNodeUseMapSet regUseReaches_
Definition: LiveRangeData.hh:91
DataDependenceGraph::addProgramOperation
void addProgramOperation(ProgramOperationPtr po)
Definition: DataDependenceGraph.cc:298
BasicBlockNode.hh
DataDependenceGraph::onlyRegisterRawAncestor
const MoveNode * onlyRegisterRawAncestor(const MoveNode &node, const std::string &sp) const
Definition: DataDependenceGraph.cc:4203
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
DataDependenceGraph::guardRenamed
DataDependenceGraph::UndoData guardRenamed(MoveNode &mn)
Definition: DataDependenceGraph.cc:5006
DataDependenceGraph::~DataDependenceGraph
virtual ~DataDependenceGraph()
Definition: DataDependenceGraph.cc:95
DataDependenceGraph::scheduledMoves
NodeSet scheduledMoves() const
Definition: DataDependenceGraph.cc:1375
BoostGraph::copyInEdge
virtual void copyInEdge(const Node &destination, Edge &edge, const Node *tail=NULL)
DataDependenceGraph::lastScheduledRegisterGuardReads
NodeSet lastScheduledRegisterGuardReads(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1163
TTAProgram::Terminal::hintOperation
virtual Operation & hintOperation() const
Definition: Terminal.cc:341
GraphNode::nodeID
int nodeID() const
DataDependenceEdge::setData
void setData(const TCEString &newData)
Definition: DataDependenceEdge.cc:331
UniversalMachine::instance
static UniversalMachine & instance()
Definition: UniversalMachine.cc:73
DataDependenceEdge::isFalseDep
bool isFalseDep() const
Definition: DataDependenceEdge.hh:95
MoveNode::clearDestinationOperation
void clearDestinationOperation()
Definition: MoveNode.cc:730
TTAProgram::Move::bus
const TTAMachine::Bus & bus() const
Definition: Move.cc:373
DataDependenceGraph::createRegisterAntiDependenciesBetweenNodes
void createRegisterAntiDependenciesBetweenNodes(NodeSet &nodes)
Definition: DataDependenceGraph.cc:4381
ObjectState
Definition: ObjectState.hh:59
MoveNode::isSourceReg
bool isSourceReg(const std::string &reg) const
Definition: MoveNode.cc:798
DataDependenceGraph.hh
ProgramOperation
Definition: ProgramOperation.hh:70
DataDependenceGraph::setMachine
void setMachine(const TTAMachine::Machine &machine)
Definition: DataDependenceGraph.cc:3116
MoveNode
Definition: MoveNode.hh:65
DataDependenceGraph::regRawPredecessors
NodeSet regRawPredecessors(const MoveNode &node, int backedges=0) const
Definition: DataDependenceGraph.cc:4310
DataDependenceGraph::findLiveRange
LiveRange * findLiveRange(MoveNode &lrNode, bool writingNode, bool guardUseNode) const
Definition: DataDependenceGraph.cc:4827
ImmediateUnit.hh
DataDependenceGraph::rrCost_
int rrCost_
Definition: DataDependenceGraph.hh:451
DataDependenceGraph::nodesOfMoves_
std::map< const TTAProgram::Move *, MoveNode * > nodesOfMoves_
Definition: DataDependenceGraph.hh:434
DataDependenceGraph::rWarEdgesOut
int rWarEdgesOut(MoveNode &mn)
Definition: DataDependenceGraph.cc:3930
BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdge
virtual Edge & rootGraphOutEdge(const Node &node, const int index) const
BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutDegree
virtual int rootGraphOutDegree(const Node &node) const
Terminal.hh
DataDependenceEdge::EDGE_REGISTER
@ EDGE_REGISTER
Definition: DataDependenceEdge.hh:53
BoostGraph::addNode
virtual void addNode(Node &node)
TTAMachine::Machine::triggerInvalidatesResults
bool triggerInvalidatesResults() const
Definition: Machine.cc:964
TTAMachine::Machine::Navigator::count
int count() const
DataDependenceGraph::sanityCheck
void sanityCheck() const
Definition: DataDependenceGraph.cc:1399
BoostGraph< MoveNode, DataDependenceEdge >::edgeCount
int edgeCount() const
DataDependenceGraph::EdgeWeightHeuristics
EdgeWeightHeuristics
Definition: DataDependenceGraph.hh:90
BoostGraph< MoveNode, DataDependenceEdge >::loopingSourceDistances_
std::map< const MoveNode *, int, typename MoveNode ::Comparator > loopingSourceDistances_
Definition: BoostGraph.hh:324
BoostGraph< MoveNode, DataDependenceEdge >::moveOutEdge
virtual void moveOutEdge(const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false)
Operation::name
virtual TCEString name() const
Definition: Operation.cc:93
DataDependenceEdge::dependenceType
DependenceType dependenceType() const
Definition: DataDependenceEdge.hh:88
LiveRangeData::regDefReaches_
MoveNodeUseMapSet regDefReaches_
Definition: LiveRangeData.hh:90
BoostGraph< MoveNode, DataDependenceEdge >::sinkDistances_
std::map< const MoveNode *, int, typename MoveNode ::Comparator > sinkDistances_
Definition: BoostGraph.hh:320
DataDependenceGraph::onlyRegisterRawSource
MoveNode * onlyRegisterRawSource(const MoveNode &mn, int allowGuardEdges=2, int backEdges=0) const
Definition: DataDependenceGraph.cc:4083
Conversion::toString
static std::string toString(const T &source)
DataDependenceEdge::tailPseudo
bool tailPseudo() const
Definition: DataDependenceEdge.hh:109
DataDependenceEdge.hh
MoveNode::isSourceRA
bool isSourceRA() const
Definition: MoveNode.cc:210
ProgramOperation::triggeringMove
MoveNode * triggeringMove() const
Definition: ProgramOperation.cc:643
DataDependenceGraph::moveFUDependenciesToTrigger
void moveFUDependenciesToTrigger(MoveNode &trigger)
Definition: DataDependenceGraph.cc:4785
DataDependenceGraph::lastScheduledRegisterKill
MoveNode * lastScheduledRegisterKill(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1285
DataDependenceGraph::guardDefMoves
NodeSet guardDefMoves(const MoveNode &moveNode)
Definition: DataDependenceGraph.cc:743
MoveNodeUse::loop
bool loop() const
Definition: MoveNodeUse.hh:43
BoostGraph< MoveNode, DataDependenceEdge >::edgeDescriptors_
EdgeDescMap edgeDescriptors_
Definition: BoostGraph.hh:340
DataDependenceGraph::EWH_HEURISTIC
@ EWH_HEURISTIC
Weights memory dependencies more, etc.
Definition: DataDependenceGraph.hh:91
DataDependenceGraph::guardRawPredecessors
NodeSet guardRawPredecessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4048
ProgramOperationPtr
std::shared_ptr< ProgramOperation > ProgramOperationPtr
Definition: MoveNode.hh:52
DataDependenceGraph::onlyRegisterRawDestinations
NodeSet onlyRegisterRawDestinations(const MoveNode &mn, bool allowGuardEdges=false, bool allowBackEdges=false) const
Definition: DataDependenceGraph.cc:4163
BoostGraph< MoveNode, DataDependenceEdge >::outDegree
virtual int outDegree(const Node &node) const
DataDependenceGraph::mergeAndKeepUser
bool mergeAndKeepUser(MoveNode &resultNode, MoveNode &userNode, bool force=false)
Definition: DataDependenceGraph.cc:2079
POMDisassembler.hh
DataDependenceGraph::setCycleGrouping
virtual void setCycleGrouping(bool flag)
Definition: DataDependenceGraph.cc:1738
BoostGraph< MoveNode, DataDependenceEdge >::moveInEdge
virtual void moveInEdge(const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
MoveNode::isPlaced
bool isPlaced() const
Definition: MoveNode.cc:352
DataDependenceGraph::combineNodes
void combineNodes(MoveNode &node1, MoveNode &node2, MoveNode &destination)
Definition: DataDependenceGraph.cc:2782
TCEString.hh
MoveNode::setSourceOperationPtr
void setSourceOperationPtr(ProgramOperationPtr po)
Definition: MoveNode.cc:541
BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInEdge
virtual Edge & rootGraphInEdge(const Node &node, const int index) const
StringTools::stringToUpper
static std::string stringToUpper(const std::string &source)
Definition: StringTools.cc:143
BasicBlockNode::basicBlock
TTAProgram::BasicBlock & basicBlock()
Definition: BasicBlockNode.cc:126
MoveNode::sourceOperation
ProgramOperation & sourceOperation() const
Definition: MoveNode.cc:453
StringTools.hh
assert
#define assert(condition)
Definition: Application.hh:86
DataDependenceGraph::regWarSuccessors
NodeSet regWarSuccessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4239
DataDependenceGraph::regDepSiblings
NodeSet regDepSiblings(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5620
TTAMachine::FunctionUnit
Definition: FunctionUnit.hh:55
DataDependenceGraph::deleteNode
void deleteNode(MoveNode &node)
Definition: DataDependenceGraph.cc:2882
DataDependenceGraph::setNodeBB
void setNodeBB(MoveNode &mn, BasicBlockNode &bblock, DataDependenceGraph *updater)
Definition: DataDependenceGraph.cc:119
DataDependenceGraph::queueRawPredecessors
bool queueRawPredecessors(NodeSet &queue, NodeSet &finalDest, NodeSet &predQueue, NodeSet &predFinalDest, bool guard) const
Definition: DataDependenceGraph.cc:4918
UniversalMachine.hh
DataDependenceGraph::createSubgraph
DataDependenceGraph * createSubgraph(NodeSet &nodes, bool includeLoops=false)
Definition: DataDependenceGraph.cc:3377
TTAProgram::Terminal::isImmediateRegister
virtual bool isImmediateRegister() const
Definition: Terminal.cc:97
BoostGraph< MoveNode, DataDependenceEdge >::rootGraphOutEdges
virtual EdgeSet rootGraphOutEdges(const Node &node) const
DataDependenceGraph::undo
void undo(UndoData &undoData)
Definition: DataDependenceGraph.cc:5898
DataDependenceGraph::regWawSuccessors
NodeSet regWawSuccessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4347
LiveRange::clear
void clear()
Definition: LiveRange.cc:129
MachineAnalysis.hh
DataDependenceEdge::DEP_UNKNOWN
@ DEP_UNKNOWN
Definition: DataDependenceEdge.hh:46
MoveNode::isMove
bool isMove() const
XMLSerializer.hh
DataDependenceGraph::writeToXMLFile
void writeToXMLFile(std::string fileName) const
Definition: DataDependenceGraph.cc:1747
TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_SRC
@ ANN_ALLOWED_UNIT_SRC
Candidate units can be passed for resource manager for choosing the source/destination unit of the mo...
Definition: ProgramAnnotation.hh:112
TTAProgram::ProgramAnnotation::ANN_REJECTED_UNIT_DST
@ ANN_REJECTED_UNIT_DST
Dst. unit rejected.
Definition: ProgramAnnotation.hh:119
DataDependenceGraph::programOperations_
POList programOperations_
Definition: DataDependenceGraph.hh:437
TTAProgram::ProgramAnnotation::id
ProgramAnnotation::Id id() const
Definition: ProgramAnnotation.cc:111
TTAProgram::Move::setDestination
void setDestination(Terminal *dst)
Definition: Move.cc:333
TTAMachine::BaseRegisterFile
Definition: BaseRegisterFile.hh:48
DataDependenceGraph::operationInEdges
EdgeSet operationInEdges(const MoveNode &node) const
Definition: DataDependenceGraph.cc:5913
TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC
@ ANN_CONN_CANDIDATE_UNIT_SRC
Src. unit candidate.
Definition: ProgramAnnotation.hh:115
DataDependenceGraph::dotString
virtual TCEString dotString() const
Dot printing related methods.
Definition: DataDependenceGraph.cc:1562
DataDependenceGraph::procedureDDG_
bool procedureDDG_
Definition: DataDependenceGraph.hh:454
GraphEdge::weight
int weight() const
Definition: GraphEdge.hh:73
MoveNodeUse::ra
bool ra() const
Definition: MoveNodeUse.hh:41
TTAMachine::Machine::controlUnit
virtual ControlUnit * controlUnit() const
Definition: Machine.cc:345
abortWithError
#define abortWithError(message)
Definition: Application.hh:72
MoveNode::cycle
int cycle() const
Definition: MoveNode.cc:421
HWOperation.hh
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
TTAMachine::HWOperation::name
const std::string & name() const
Definition: HWOperation.cc:141
BoostGraph< MoveNode, DataDependenceEdge >::rootGraph
BoostGraph * rootGraph()
InvalidData
Definition: Exception.hh:149
DataDependenceEdge::loopDepth
int loopDepth() const
Definition: DataDependenceEdge.hh:121
BoostGraph< MoveNode, DataDependenceEdge >::EdgeSet
std::set< DataDependenceEdge *, typename DataDependenceEdge ::Comparator > EdgeSet
Definition: BoostGraph.hh:87
Instruction.hh
BoostGraph::removeNode
virtual void removeNode(Node &node)
TTAProgram::BasicBlock::liveRangeData_
LiveRangeData * liveRangeData_
Definition: BasicBlock.hh:111
DataDependenceGraph::UndoData::changedDataEdges
std::map< DataDependenceEdge *, TCEString, DataDependenceEdge::Comparator > changedDataEdges
Definition: DataDependenceGraph.hh:75
MoveNodeSet::at
MoveNode & at(int index)
MoveNode::addDestinationOperationPtr
void addDestinationOperationPtr(ProgramOperationPtr po)
Definition: MoveNode.cc:533
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
DataDependenceEdge::DEP_RAW
@ DEP_RAW
Definition: DataDependenceEdge.hh:47
DataDependenceGraph::copyExternalOutEdges
void copyExternalOutEdges(MoveNode &nodeCopy, const MoveNode &source)
Definition: DataDependenceGraph.cc:5346
BoostGraph< MoveNode, DataDependenceEdge >::connectingEdge
EdgeDescriptor connectingEdge(const Node &nTail, const Node &nHead) const
TTAMachine::RegisterGuard
Definition: Guard.hh:137
DataDependenceGraph::updateRegUse
void updateRegUse(const MoveNodeUse &mnd, const TCEString &reg, TTAProgram::BasicBlock &bb)
Definition: DataDependenceGraph.cc:5367
BoostGraph< MoveNode, DataDependenceEdge >::inEdge
virtual Edge & inEdge(const Node &node, const int index) const
DataDependenceGraph::UndoData::removedEdges
RemovedEdgeMap removedEdges
Definition: DataDependenceGraph.hh:73
BoostGraph< MoveNode, DataDependenceEdge >::childGraphs_
std::vector< BoostGraph< MoveNode, DataDependenceEdge > * > childGraphs_
Definition: BoostGraph.hh:378
DataDependenceGraph::firstScheduledRegisterRead
MoveNode * firstScheduledRegisterRead(const TTAMachine::BaseRegisterFile &rf, int registerIndex, int firstCycleToTest=0) const
Definition: DataDependenceGraph.cc:808
Application.hh
DataDependenceEdge::EDGE_FUSTATE
@ EDGE_FUSTATE
Definition: DataDependenceEdge.hh:55
TTAProgram::Move::guard
MoveGuard & guard() const
Definition: Move.cc:345
DataDependenceEdge::EDGE_OPERATION
@ EDGE_OPERATION
Definition: DataDependenceEdge.hh:56
DataDependenceGraph::nodeOfMove
MoveNode & nodeOfMove(const TTAProgram::Move &move)
Definition: DataDependenceGraph.cc:3600
BoostGraph< MoveNode, DataDependenceEdge >::moveOutEdges
virtual void moveOutEdges(const Node &source, const Node &destination)
XMLSerializer::setDestinationFile
void setDestinationFile(const std::string &fileName)
Definition: XMLSerializer.cc:142
__func__
#define __func__
Definition: Application.hh:67
DataDependenceGraph::machine_
const TTAMachine::Machine * machine_
Definition: DataDependenceGraph.hh:448
ObjectState.hh
TTAProgram::Instruction::parent
CodeSnippet & parent() const
Definition: Instruction.cc:109
TTAMachine::Machine::functionUnitNavigator
virtual FunctionUnitNavigator functionUnitNavigator() const
Definition: Machine.cc:380
DataDependenceGraph::otherSuccessorsScheduled
bool otherSuccessorsScheduled(MoveNode &node, const NodeSet &ignoredNodes) const
Definition: DataDependenceGraph.cc:3266
DataDependenceGraph::removeNode
void removeNode(MoveNode &node)
Definition: DataDependenceGraph.cc:2843
BasicBlockNode
Definition: BasicBlockNode.hh:64
DataDependenceEdge::isRegisterOrRA
bool isRegisterOrRA() const
Definition: DataDependenceEdge.hh:129
DataDependenceGraph::hasUnscheduledPredecessors
bool hasUnscheduledPredecessors(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5594
TTAProgram::Terminal::isGPR
virtual bool isGPR() const
Definition: Terminal.cc:107
DataDependenceGraph::onlyGuardDefOfMove
MoveNode * onlyGuardDefOfMove(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:4581
Guard.hh
TTAMachine::FunctionUnit::operationCount
virtual int operationCount() const
Definition: FunctionUnit.cc:419
ObjectState::addChild
void addChild(ObjectState *child)
Definition: ObjectState.cc:376
Operation.hh
DataDependenceEdge::toString
TCEString toString() const
Definition: DataDependenceEdge.cc:201
MoveNode::isSourceOperation
bool isSourceOperation() const
Definition: MoveNode.cc:168
TTAProgram::Terminal::value
virtual SimValue value() const
Definition: Terminal.cc:178
DataDependenceGraph::hasOtherRegWawSources
bool hasOtherRegWawSources(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5701
DataDependenceGraph::findLoopIndexUpdate
std::pair< MoveNode *, int > findLoopIndexUpdate(MoveNode *indexMove)
Definition: DataDependenceGraph.cc:4704
DataDependenceGraph::connectOrDeleteEdge
bool connectOrDeleteEdge(const MoveNode &tailNode, const MoveNode &headNode, DataDependenceEdge *edge)
Definition: DataDependenceGraph.cc:3355
DataDependenceGraph::smallestCycle
int smallestCycle() const
Definition: DataDependenceGraph.cc:1818
TTAProgram::Terminal::immediateUnit
virtual const TTAMachine::ImmediateUnit & immediateUnit() const
Definition: Terminal.cc:240
MoveNode::unsetSourceOperation
void unsetSourceOperation()
Definition: MoveNode.cc:760
Operation::readsMemory
virtual bool readsMemory() const
Definition: Operation.cc:242
DataDependenceGraph::copyIncomingGuardEdges
void copyIncomingGuardEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:3865
DataDependenceGraph::programOperationCount
int programOperationCount() const
Definition: DataDependenceGraph.cc:246
LiveRange::writes
DataDependenceGraph::NodeSet writes
Definition: LiveRange.hh:39
TTAProgram::Move
Definition: Move.hh:55
TTAMachine::ControlUnit::delaySlots
int delaySlots() const
ProgramOperation::removeGuardOutputNode
void removeGuardOutputNode(MoveNode &node)
Definition: ProgramOperation.cc:249
CodeSnippet.hh
Exception
Definition: Exception.hh:54
DataDependenceGraph::unMergeUser
void unMergeUser(MoveNode &resultNode, MoveNode &mergedNode, bool loopBypass=false)
Definition: DataDependenceGraph.cc:2240
BoostGraph< MoveNode, DataDependenceEdge >::EdgeDescriptor
GraphTraits::edge_descriptor EdgeDescriptor
Type with which edges of the graph are seen internally.
Definition: BoostGraph.hh:262
TTAProgram::Move::isInInstruction
bool isInInstruction() const
Definition: Move.cc:144
MoveNodeUse::guard
bool guard() const
Definition: MoveNodeUse.hh:40
DataDependenceGraph::ownedBBN_
BasicBlockNode * ownedBBN_
Definition: DataDependenceGraph.hh:453
DataDependenceGraph::fixAntidepsAfterLoopUnmergeUser
void fixAntidepsAfterLoopUnmergeUser(MoveNode &sourceNode, MoveNode &mergedNode, const TCEString &reg)
Definition: DataDependenceGraph.cc:2213
MoveNode::unsetGuardOperation
void unsetGuardOperation()
Definition: MoveNode.cc:771
MoveNode::destinationOperationCount
unsigned int destinationOperationCount() const
DataDependenceEdge::certainAlias
bool certainAlias() const
Definition: DataDependenceEdge.hh:103
BoostGraph< MoveNode, DataDependenceEdge >::inDegree
virtual int inDegree(const Node &node) const
MoveNodeSet
Definition: MoveNodeSet.hh:41
TTAProgram::ProgramAnnotation::ANN_ALLOWED_UNIT_DST
@ ANN_ALLOWED_UNIT_DST
Dst. unit candidate.
Definition: ProgramAnnotation.hh:113
ProgramOperation::inputMoveCount
int inputMoveCount() const
Definition: ProgramOperation.cc:600
DataDependenceGraph::findLimitingAntidependenceDestination
MoveNode * findLimitingAntidependenceDestination(MoveNode &mn)
Definition: DataDependenceGraph.cc:5293
BoostGraph< MoveNode, DataDependenceEdge >::hasNode
bool hasNode(const Node &) const
DataDependenceGraph::cycleGrouping_
bool cycleGrouping_
Dot printing related variables. Group the printed MoveNodes according to their cycles.
Definition: DataDependenceGraph.hh:442
DataDependenceEdge::data
const TCEString data() const
Definition: DataDependenceEdge.hh:142
DataDependenceEdge::DEP_WAW
@ DEP_WAW
Definition: DataDependenceEdge.hh:49
BoostGraph< MoveNode, DataDependenceEdge >::NodeDescriptor
GraphTraits::vertex_descriptor NodeDescriptor
Type with which nodes of the graph are seen internally.
Definition: BoostGraph.hh:264
DataDependenceGraph::hasEqualEdge
bool hasEqualEdge(const MoveNode &tailNode, const MoveNode &headNode, const DataDependenceEdge &edge) const
Definition: DataDependenceGraph.cc:3324
LiveRange::reads
DataDependenceGraph::NodeSet reads
Definition: LiveRange.hh:40
DataDependenceGraph::onlyIncomingGuard
DataDependenceEdge * onlyIncomingGuard(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:4024
BoostGraph< MoveNode, DataDependenceEdge >::inEdges
virtual EdgeSet inEdges(const Node &node) const
BoostGraph< MoveNode, DataDependenceEdge >::connectingEdges
EdgeSet connectingEdges(const Node &nTail, const Node &nHead) const
GraphBase< MoveNode, DataDependenceEdge >::writeToDotFile
virtual void writeToDotFile(const TCEString &fileName) const
DataDependenceGraph::guardRestored
void guardRestored(MoveNode &guardSrc, MoveNode &dst)
Definition: DataDependenceGraph.cc:5849
TTAProgram::CodeSnippet
Definition: CodeSnippet.hh:59
DataDependenceGraph::isLoopInvariant
bool isLoopInvariant(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5688
ProgramOperation::outputMoveCount
int outputMoveCount() const
Definition: ProgramOperation.cc:610
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
DataDependenceGraph::movesAtCycle
NodeSet movesAtCycle(int cycle) const
Definition: DataDependenceGraph.cc:699
BoostGraph< MoveNode, DataDependenceEdge >::constructSubGraph
void constructSubGraph(BoostGraph &subGraph, NodeSet &nodes)
TCEString::replaceString
TCEString & replaceString(const std::string &old, const std::string &newString)
Definition: TCEString.cc:94
ProgramOperation.hh
LiveRange::guards
DataDependenceGraph::NodeSet guards
Definition: LiveRange.hh:41
TTAProgram::Terminal::functionUnit
virtual const TTAMachine::FunctionUnit & functionUnit() const
Definition: Terminal.cc:251
MoveNodeSet::count
int count() const
DataDependenceGraph::isRootGraphProcedureDDG
bool isRootGraphProcedureDDG()
Definition: DataDependenceGraph.cc:3669
MoveNode::isSourceVariable
bool isSourceVariable() const
Definition: MoveNode.cc:196
BoostGraph< MoveNode, DataDependenceEdge >::edge
virtual Edge & edge(const int index) const
BoostGraph< MoveNode, DataDependenceEdge >::outEdges
virtual EdgeSet outEdges(const Node &node) const
DataDependenceEdge::guardUse
bool guardUse() const
Definition: DataDependenceEdge.hh:100
DataDependenceGraph::lastGuardDefMove
MoveNode * lastGuardDefMove(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:721
MoveNode::destinationOperation
ProgramOperation & destinationOperation(unsigned int index=0) const
DataDependenceGraph::addNode
void addNode(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:144
TTAMachine::Guard::isOpposite
virtual bool isOpposite(const Guard &guard) const =0
TTAProgram::AnnotatedInstructionElement::annotation
ProgramAnnotation annotation(int index, ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID) const
Definition: AnnotatedInstructionElement.cc:100
MoveNode::destinationOperationPtr
ProgramOperationPtr destinationOperationPtr(unsigned int index=0) const
TTAProgram::BasicBlock
Definition: BasicBlock.hh:85
DataDependenceGraph::lastRegisterCycle
int lastRegisterCycle(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:882
TTAProgram::AnnotatedInstructionElement::addAnnotation
void addAnnotation(const ProgramAnnotation &annotation)
Definition: AnnotatedInstructionElement.cc:63
GraphEdge::setWeight
void setWeight(int w)
Definition: GraphEdge.hh:74
MoveNode::move
TTAProgram::Move & move()
DataDependenceGraph::UndoData
Definition: DataDependenceGraph.hh:71
TTAProgram::Instruction::isInProcedure
bool isInProcedure() const
Definition: Instruction.cc:135
BoostGraph< MoveNode, DataDependenceEdge >::isInCriticalPath
bool isInCriticalPath(const MoveNode &node) const
Definition: BoostGraph.hh:179
DataDependenceGraph::trueDependenceGraph
DataDependenceGraph * trueDependenceGraph(bool removeMemAntideps=true, bool ignoreMemDeps=false)
Definition: DataDependenceGraph.cc:3417
POMDisassembler::disassemble
static std::string disassemble(const TTAProgram::Move &move)
Definition: POMDisassembler.cc:629
DisassemblyRegister.hh
TTAProgram::Move::hasSourceLineNumber
bool hasSourceLineNumber() const
Definition: Move.cc:445
LiveRangeData.hh
TTAProgram::Move::parent
Instruction & parent() const
Definition: Move.cc:115
BoostGraph::dropEdge
virtual void dropEdge(Edge &edge)
DataDependenceGraph::destRenamed
DataDependenceGraph::UndoData destRenamed(MoveNode &mn)
Definition: DataDependenceGraph.cc:5055
DataDependenceGraph::guardConverted
void guardConverted(MoveNode &guardSrc, MoveNode &dst)
Definition: DataDependenceGraph.cc:5795
DataDependenceGraph::DataDependenceGraph
DataDependenceGraph(std::set< TCEString > allParamRegs, const TCEString &name="", AntidependenceLevel antidependenceLevel=ALL_ANTIDEPS, BasicBlockNode *ownedBBN=NULL, bool containsProcedure=false, bool noLoopEdges=false)
Definition: DataDependenceGraph.cc:78
false
find Finds info of the inner loops in the false
Definition: InnerLoopFinder.cc:81
DataDependenceGraph::isNotAvoidable
bool isNotAvoidable(const DataDependenceEdge &edge) const
Definition: DataDependenceGraph.cc:5553
DataDependenceEdge::EDGE_MEMORY
@ EDGE_MEMORY
Definition: DataDependenceEdge.hh:54
DataDependenceGraph::onlyRegisterEdgeOut
DataDependenceEdge * onlyRegisterEdgeOut(MoveNode &mn) const
Definition: DataDependenceGraph.cc:276
DataDependenceGraph::exclusingGuards
bool exclusingGuards(const MoveNode &mn1, const MoveNode &mn2) const
Definition: DataDependenceGraph.cc:4480
TTAMachine::Component::machine
virtual Machine * machine() const
MoveNodeSet.hh
AssocTools.hh
GraphEdge
Definition: GraphEdge.hh:52
MoveNode::inSameOperation
bool inSameOperation(const MoveNode &other) const
Definition: MoveNode.cc:306
TCEString
Definition: TCEString.hh:53
DataDependenceGraph::guardsAllowBypass
bool guardsAllowBypass(const MoveNode &defNode, const MoveNode &useNode, bool loopBypass=false)
Definition: DataDependenceGraph.cc:4543
BasicBlock.hh
DataDependenceGraph::programOperationPtr
ProgramOperationPtr programOperationPtr(int index)
Definition: DataDependenceGraph.cc:237
DataDependenceGraph::firstScheduledRegisterKill
MoveNode * firstScheduledRegisterKill(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1320
ControlUnit.hh
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
DataDependenceGraph::dropBackEdges
void dropBackEdges()
Definition: DataDependenceGraph.cc:3620
DataDependenceGraph::copyOutgoingGuardWarEdges
void copyOutgoingGuardWarEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:3897
DataDependenceGraph::criticalPathGraph
DataDependenceGraph * criticalPathGraph()
Definition: DataDependenceGraph.cc:3458
MoveNode::setGuardOperationPtr
void setGuardOperationPtr(ProgramOperationPtr po)
Definition: MoveNode.cc:550
MoveNode::isOperationMove
bool isOperationMove() const
Definition: MoveNode.cc:253
TTAProgram::Terminal::copy
virtual Terminal * copy() const =0
ProgramOperation::inputNode
MoveNodeSet & inputNode(int in) const
Definition: ProgramOperation.cc:513
DataDependenceGraph::memoryDependenceGraph
DataDependenceGraph * memoryDependenceGraph()
Definition: DataDependenceGraph.cc:3482
BoostGraph< MoveNode, DataDependenceEdge >::OutEdgeIter
GraphTraits::out_edge_iterator OutEdgeIter
Output edge iterator type.
Definition: BoostGraph.hh:253
MoveNode::sourceOperationPtr
ProgramOperationPtr sourceOperationPtr() const
Definition: MoveNode.cc:458
DataDependenceGraph::firstScheduledRegisterWrites
NodeSet firstScheduledRegisterWrites(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1245
DataDependenceGraph::AntidependenceLevel
AntidependenceLevel
Definition: DataDependenceGraph.hh:78
DataDependenceGraph::EWH_REAL
@ EWH_REAL
Height returns the minimum cycle count for the schedule given enough resources.
Definition: DataDependenceGraph.hh:92
DataDependenceEdge::saveState
ObjectState * saveState(const MoveNode &tail, const MoveNode &head)
Definition: DataDependenceEdge.cc:345
TTAProgram::Terminal
Definition: Terminal.hh:60
TTAProgram::Terminal::equals
virtual bool equals(const Terminal &other) const =0
DataDependenceEdge
Definition: DataDependenceEdge.hh:43
TTAProgram::CodeSnippet::instructionAtIndex
virtual Instruction & instructionAtIndex(int index) const
Definition: CodeSnippet.cc:285
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
BoostGraph< MoveNode, DataDependenceEdge >::graph_
Graph graph_
The internal graph structure.
Definition: BoostGraph.hh:331
BoostGraph
Definition: BoostGraph.hh:83
ProgramOperation::poId
unsigned int poId() const
Definition: ProgramOperation.cc:765
TTAMachine::Machine::Navigator::item
ComponentType * item(int index) const
DataDependenceGraph::operationLatencies_
std::map< TCEString, int > operationLatencies_
Definition: DataDependenceGraph.hh:450
DisassemblyRegister::registerName
static TCEString registerName(const TTAMachine::RegisterFile &rf, int index, char delim='.')
Definition: DisassemblyRegister.cc:95
DataDependenceGraph::UndoData::newEdges
EdgeSet newEdges
Definition: DataDependenceGraph.hh:72
TTAMachine::FunctionUnit::operation
virtual HWOperation * operation(const std::string &name) const
Definition: FunctionUnit.cc:363
DataDependenceGraph::findLoopIndexInit
MoveNode * findLoopIndexInit(MoveNode &updateMove)
Definition: DataDependenceGraph.cc:4755
TTAMachine::HWOperation::latency
int latency() const
Definition: HWOperation.cc:216
TTAMachine::RegisterFile
Definition: RegisterFile.hh:47
DataDependenceGraph::removeOutgoingGuardWarEdges
void removeOutgoingGuardWarEdges(MoveNode &node)
Definition: DataDependenceGraph.cc:5496
TTAProgram::MoveGuard::guard
const TTAMachine::Guard & guard() const
Definition: MoveGuard.cc:86
MachineAnalysis::connectivity
float connectivity() const
Definition: MachineAnalysis.hh:44
TTAProgram::ProgramAnnotation
Definition: ProgramAnnotation.hh:49
TTAProgram::Move::isJump
bool isJump() const
Definition: Move.cc:164
TTAProgram::AnnotatedInstructionElement::removeAnnotations
void removeAnnotations(ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID)
Definition: AnnotatedInstructionElement.cc:146
DataDependenceGraph::allParamRegs_
std::set< TCEString > allParamRegs_
Definition: DataDependenceGraph.hh:430
DataDependenceGraph::rAntiEdgesIn
int rAntiEdgesIn(MoveNode &mn)
Definition: DataDependenceGraph.cc:4001
Move.hh
DataDependenceGraph::onlyRegisterEdgeIn
DataDependenceEdge * onlyRegisterEdgeIn(MoveNode &mn) const
Definition: DataDependenceGraph.cc:255
DataDependenceEdge::headPseudo
bool headPseudo() const
Definition: DataDependenceEdge.hh:115
TTAProgram::Terminal::isImmediate
virtual bool isImmediate() const
Definition: Terminal.cc:63
DataDependenceGraph::firstScheduledRegisterReads
NodeSet firstScheduledRegisterReads(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1121
DataDependenceEdge::DEP_WAR
@ DEP_WAR
Definition: DataDependenceEdge.hh:48
BoostGraph< MoveNode, DataDependenceEdge >::height_
int height_
Definition: BoostGraph.hh:328
BoostGraph< MoveNode, DataDependenceEdge >::name
virtual const TCEString & name() const
BoostGraph< MoveNode, DataDependenceEdge >::parentGraph_
BoostGraph< MoveNode, DataDependenceEdge > * parentGraph_
Definition: BoostGraph.hh:377
TTAProgram::MoveGuard
Definition: MoveGuard.hh:47
DataDependenceGraph::lastScheduledRegisterReads
NodeSet lastScheduledRegisterReads(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1080
DataDependenceGraph::copyDepsOver
EdgeSet copyDepsOver(MoveNode &node, bool anti, bool raw)
Definition: DataDependenceGraph.cc:2422
BoostGraph< MoveNode, DataDependenceEdge >::nodeCount
int nodeCount() const
XMLSerializer
Definition: XMLSerializer.hh:62
DataDependenceGraph::copyExternalInEdges
void copyExternalInEdges(MoveNode &nodeCopy, const MoveNode &source)
Definition: DataDependenceGraph.cc:5323
DataDependenceGraph::updateRegWrite
DataDependenceGraph::EdgeSet updateRegWrite(const MoveNodeUse &mnd, const TCEString &reg, TTAProgram::BasicBlock &bb)
Definition: DataDependenceGraph.cc:5401
TTAMachine::RegisterGuard::registerFile
const RegisterFile * registerFile() const
BoostGraph< MoveNode, DataDependenceEdge >::descriptor
EdgeDescriptor descriptor(const Edge &e) const
DataDependenceGraph::regRawSuccessorCount
int regRawSuccessorCount(const MoveNode &mn, bool onlyScheduled)
Definition: DataDependenceGraph.cc:3952
ProgramOperation::outputMove
MoveNode & outputMove(int index) const
Definition: ProgramOperation.cc:632
DataDependenceGraph::successorsReady
bool successorsReady(MoveNode &node) const
Definition: DataDependenceGraph.cc:3228
DataDependenceEdge::EDGE_RA
@ EDGE_RA
Definition: DataDependenceEdge.hh:57
DataDependenceGraph::unscheduledMoves
NodeSet unscheduledMoves() const
Definition: DataDependenceGraph.cc:1355
LiveRange
Definition: LiveRange.hh:38
BoostGraph< MoveNode, DataDependenceEdge >::successors
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
TTAMachine::Machine::Navigator
Definition: Machine.hh:186
BoostGraph< MoveNode, DataDependenceEdge >::rootGraphInEdges
virtual EdgeSet rootGraphInEdges(const Node &node) const
ObjectState::setValue
void setValue(const std::string &value)
DataDependenceGraph::moveNodeBlocks_
std::map< const MoveNode *, BasicBlockNode * > moveNodeBlocks_
Definition: DataDependenceGraph.hh:438
DataDependenceGraph::copyDependencies
void copyDependencies(const MoveNode &src, MoveNode &dst, bool ignoreSameBBBackedges, bool moveOverLoopEdge=true)
Definition: DataDependenceGraph.cc:3816
DataDependenceGraph::edgeWeightHeuristics_
EdgeWeightHeuristics edgeWeightHeuristics_
The heuristics to use to weight edges in the longest path computation.
Definition: DataDependenceGraph.hh:458
DataDependenceGraph::hasAllRegisterAntidependencies
bool hasAllRegisterAntidependencies()
Definition: DataDependenceGraph.hh:379
DataDependenceGraph::removeRAWEdges
TCEString removeRAWEdges(MoveNode &sourceNode, MoveNode &userNode)
Definition: DataDependenceGraph.cc:1937
TTAProgram::Instruction::moveCount
int moveCount() const
Definition: Instruction.cc:176
DataDependenceGraph::findBypassSource
MoveNode * findBypassSource(const MoveNode &mn)
Definition: DataDependenceGraph.cc:5734
DataDependenceGraph::getBasicBlockNode
const BasicBlockNode & getBasicBlockNode(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:186
DataDependenceGraph::writesJumpGuard
bool writesJumpGuard(const MoveNode &moveNode)
Definition: DataDependenceGraph.cc:4593
DataDependenceGraph::getOperationLatency
int getOperationLatency(const TCEString &name) const
Definition: DataDependenceGraph.cc:3304
BoostGraph< MoveNode, DataDependenceEdge >::InEdgeIter
GraphTraits::in_edge_iterator InEdgeIter
Input edge iterator type.
Definition: BoostGraph.hh:255
LiveRange.hh
DataDependenceGraph::hasRegWaw
bool hasRegWaw(const MoveNodeUse &mnu, std::set< MoveNodeUse > targets) const
Definition: DataDependenceGraph.cc:5518
TTAProgram::ProgramAnnotation::payload
const std::vector< Byte > & payload() const
Definition: ProgramAnnotation.cc:121
DataDependenceEdge::edgeReason
EdgeReason edgeReason() const
Definition: DataDependenceEdge.hh:91
BoostGraph< MoveNode, DataDependenceEdge >::EdgeIter
GraphTraits::edge_iterator EdgeIter
Iterator type for the list of all edges in the graph.
Definition: BoostGraph.hh:257
InstanceNotFound
Definition: Exception.hh:304
DataDependenceGraph::mergeAndKeepSource
bool mergeAndKeepSource(MoveNode &resultNode, MoveNode &userNode, bool force=false)
Definition: DataDependenceGraph.cc:1962
TTAProgram::Move::setSource
void setSource(Terminal *src)
Definition: Move.cc:312
ProgramOperation::removeOutputNode
void removeOutputNode(MoveNode &node, int outputIndex)
Definition: ProgramOperation.cc:214
ProgramOperation::inputMove
MoveNode & inputMove(int index) const
Definition: ProgramOperation.cc:621
TTAMachine::Machine
Definition: Machine.hh:73
DataDependenceGraph::sourceRenamed
DataDependenceGraph::UndoData sourceRenamed(MoveNode &mn)
Definition: DataDependenceGraph.cc:4970
XMLSerializer::writeState
virtual void writeState(const ObjectState *rootState)
Definition: XMLSerializer.cc:219
DataDependenceGraph::hasUnscheduledSuccessors
bool hasUnscheduledSuccessors(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5607
DataDependenceGraph::setEdgeWeightHeuristics
void setEdgeWeightHeuristics(EdgeWeightHeuristics ewh)
Definition: DataDependenceGraph.cc:5716
DataDependenceGraph::dropProgramOperation
void dropProgramOperation(ProgramOperationPtr po)
Definition: DataDependenceGraph.cc:361
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
DataDependenceGraph::mergeAndKeepAllowed
bool mergeAndKeepAllowed(MoveNode &sourceNode, MoveNode &userNode)
Definition: DataDependenceGraph.cc:1880
MoveGuard.hh