OpenASIP  2.0
RegisterCopyAdder.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2012 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 RegisterCopyAdder.cc
26  *
27  * Definition of RegisterCopyAdder class.
28  *
29  * @todo rename the file to match the class name
30  *
31  * @author Pekka Jääskeläinen 2007,2012 (pjaaskel-no.spam-cs.tut.fi)
32  * @author Fabio Garzia 2010 (fabio.garzia-no.spam-cs.tut.fi)
33  * @note rating: orange
34  * @note reviewed 16-17 January 2008 by pj, pk, ml, hk
35  */
36 
37 #include "Machine.hh"
38 #include "ControlUnit.hh"
39 #include "RegisterCopyAdder.hh"
40 #include "DataDependenceGraph.hh"
42 #include "ProgramOperation.hh"
43 #include "HWOperation.hh"
44 #include "FUPort.hh"
46 #include "BasicBlock.hh"
47 #include "POMDisassembler.hh"
48 #include "Instruction.hh"
49 #include "AssocTools.hh"
50 #include "SpecialRegisterPort.hh"
51 #include "ProgramAnnotation.hh"
52 #include "InterPassDatum.hh"
53 #include "InterPassData.hh"
54 #include "Exception.hh"
55 #include "BusBroker.hh"
56 #include "TCEString.hh"
57 #include "MoveNodeSelector.hh"
58 #include "Guard.hh"
59 #include "TerminalRegister.hh"
60 #include "TerminalImmediate.hh"
61 #include "DisassemblyRegister.hh"
62 #include "SimpleResourceManager.hh"
63 #include "Operation.hh"
64 #include "Move.hh"
65 
66 //#define DEBUG_REG_COPY_ADDER
67 
68 /**
69  * Constructor.
70  *
71  * @param data The inter-pass data.
72  * @param rm The resource manager used to check for availability of resources.
73  */
76  MoveNodeSelector&, bool buScheduler) :
77  interPassData_(data), rm_(rm),
78  buScheduler_(buScheduler) {
79 }
80 
81 /**
82  * Destructor.
83  */
85 }
86 
87 /**
88  * Counts the temporary register copies required for each FU in case the
89  * given operation was assigned to them.
90  *
91  * @param targetMachine The machine to use.
92  * @return An index with temporary register move counts.
93  */
96  const TTAMachine::Machine& targetMachine,
97  ProgramOperation& programOperation) {
98 
99  RegisterCopyCountIndex registerCopiesRequired;
100 
101  // analyze each FU assignment alternative for the operation
103  targetMachine.functionUnitNavigator();
104 
105  for (int i = 0; i <= FUs.count(); i++) {
106 
107  // include control unit in the traversed FUs
108  const TTAMachine::FunctionUnit& unit =
109  (i == FUs.count())?
110  (*targetMachine.controlUnit()) : (*FUs.item(i));
111 
112  std::string operationName = programOperation.operation().name();
113  if (unit.hasOperation(operationName)) {
114  if (isAllowedUnit(unit, programOperation)) {
115  registerCopiesRequired[&unit] =
116  addRegisterCopies(programOperation, unit).count_;
117  }
118  }
119  }
120 
121  return registerCopiesRequired;
122 }
123 
124 /**
125  * Adds minimum register copies required for the given operation.
126  *
127  * Adds the register copies to the given DDG along with required new edges
128  * between the copy moves and annotates the moves with a candidate set
129  * for the FU binding.
130  *
131  * @param programOperation The operation execution.
132  * @param targetMachine The target machine.
133  * @param ddg ddg which to update when adding temp reg moves. Can be NULL.
134  * @return Data which temp reg moves were added.
135  * @exception In case there was no such FU that could be connected with
136  * a temp register chain of maximal length of 2 copies.
137  */
140  ProgramOperation& programOperation,
141  const TTAMachine::Machine& targetMachine,
142  DataDependenceGraph* ddg) {
143 
144 #ifdef DEBUG_REG_COPY_ADDER
146  << "# Add minimum register copies for the following operation: "
147  << std::endl
148  << "# " << programOperation.toString() << std::endl << std::endl;
149 #endif
150 
152  registerCopiesRequired =
153  requiredRegisterCopiesForEachFU(targetMachine, programOperation);
154 
155  // find the FU which requires least register copies
156  int min = INT_MAX;
157  const TTAMachine::FunctionUnit* unit = NULL;
158  for (RegisterCopyAdder::RegisterCopyCountIndex::const_iterator
159  i = registerCopiesRequired.begin();
160  i != registerCopiesRequired.end(); ++i) {
161 
162  const TTAMachine::FunctionUnit* u = (*i).first;
163  if (!isAllowedUnit(*u, programOperation)) {
164  continue;
165  }
166  int copies = (*i).second;
167  if (copies < min) {
168  min = copies;
169  unit = u;
170  if (copies == 0) {
171  break;
172  }
173  }
174  }
175 
176  if (min == 0) {
177  // no temp reg copies required for some FU, annotate the moves in case
178  // some FUs require the copies and thus the FU selection should be
179  // restricted to those which do not require any copies
180  addCandidateSetAnnotations(programOperation, targetMachine);
181  // return empty
182  return AddedRegisterCopies();
183  } else if (unit != NULL && min < INT_MAX) {
184  // add register copies as if the operation was assigned to that FU
185  AddedRegisterCopies copies =
186  addRegisterCopies(programOperation, *unit, false, ddg, min);
187 
188  // create the FU candidate set now that we have added the register
189  // copies
190  addCandidateSetAnnotations(programOperation, targetMachine);
191  return copies;
192  } else {
193  throw IllegalMachine(
194  __FILE__, __LINE__, __func__,
195  std::string("Cannot schedule '") +
196  programOperation.toString() +
197  "' ensure that at least one FU supports the operation and is "
198  "connected to some register file.");
199  }
200 }
201 
202 /**
203  * Adds or counts register copies required for a given R-R move to be
204  * assigned without connectivity problems.
205  *
206  * @param The given R-R move.
207  * @param ddg ddg to update, or NULL.
208  * @return Returns data about register copies required if the given operation
209  * execution was assigned to the given FU.
210  */
213  MoveNode& moveNode,
214  DataDependenceGraph* ddg) {
215 
216  AddedRegisterCopies copies;
217  int registerCopyCount = 0;
218  DataDependenceGraph::NodeSet addedNodes;
219 
220 #ifdef DEBUG_REG_COPY_ADDER
222  << "# Add register copies to \""
223  << moveNode.toString() << "\" R-R move."
224  << std::endl << std::endl;
225 #endif
226 
227  const int count = countAndAddConnectionRegisterCopiesToRR(
228  moveNode, ddg, &addedNodes);
229 
230  if (count == INT_MAX) {
231  assert(false &&
232  "Temp moves not possible for the Register-Register move.");
233  }
234  registerCopyCount += count;
235  if (count != 0) {
236  copies.operandCopies_[&moveNode] = addedNodes;
237  }
238 
239  copies.count_ = registerCopyCount;
240  return copies;
241 
242 }
243 
244 
245 /**
246  * Adds or counts register copies required for the given operation to be
247  * assigned without connectivity problems to the given FU.
248  *
249  * @param programOperation The operation execution.
250  * @param fu The function unit the operation should be able to be assigned to.
251  * @param countOnly whether to only count or do the register copies.
252  * @param ddg ddg to update, or NULL.
253  * @return Returns data about register copies required if the given operation
254  * execution was assigned to the given FU.
255  */
258  ProgramOperation& programOperation,
259  const TTAMachine::FunctionUnit& fu,
260  bool countOnly,
261  DataDependenceGraph* ddg,
262  int neededCopies) {
263 
264  AddedRegisterCopies copies;
265  int registerCopyCount = 0;
266  for (int input = 0; input < programOperation.inputMoveCount(); ++input) {
267  MoveNode& m = programOperation.inputMove(input);
268  DataDependenceGraph::NodeSet addedNodes;
269  const int count = addConnectionRegisterCopies(
270  m, fu, countOnly, ddg, &addedNodes, neededCopies);
271  if (count == INT_MAX) {
272  if (countOnly)
273  return INT_MAX;
274  else
275  assert(false && "Temp moves not possible for the FU.");
276  }
277  registerCopyCount += count;
278  if (count != 0 && !countOnly) {
279  copies.operandCopies_[&m] = addedNodes;
280  }
281  }
282 
283  for (int output = 0; output < programOperation.outputMoveCount();
284  ++output) {
285  MoveNode& m = programOperation.outputMove(output);
286 #ifdef DEBUG_REG_COPY_ADDER
287  if (!countOnly)
288  Application::logStream() << "# Add register copies to \""
289  << m.toString() << "\" output move."
290  << std::endl;
291 #endif
292  DataDependenceGraph::NodeSet addedNodes;
293  const int count = addConnectionRegisterCopies(
294  m, fu, countOnly, ddg, &addedNodes, neededCopies);
295  if (count == INT_MAX) {
296  if (countOnly)
297  return INT_MAX;
298  else
299  assert(false && "Temp moves not possible for the FU.");
300  }
301  registerCopyCount += count;
302  if (count != 0 && !countOnly) {
303  copies.resultCopies_[&m] = addedNodes;
304  }
305  }
306  copies.count_ = registerCopyCount;
307  return copies;
308 }
309 
310 /**
311  * Adds or counts register copies required for a move between the given ports.
312  *
313  * Returns 0 in case there is a connection already.
314  *
315  * @param originalMove The move that might not be unschedulable due to missing
316  * connectivity. Will be modified to read from the temporary reg instead in
317  * case connectivity is missing.
318  * @param sourcePort The source port.
319  * @param destinationPort The destination port.
320  * @param countOnly whether to only count or do the register copies.
321  * @param ddg ddg to update
322  * @param addedNodes place to store information about added regcopies.
323  * @return Returns the count of register copies required.
324  * @exception Exception Throws in case the machine does not have
325  * enough connectivity even when 2 register copies are used.
326  */
327 int
329  MoveNode& originalMove,
330  const TTAMachine::Port& sourcePort,
331  const TTAMachine::Port& destinationPort,
332  bool countOnly,
333  DataDependenceGraph* ddg,
334  DataDependenceGraph::NodeSet* addedNodes,
335  int neededCopies) {
336 
337 
338  if (MachineConnectivityCheck::isConnected(sourcePort, destinationPort))
339  return 0;
340 
341  typedef SimpleInterPassDatum<
342  std::vector<std::pair<const TTAMachine::RegisterFile*, int> > >
343  TempRegData;
344 
345  std::string srDatumName = "SCRATCH_REGISTERS";
346  if (!interPassData_.hasDatum(srDatumName) ||
347  (dynamic_cast<TempRegData&>(
348  interPassData_.datum(srDatumName))).size() == 0) {
349  // if there are no temp regs, addign them is impossible.
350  // but scheduling may be posible with some other FU, so
351  // return INT_MAX instead of throwing exception
352  // is only counting the amount of regcopies.
353  if (countOnly) {
354  return INT_MAX;
355  }
356  throw IllegalProgram(
357  __FILE__, __LINE__, __func__,
358  "No scratch registers available for temporary moves.");
359  }
360  const TempRegData& tempRegs =
361  dynamic_cast<TempRegData&>(interPassData_.datum(srDatumName));
362 
363  const int minRegisterWidth =
364  std::min(sourcePort.width(), destinationPort.width());
365 
366  // initialize to 0 -> at default the register file has no connectivity
367  // information
368  // tempRegsDist defines the "distance" (=connectivity level) in terms of
369  // reg copies from the source port; 0 = cannot be reached from the source;
370  // tempRegsConn stores the index of the register file of the previous
371  // connectivity level to which the current register file is connected
372  std::vector<int> tempRegsDist(tempRegs.size(), 0);
373  std::vector<int> tempRegsConn(tempRegs.size(), 0);
374  bool connectionFound = false;
375 
376  int lastRegisterIndex = -1;
377  int firstRegisterIndex = -1;
378  int regsRequired = INT_MAX;
379  int lastRegID = -1;
380 
381  // find a sequence of temp register moves from source to destination
382  // (this algorithm is based on the maze algorithm for ASIC place & route;
383  // it assigns to each register file a number that is equal to the
384  // distance from the source port; at each level check if the register file
385  // can be connected to the destination port)
386  const TTAMachine::RegisterFile* lastRF = NULL;
387  const TTAMachine::RegisterFile* firstRF = NULL;
388  int correctSizeTempsFound = 0;
389 
390  // analyze the first level of connections
391  // check the temp regs directly connected to source
392  for (std::size_t i = 0; i < tempRegs.size(); ++i) {
393  const TTAMachine::RegisterFile& rf = *tempRegs.at(i).first;
394  if (rf.width() < minRegisterWidth) {
395  continue;
396  }
397  ++correctSizeTempsFound;
398  if (MachineConnectivityCheck::isConnected(sourcePort, rf)) {
399 
400  // found a RF that is connected to the source port
401  tempRegsDist[i] = 1;
402 
403  if (MachineConnectivityCheck::isConnected(rf, destinationPort)) {
404  // found a RF that is connected both to the src and dst
405  lastRegID = i;
406  lastRegisterIndex = tempRegs.at(i).second;
407  lastRF = &rf;
408  connectionFound = true;
409  regsRequired = 1;
410  break;
411  }
412  }
413  }
414 
415  int level = 1;
416  int connCount;
417 
418  while (!connectionFound) {
419  // analyze higher levels of register connections
420  connCount = 0;
421  level++;
422  for (std::size_t i = 0; i < tempRegs.size(); ++i) {
423  // select a temp reg without an assigned connections (dist=0)
424  if (connectionFound)
425  break;
426  if (tempRegsDist[i] == 0) {
427  const TTAMachine::RegisterFile& rf = *tempRegs.at(i).first;
428  if (rf.width() < minRegisterWidth) {
429  continue;
430  }
431  ++correctSizeTempsFound;
432 
433  // check if the selected temp reg can be connected with any of the registers
434  // assigned to the previous level
435  for (std::size_t j = 0; j < tempRegs.size(); ++j) {
436  if (tempRegsDist[j] == level - 1) {
437  const TTAMachine::RegisterFile& srcRF = *tempRegs.at(j).first;
438  if (MachineConnectivityCheck::isConnected(srcRF, rf)) {
439 
440  // found a RF that is connected to the previous level
441  // => assign it to the current level of connections
442  tempRegsDist[i] = level;
443  // => increase the number of connections established at this level
444  // this is needed to stop the algorithm if no new connection is
445  // established
446  connCount++;
447  // record the source register for the connection
448  // this is needed to reconstruct the path
449  tempRegsConn[i] = j;
450  if (MachineConnectivityCheck::isConnected(rf, destinationPort)) {
451  // found a RF that is connected to the dst
452  lastRegID = i;
453  lastRegisterIndex = tempRegs.at(i).second;
454  lastRF = &rf;
455  connectionFound = true;
456  break;
457  }
458  }
459  }
460  }
461  }
462  }
463  if (connCount == 0){
464  // no new connection established; the current level is
465  // isolated => algorithm stops
466  break;
467  }
468  }
469 
470 
471  regsRequired = level;
472 
473  if (correctSizeTempsFound == 0) {
474  throw IllegalProgram(
475  __FILE__, __LINE__, __func__,
476  (boost::format(
477  "Register allocator didn't reserve a large enough "
478  "connectivity register for routing the move %s.")
479  % originalMove.toString()).str());
480  }
481 
482  if (countOnly) {
483  return regsRequired;
484  }
485 
486  if (!connectionFound){
487  throw IllegalMachine(
488  __FILE__, __LINE__, __func__,
489  std::string("Cannot schedule ") +
490  originalMove.toString() +
491  " ensure that all FUs are connected to at least one RF." +
492  destinationPort.parentUnit()->name() + " cannot be reached.");
493  }
494 
495 
496  // before splitting, annotate the possible return move so we can still
497  // detect a procedure return in simulator
498  if (originalMove.move().isReturn()) {
501  originalMove.move().setAnnotation(annotation);
502  }
503 
504  // add the register copy moves
505  // starting from the destination port and creating all the needed moves
506 
507  // find a connected port in the last temp reg file of the chain
508  const TTAMachine::RFPort* dstRFPort = NULL;
509  for (int p = 0; p < lastRF->portCount(); ++p) {
510  const TTAMachine::RFPort* RFport = lastRF->port(p);
511  if (MachineConnectivityCheck::isConnected(*RFport, destinationPort)) {
512  dstRFPort = RFport;
513  break;
514  }
515  }
516  assert(dstRFPort != NULL);
517 
519  new TTAProgram::TerminalRegister(*dstRFPort, lastRegisterIndex);
520 
521  TTAProgram::Terminal* originalDestination =
522  originalMove.move().destination().copy();
523 
524  MoveNode* firstMove = NULL;
525  MoveNode* lastMove = NULL;
526 
527  TTAProgram::ProgramAnnotation connMoveAnnotation(
529 
530  /* Make sure that the original move is still the one that should
531  be in the ProgramOperation, i.e., an operation move. The original
532  move should be either the last of the chain or the first, in case
533  it's input or output move, respectively. In case of register move,
534  the original move is considered the fisrt of the chain */
535 
536 
537  TTAProgram::Terminal& omDest = originalMove.move().destination();
538  // may not catch RA on this one.
539  if (omDest.isFUPort() && !omDest.isRA()) {
540  assert(neededCopies != 0); // if 0, we should not be here.
541 
542  // try to bypass the regcopy away, by using previous value in
543  // some reg which is connected to the FU.
544  if (ddg != NULL && neededCopies == 1) {
545  // 2 == no guard edges, 0 == do not care if backedge
546  MoveNode* rawSource =
547  ddg->onlyRegisterRawSource(originalMove, 2, 0);
548 
549  // if would have war out edges, we would have to handle
550  // the war conflicts to those nodes as well, limiting schedule
551  if (rawSource != NULL && ddg->rWarEdgesOut(*rawSource) == 0 &&
552  ddg->guardsAllowBypass(*rawSource, originalMove)) {
553  TTAProgram::Terminal& rawSrcSrc = rawSource->move().source();
554  if (rawSrcSrc.isGPR()) {
555  const TTAMachine::RegisterFile& rf =
556  rawSrcSrc.registerFile();
558  rf, destinationPort)) {
559  delete temp;
560  ddg->mergeAndKeepUser(*rawSource, originalMove);
561 
562  /* cannot remove if first or last write?
563  as may have refs in live range bookkeeping.
564  disable dre here until check ready for this
565  if (!ddg->resultUsed(*rawSource)) {
566  if (rawSource->isScheduled()) {
567  rm_.unassign(*rawSource);
568  }
569  DataDependenceGraph::NodeSet successors =
570  ddg->successors(*rawSource);
571 
572  ddg->removeNode(*rawSource);
573  delete rawSource;
574 
575  // notify selector.
576  for (DataDependenceGraph::NodeSet::iterator
577  iter = successors.begin();
578  iter != successors.end(); iter++) {
579  selector_.mightBeReady(**iter);
580  }
581  }
582  */
583  // just one regcopy needed and that was bypassed.
584  // we can quit.
585  delete originalDestination;
586  return 0;
587  }
588  }
589  }
590  }
591 
592  // input move
593  firstMove = new MoveNode(originalMove.move().copy());
594  lastMove = &originalMove;
595  if (ddg != NULL) {
596  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
597  ddg->addNode(*firstMove,bbn);
598  }
599  // TODO: firstMove leaks if we don't have a ddg.
600 
601  if (addedNodes != NULL) {
602  addedNodes->insert(firstMove);
603  }
604 
605  firstMove->move().addAnnotation(connMoveAnnotation);
606 
607  } else if (originalMove.move().source().isFUPort()) {
608  // output move
609  firstMove = &originalMove;
610  lastMove = new MoveNode(originalMove.move().copy());
611  if (ddg != NULL) {
612  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
613  ddg->addNode(*lastMove,bbn);
614  }
615  if (addedNodes != NULL) {
616  addedNodes->insert(lastMove);
617  }
618 
619  lastMove->move().addAnnotation(connMoveAnnotation);
620  } else {
621  firstMove = &originalMove;
622  lastMove = new MoveNode(originalMove.move().copy());
623  if (ddg != NULL) {
624  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
625  ddg->addNode(*lastMove,bbn);
626  }
627  if (addedNodes != NULL) {
628  addedNodes->insert(lastMove);
629  }
630 
631  lastMove->move().addAnnotation(connMoveAnnotation);
632  }
633 
634  // adding the last move: tempN -> dst
635  TTAProgram::TerminalRegister* lastMoveSrc = temp;
636 
637  lastMove->move().setSource(lastMoveSrc);
638  lastMove->move().setDestination(originalDestination);
639 
640 #ifdef DEBUG_REG_COPY_ADDER
642  << "# Last move of the chain: "
643  << std::endl
644  << "# " << lastMove->toString() << std::endl;
645 #endif
646 
647  // the lastRF becomes the dst of the following
648  // moves
649  TTAProgram::TerminalRegister* moveDst = temp;
650  MoveNode* regToRegCopy = NULL;
651 
652  // add the intermediate moves
653  std::vector<MoveNode*> intMoves(regsRequired - 1);
654  std::vector<const TTAMachine::RegisterFile*> intRF(regsRequired - 1);
655  std::vector<int> intRegisterIndex(regsRequired - 1);
656 
657 
658  if (regsRequired >= 2) {
659  int tempRegisterIndexDst = lastRegisterIndex;
660  int dstID = lastRegID;
661  // for each level
662  for (int i = 0; i < regsRequired - 1; ++i){
663  regToRegCopy = new MoveNode(originalMove.move().copy());
664  // retrieving the source and destination of the current move
665  // from tempRegs
666  int srcID = tempRegsConn[dstID];
667  int tempRegisterIndexSrc = tempRegs.at(srcID).second;
668  const TTAMachine::RegisterFile& dstRF = *tempRegs.at(dstID).first;
669  const TTAMachine::RegisterFile& srcRF = *tempRegs.at(srcID).first;
670  const TTAMachine::RFPort* srcRFPort = NULL;
671  for (int p = 0; p < srcRF.portCount(); ++p) {
672  const TTAMachine::RFPort* RFport = srcRF.port(p);
673  if (MachineConnectivityCheck::isConnected(*RFport, dstRF)) {
674  srcRFPort = RFport;
675  break;
676  }
677  }
678  assert(srcRFPort != NULL);
679 
680  TTAProgram::TerminalRegister* moveSrc =
682  *srcRFPort, tempRegisterIndexSrc);
683  // temp1 now owned by the regCopy
684  regToRegCopy->move().setSource(moveSrc);
685  regToRegCopy->move().setDestination(moveDst->copy());
686 
687  if (ddg != NULL) {
688  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
689  ddg->addNode(*regToRegCopy,bbn);
690  }
691  if (addedNodes != NULL) {
692  addedNodes->insert(regToRegCopy);
693  }
694  regToRegCopy->move().addAnnotation(connMoveAnnotation);
695 
696  //store the intermediate move,
697  // its destination RF and related index in a vector
698  intMoves[regsRequired - 2 - i] = regToRegCopy;
699  intRF[regsRequired - 2 - i] = tempRegs.at(dstID).first;
700  intRegisterIndex[regsRequired - 2 - i] = tempRegisterIndexDst;
701 
702 #ifdef DEBUG_REG_COPY_ADDER
704  << "# Intermediate move #" << regsRequired - 2 - i << " :"
705  << std::endl
706  << "# " << regToRegCopy->toString() << std::endl;
707 #endif
708 
709  // set the current source as destination of the next move
710  moveDst = moveSrc;
711  tempRegisterIndexDst = tempRegisterIndexSrc;
712  dstID = srcID;
713 
714  }
715 
716  firstRF = tempRegs.at(dstID).first;
717  firstRegisterIndex = tempRegisterIndexDst;
718 
719  }
720 
721  // add the first move
722  // src -> temp1
723  firstMove->move().setDestination(moveDst->copy());
724 
725  if (ddg != NULL) {
726  // update the DDG edges
727  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
728  if (regsRequired >= 2) {
730  *ddg, originalMove, firstMove, intMoves, lastMove, firstRF,
731  intRF, lastRF, firstRegisterIndex, intRegisterIndex,
732  lastRegisterIndex, regsRequired, bbn);
733  }
734 
735  else {
737  *ddg, originalMove, firstMove, lastMove, lastRF,
738  lastRegisterIndex, bbn, buScheduler_, false);
739  }
740  }
741 
742  return regsRequired;
743 }
744 
745 /**
746  * Adds register copies required for transporting an immediate to the given
747  * port.
748  *
749  * If there is at least one IU that is connected to the destination and
750  * the immediate is going to be converted to a long immediate, does not
751  * add any temp registers, but annotates the move with the IU choice so
752  * RM can assign it correctly later.
753  *
754  * @param originalMove The move that cannot be scheduled due to missing
755  * connectivity. Will be modified to read from the temporary reg
756  * instead.
757  * @param destinationPort The destination port.
758  * @param countOnly whether to count only or do the reg copies.
759  * @param ddg ddg to update, or null if none.
760  * @param addedNodes place to put data about added reg copies.
761  * @return Returns the count of register copies required.
762  * @exception Exception Throws in case the machine does not have
763  * enough connectivity even when 2 register copies are used or
764  * no scratch registers to redirect unconnected moves through.
765  */
766 int
768  MoveNode& originalMove,
769  const TTAMachine::Port& destinationPort,
770  bool countOnly,
771  DataDependenceGraph* ddg,
772  DataDependenceGraph::NodeSet* addedNodes) {
773 
774  assert(originalMove.isSourceConstant());
775 
776  typedef SimpleInterPassDatum<
777  std::vector<std::pair<const TTAMachine::RegisterFile*, int> > >
778  TempRegData;
779 
780  if (!interPassData_.hasDatum("SCRATCH_REGISTERS") ||
781  (dynamic_cast<TempRegData&>(
782  interPassData_.datum("SCRATCH_REGISTERS"))).size() == 0)
783  throw IllegalProgram(
784  __FILE__, __LINE__, __func__,
785  "No scratch registers available for temporary move for: " +
786  originalMove.toString());
787 
788  const TempRegData& tempRegs =
789  dynamic_cast<TempRegData&>(interPassData_.datum("SCRATCH_REGISTERS"));
790 
791  const TTAProgram::TerminalImmediate& immediate =
792  dynamic_cast<const TTAProgram::TerminalImmediate&>(
793  originalMove.move().source());
794 
795  const int immediateBitWidth =
797  false, immediate, *destinationPort.parentUnit()->machine());
798 
799 
800  /* Find out an RF that is connected to the target (targetConnectedRF) and
801  an RF that can read the immediate.
802 
803  Always do at least a single temp move to a temp RF.
804 
805  In case there is no immediate slot to the RF and the machine has
806  an IU, it will be converted to
807 
808  IMM ->IU -> RF -> DEST during resource assignment.
809 
810  In case there is an RF than can read the IMM but not write to dest,
811  and there is no IU, we need additional temp reg, thus producing:
812 
813  IMM -> RF1 -> RF2 -> DEST
814  */
815 
816  const TTAMachine::RegisterFile* immediateTargetRF = NULL;
817  int immediateTargetIndex = -1;
818 
819  const TTAMachine::RegisterFile* targetConnectedRF = NULL;
820  int targetConnectedIndex = -1;
821 
822  int correctSizeTempsFound = 0;
823  for (std::size_t i = 0; i < tempRegs.size(); ++i) {
824  const TTAMachine::RegisterFile& rf = *tempRegs.at(i).first;
825  if (rf.width() < immediateBitWidth) {
826  continue;
827  }
828  ++correctSizeTempsFound;
830  immediateTargetRF = &rf;
831  immediateTargetIndex = tempRegs.at(i).second;
832  }
833  if (MachineConnectivityCheck::isConnected(rf, destinationPort)) {
834  /// @todo check that the buses support the guard of the
835  /// original move
836  targetConnectedRF = &rf;
837  targetConnectedIndex = tempRegs.at(i).second;
838  if (immediateTargetRF == targetConnectedRF) {
839  // found a RF that can take in immediate and write to the
840  // destination
841  break;
842  }
843  }
844  }
845 
846  assert(
847  correctSizeTempsFound > 0 &&
848  "Register allocator didn't reserve a large enough temp reg!");
849 
850  const bool machineHasIU =
851  destinationPort.parentUnit()->machine()->
852  immediateUnitNavigator().count() > 0;
853 
854  if (targetConnectedRF == NULL) {
855  if (countOnly) {
856  return INT_MAX;
857  } else {
858  throw IllegalMachine(
859  __FILE__, __LINE__, __func__,
860  (boost::format(
861  "%s is not connected to any register file, unable to "
862  "schedule.") %
863  destinationPort.parentUnit()->name()).str());
864  }
865  }
866 
867  int tempRegisterIndex1 = -1;
868  int tempRegisterIndex2 = -1;
869 
870  int regsRequired = INT_MAX;
871  // the RF for the first temp reg copy
872  const TTAMachine::RegisterFile* tempRF1 = NULL;
873  // the RF for the (optional) second temp reg copy
874  const TTAMachine::RegisterFile* tempRF2 = NULL;
875  if (targetConnectedRF == immediateTargetRF || machineHasIU) {
876  // enough to just add a IMM -> TEMPRF -> DEST which
877  // gets converted to IMM -> IU -> TEMPRF -> DEST during resource
878  // assignment in case there is no immediate slots to the TEMPRF
879  tempRF1 = targetConnectedRF;
880  tempRegisterIndex1 = targetConnectedIndex;
881  regsRequired = 1;
882  } else {
883  // IMM -> TEMPRF1 -> TEMPRF2 -> DEST
884  tempRF1 = immediateTargetRF;
885  tempRegisterIndex1 = immediateTargetIndex;
886  tempRF2 = targetConnectedRF;
887  tempRegisterIndex2 = targetConnectedIndex;
888  regsRequired = 2;
889  }
890 
891  if (countOnly)
892  return regsRequired;
893 
894 
895  /* two options:
896  1:
897  IMM -> temp1;
898  temp1 -> dst;
899 
900  2:
901  IMM -> temp1;
902  temp1 -> temp2;
903  temp2 -> dst;
904  */
905 
906  // before splitting, annotate the possible return move so we can still
907  // detect a procedure return in simulator
908  if (originalMove.move().isReturn()) {
911  originalMove.move().setAnnotation(annotation);
912  }
913 
914  // add the register copy moves
915 
916  if (tempRF1 == NULL) {
917  throw IllegalMachine(
918  __FILE__, __LINE__, __func__,
919  (boost::format(
920  "Unable to schedule move '%s' due to lacking "
921  "immediate resources (required width %d bits).")
922  % originalMove.move().toString() % immediateBitWidth).
923  str());
924  }
925 
926  // create the first temporary move 'src -> temp1'
927  // find a connected port in the temp reg file
928  const TTAMachine::RFPort* dstRFPort = NULL;
929  for (int p = 0; p < tempRF1->portCount(); ++p) {
930  const TTAMachine::RFPort* RFport = tempRF1->port(p);
932  immediate, *RFport)) {
933  dstRFPort = RFport;
934  break;
935  } else {
936  // any port will do if there is no immediate slots: IU
937  // conversion takes care of the connectivity in that case
938  dstRFPort = RFport;
939  }
940  }
941 
943  new TTAProgram::TerminalRegister(*dstRFPort, tempRegisterIndex1);
944 
945  TTAProgram::Terminal* originalDestination =
946  originalMove.move().destination().copy();
947 
948  MoveNode* firstMove = NULL;
949  MoveNode* lastMove = NULL;
950 
951  TTAProgram::ProgramAnnotation connMoveAnnotation(
953 
954  /* Make sure that the original move is still the one that should
955  be in the ProgramOperation, i.e., an operation move. The original
956  move should be the last of the chain (should be an input move only
957  as this is an immediate move). */
958  if (originalMove.move().destination().isFUPort() ||
959  originalMove.move().destination().isGPR()) {
960  // input move
961  firstMove = new MoveNode(originalMove.move().copy());
962  lastMove = &originalMove;
963 
964  if (ddg != NULL) {
965  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
966  ddg->addNode(*firstMove,bbn);
967  }
968  if (addedNodes != NULL) {
969  addedNodes->insert(firstMove);
970  }
971 
972  firstMove->move().addAnnotation(connMoveAnnotation);
973  } else {
974  abortWithError("Can add imm temp regs only for FU or RF moves.");
975  }
976 
977  // src -> temp1
978  firstMove->move().setDestination(temp1->copy());
979 
980  TTAProgram::TerminalRegister* lastMoveSrc = temp1;
981 
982  // in the case 2, add the extra register copy 'temp1 -> temp2'
983  MoveNode* regToRegCopy = NULL;
984  if (tempRF2 != NULL) {
985  regToRegCopy = new MoveNode(originalMove.move().copy());
986 
987  // find a connected port in the temp2 reg file
988  const TTAMachine::RFPort* dstRFPort2 = NULL;
989  for (int p = 0; p < tempRF2->portCount(); ++p) {
990  const TTAMachine::RFPort* RFport = tempRF2->port(p);
992  *RFport, destinationPort)) {
993  dstRFPort2 = RFport;
994  break;
995  }
996  }
997  assert(dstRFPort2 != NULL);
999  new TTAProgram::TerminalRegister(*dstRFPort2, tempRegisterIndex2);
1000 
1001  // temp1 -> temp2
1002  regToRegCopy->move().setSource(temp1); // temp1 now owned by the regCopy
1003  regToRegCopy->move().setDestination(temp2->copy());
1004  lastMoveSrc = temp2;
1005 
1006  if (ddg != NULL) {
1007  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
1008  ddg->addNode(*regToRegCopy,bbn);
1009  }
1010  if (addedNodes != NULL) {
1011  addedNodes->insert(regToRegCopy);
1012  }
1013 
1014  regToRegCopy->move().addAnnotation(connMoveAnnotation);
1015  }
1016 
1017  // lastMoveSrc={temp1|temp2} -> dst
1018  lastMove->move().setSource(lastMoveSrc);
1019  lastMove->move().setDestination(originalDestination);
1020 
1021  if (ddg != NULL) {
1022  BasicBlockNode& bbn = ddg->getBasicBlockNode(originalMove);
1023  // update the DDG edges
1025  *ddg, originalMove, firstMove, regToRegCopy, lastMove, tempRF1,
1026  tempRF2, tempRegisterIndex1, tempRegisterIndex2, bbn);
1027  }
1028 
1029  return regsRequired;
1030 }
1031 
1032 /**
1033  * Fixes edges in DDG when only one additional register is required.
1034  *
1035  * @todo currently leaves some inter-bb-antidependencies out,
1036  * these are caught later when doing delay slot filling in order
1037  * to get it working.
1038  *
1039  * @param ddg The DDG to fix.
1040  * @param originalMove The move which got the temp reg chain added.
1041  * @param firstMove First move in the chain.
1042  * @param lastMove The last move in the chain.
1043  * @param tempRF The RF used for the temp move.
1044  * @param lastRegisterIndex The index of the temp register.
1045  *
1046  */
1047 void
1049  DataDependenceGraph& ddg,
1050  MoveNode& originalMove,
1051  MoveNode* firstMove,
1052  MoveNode* lastMove,
1053  const TTAMachine::RegisterFile* lastRF,
1054  int lastRegisterIndex,
1055  BasicBlockNode& currentBBNode,
1056  bool bottomUpScheduler,
1057  bool loopScheduling) {
1058 
1059  // move all incoming edges
1060  DataDependenceGraph::EdgeSet inEdges =
1061  ddg.rootGraph()->inEdges(originalMove);
1062  for (DataDependenceGraph::EdgeSet::iterator i = inEdges.begin();
1063  i != inEdges.end(); ++i) {
1064  DataDependenceEdge& edge = **i;
1065  // only move ra and reg edges
1068  edge.headPseudo()) {
1069  continue;
1070  }
1071 
1072  // guard is copied to all.
1073  if (edge.guardUse() &&
1075  if (lastMove == &originalMove) {
1076  ddg.rootGraph()->copyInEdge(*firstMove, edge);
1077  } else {
1078  ddg.rootGraph()->copyInEdge(*lastMove, edge);
1079  }
1080  } else {
1081  // operand move?
1082  if (lastMove == &originalMove) {
1084  ddg.rootGraph()->moveInEdge(originalMove, *firstMove, edge);
1085  }
1086  } else { // result move
1087  assert (firstMove == &originalMove);
1090  ddg.rootGraph()->moveInEdge(originalMove, *lastMove, edge);
1091  }
1092  }
1093  }
1094  }
1095 
1096  // move all outgoing edges
1097  DataDependenceGraph::EdgeSet outEdges =
1098  ddg.rootGraph()->outEdges(originalMove);
1099  for (DataDependenceGraph::EdgeSet::iterator i = outEdges.begin();
1100  i != outEdges.end(); ++i) {
1101  DataDependenceEdge& edge = **i;
1102 
1103  // only move ra and reg edges
1106  edge.tailPseudo()) {
1107  continue;
1108  }
1109 
1110  // operand move?
1111  if (lastMove == &originalMove) {
1113  // guard war's leave from all nodes.
1114  if (!edge.guardUse()) {
1115  ddg.rootGraph()->moveOutEdge(originalMove, *firstMove, edge);
1116  } // todo: should be copyOutEdge in else branch but
1117  // it causes some ddg to not be dag
1118  }
1119  } else { // result move
1122  ddg.rootGraph()->moveOutEdge(originalMove, *lastMove, edge);
1123  }
1124  // copy outgoing guard war
1126  edge.guardUse()) {
1127  ddg.rootGraph()->copyOutEdge(*lastMove, edge);
1128  }
1129  }
1130  }
1131 
1132 
1133  TCEString tempReg = lastRF->name() + '.' +
1134  Conversion::toString(lastRegisterIndex);
1135 
1136  // add the new edge(s)
1137  DataDependenceEdge* edge1 =
1138  new DataDependenceEdge(
1140  DataDependenceEdge::DEP_RAW, tempReg);
1141  ddg.connectNodes(*firstMove, *lastMove, *edge1);
1142 
1143 
1145  *firstMove, *lastMove, originalMove, *lastRF, lastRegisterIndex,
1146  ddg, currentBBNode, bottomUpScheduler, loopScheduling);
1147 }
1148 
1149 /**
1150  * Fixes edges in DDG after creating the temporary register chain.
1151  *
1152  * @todo currently leaves some inter-bb-antidependencies out,
1153  * these are caught later when doing delay slot filling in order
1154  * to get it working.
1155  *
1156  * @param ddg The DDG to fix.
1157  * @param originalMove The move which got the temp reg chain added.
1158  * @param firstMove First move in the chain.
1159  * @param intMov A vector containing all the intermediate
1160  register to register copies.
1161  * @param lastMove The last move in the chain.
1162  * @param firstRF The RF used for the 1st temp move.
1163  * @param lastRF The RF used for the last temp move.
1164  * @param firstRegisterIndex The index of the 1st temp register.
1165  * @param lastRegisterIndex The index of the last temp register.
1166  * @param regsRequired The number of temp register required.
1167  *
1168  */
1169 void
1171  DataDependenceGraph& ddg,
1172  MoveNode& originalMove,
1173  MoveNode* firstMove,
1174  std::vector<MoveNode*> intMoves,
1175  MoveNode* lastMove,
1176  const TTAMachine::RegisterFile* firstRF,
1177  std::vector<const TTAMachine::RegisterFile*> intRF,
1178  const TTAMachine::RegisterFile* lastRF,
1179  int firstRegisterIndex,
1180  std::vector<int> intRegisterIndex,
1181  int lastRegisterIndex,
1182  int regsRequired,
1183  BasicBlockNode& currentBBNode) {
1184 
1185  // move all incoming edges
1186  DataDependenceGraph::EdgeSet inEdges =
1187  ddg.rootGraph()->inEdges(originalMove);
1188  for (DataDependenceGraph::EdgeSet::iterator i = inEdges.begin();
1189  i != inEdges.end(); ++i) {
1190  DataDependenceEdge& edge = **i;
1191  // only move ra and reg edges
1194  edge.headPseudo()) {
1195  continue;
1196  }
1197 
1198  // guard is copied to all.
1199  if (edge.guardUse() &&
1201 
1202  // grr, these do not contain ALL temp moves
1203  for (int i = 0; i < regsRequired - 1; ++i) {
1204  ddg.copyInEdge(*intMoves[i], edge);
1205  }
1206  // .. so we need also this.
1207  // operand move?
1208  if (lastMove == &originalMove) {
1209  ddg.copyInEdge(*firstMove, edge);
1210  } else { // result move
1211  assert (firstMove == &originalMove);
1212  ddg.copyInEdge(*lastMove, edge);
1213  }
1214  } else {
1215  // operand move?
1216  if (lastMove == &originalMove) {
1218  ddg.moveInEdge(originalMove, *firstMove, edge);
1219  }
1220  } else { // result move
1221  assert (firstMove == &originalMove);
1224  ddg.moveInEdge(originalMove, *lastMove, edge);
1225  }
1226  }
1227  }
1228  }
1229 
1230  // move all outgoing edges
1231  DataDependenceGraph::EdgeSet outEdges =
1232  ddg.rootGraph()->outEdges(originalMove);
1233  for (DataDependenceGraph::EdgeSet::iterator i = outEdges.begin();
1234  i != outEdges.end(); ++i) {
1235  DataDependenceEdge& edge = **i;
1236 
1237  // only move ra and reg edges
1240  edge.tailPseudo()) {
1241  continue;
1242  }
1243 
1244  // operand move?
1245  if (lastMove == &originalMove) {
1247  // guard war's leave from all nodes.
1248  if (!edge.guardUse()) {
1249  ddg.moveOutEdge(originalMove, *firstMove, edge);
1250  } // todo: should be copyOutEdge in else branch but
1251  // it causes some ddg to not be dag
1252  }
1253  } else { // result move
1256  ddg.moveOutEdge(originalMove, *lastMove, edge);
1257  }
1258  // copy outgoing guard war
1260  edge.guardUse()) {
1261  ddg.copyOutEdge(*lastMove, edge);
1262  }
1263  }
1264  }
1265 
1267  *firstRF, firstRegisterIndex);
1268 
1269  // add the new edge(s)
1270  DataDependenceEdge* edgeFirst =
1271  new DataDependenceEdge(
1273  DataDependenceEdge::DEP_RAW, firstTempReg);
1274  ddg.connectNodes(*firstMove, *intMoves[0], *edgeFirst);
1275 
1277  *firstMove, *intMoves[0], originalMove,
1278  *firstRF, firstRegisterIndex, ddg, currentBBNode, buScheduler_, false);
1279 
1280  for (int i = 0; i < regsRequired - 2; ++i) {
1281 
1282  TCEString tempReg = intRF[i+1]->name() + '.' +
1283  Conversion::toString(intRegisterIndex[i+1]);
1284 
1285  DataDependenceEdge* edgeInt =
1286  new DataDependenceEdge(
1288  DataDependenceEdge::DEP_RAW, tempReg);
1289  ddg.connectNodes(*intMoves[i], *intMoves[i + 1], *edgeInt);
1290 
1292  *intMoves[i], *intMoves[i+1], originalMove,
1293  *intRF[i], intRegisterIndex[i], ddg, currentBBNode, buScheduler_, false);
1294  }
1295 
1297  *lastRF, lastRegisterIndex);
1298 
1299  DataDependenceEdge* edgeLast =
1301  DataDependenceEdge::DEP_RAW, lastTempReg);
1302  ddg.connectNodes(*intMoves[regsRequired - 2], *lastMove, *edgeLast);
1303 
1305  *intMoves[regsRequired - 2], *lastMove, originalMove,
1306  *lastRF, lastRegisterIndex, ddg, currentBBNode, buScheduler_, false);
1307 }
1308 
1309 
1310 
1311 void
1313  const MoveNode& defMove, const MoveNode& useMove,
1314  const MoveNode& originalMove,
1315  const TTAMachine::RegisterFile& rf, int index,
1316  DataDependenceGraph& ddg, BasicBlockNode& bbn, bool backwards,
1317  bool loopScheduling) {
1318 
1319  TCEString tempReg = DisassemblyRegister::registerName(rf, index);
1320 
1321  if (backwards) {
1322  DataDependenceGraph::NodeSet firstScheduledDefs0 =
1323  ddg.firstScheduledRegisterWrites(rf, index);
1324 
1325  MoveNode* lastScheduledKill0 =
1326  ddg.lastScheduledRegisterKill(rf, index);
1327 
1328  for (DataDependenceGraph::NodeSet::iterator i =
1329  firstScheduledDefs0.begin();
1330  i != firstScheduledDefs0.end(); i++) {
1331  if (!ddg.exclusingGuards(**i, useMove)) {
1332  DataDependenceEdge* war =
1333  new DataDependenceEdge(
1335  DataDependenceEdge::DEP_WAR, tempReg);
1336  ddg.connectNodes(useMove, **i, *war);
1337  }
1338  if (!ddg.exclusingGuards(**i, defMove)) {
1339  DataDependenceEdge* waw =
1340  new DataDependenceEdge(
1342  DataDependenceEdge::DEP_WAW, tempReg);
1343  ddg.connectNodes(defMove, **i, *waw);
1344  }
1345  }
1346 
1347  if (loopScheduling) {
1348  DataDependenceGraph::NodeSet lastScheduledReads0 =
1349  ddg.lastScheduledRegisterReads(rf, index);
1350 
1351  for (DataDependenceGraph::NodeSet::iterator i =
1352  lastScheduledReads0.begin();
1353  i != lastScheduledReads0.end(); i++) {
1354  if (!ddg.exclusingGuards(**i, defMove)) {
1355  DataDependenceEdge* war =
1356  new DataDependenceEdge(
1358  DataDependenceEdge::DEP_WAR, tempReg,
1359  false, false, false, false, 1);
1360  ddg.connectNodes(**i, defMove, *war);
1361  }
1362  }
1363 
1364  DataDependenceGraph::NodeSet lastScheduledDefs0 =
1365  ddg.lastScheduledRegisterWrites(rf, index);
1366 
1367  for (DataDependenceGraph::NodeSet::iterator i =
1368  lastScheduledDefs0.begin();
1369  i != lastScheduledDefs0.end(); i++) {
1370  if (!ddg.exclusingGuards(**i, defMove)) {
1371  DataDependenceEdge* waw =
1372  new DataDependenceEdge(
1374  DataDependenceEdge::DEP_WAW, tempReg,
1375  false, false, false, false, 1);
1376  ddg.connectNodes(**i, defMove, *waw);
1377  }
1378  }
1379  }
1380 
1381  if (bbn.basicBlock().liveRangeData_ != NULL) {
1382  if (lastScheduledKill0 == NULL) {
1383 
1384  LiveRangeData::MoveNodeUseSet& lastWrites0 =
1385  bbn.basicBlock().liveRangeData_->regDefines_[tempReg];
1386  lastWrites0.insert(MoveNodeUse(defMove));
1387 
1388  LiveRangeData::MoveNodeUseSet& lastReads0 =
1389  bbn.basicBlock().liveRangeData_->regLastUses_[tempReg];
1390  lastReads0.insert(MoveNodeUse(useMove));
1391  }
1392 
1393  // last write, for WaW defs
1394  LiveRangeData::MoveNodeUseSet& firstDefs =
1395  bbn.basicBlock().liveRangeData_->regFirstDefines_[tempReg];
1396 
1397  if (originalMove.move().isUnconditional()) {
1398  LiveRangeData::MoveNodeUseSet& firstReads =
1399  bbn.basicBlock().liveRangeData_->regFirstUses_[tempReg];
1400 
1401  firstReads.clear();
1402  firstDefs.clear();
1403  // TODO: what about updating the kill bookkeeping?
1404  }
1405 
1406  // last write for WaW deps
1407  firstDefs.insert(
1408  MoveNodeUse(defMove));
1409 
1410  // no need to inser use to anything here. all antideps to to def
1411  } // update intra-bb-live-info
1412  } else {
1413  DataDependenceGraph::NodeSet lastScheduledDefs0 =
1414  ddg.lastScheduledRegisterWrites(rf, index);
1415 
1416  DataDependenceGraph::NodeSet lastScheduledUses0 =
1417  ddg.lastScheduledRegisterReads(rf, index);
1418 
1419  MoveNode* firstScheduledKill0 =
1420  ddg.firstScheduledRegisterKill(rf, index);
1421 
1422  for (DataDependenceGraph::NodeSet::iterator i =
1423  lastScheduledUses0.begin();
1424  i != lastScheduledUses0.end(); i++) {
1425  if (!ddg.exclusingGuards(**i, defMove)) {
1426  DataDependenceEdge* war =
1427  new DataDependenceEdge(
1429  DataDependenceEdge::DEP_WAR, tempReg);
1430  ddg.connectNodes(**i, defMove, *war);
1431  }
1432  }
1433 
1434  for (DataDependenceGraph::NodeSet::iterator i =
1435  lastScheduledDefs0.begin();
1436  i != lastScheduledDefs0.end(); i++) {
1437  if (!ddg.exclusingGuards(**i, defMove)) {
1438  DataDependenceEdge* waw =
1439  new DataDependenceEdge(
1441  DataDependenceEdge::DEP_WAW, tempReg);
1442  ddg.connectNodes(**i, defMove, *waw);
1443  }
1444  }
1445 
1446  if (bbn.basicBlock().liveRangeData_ != NULL) {
1447  if (firstScheduledKill0 == NULL) {
1448  // set first use of given reg.
1449  LiveRangeData::MoveNodeUseSet& firstWrites0 =
1450  bbn.basicBlock().liveRangeData_->regFirstDefines_[tempReg];
1451  firstWrites0.insert(MoveNodeUse(defMove));
1452  }
1453 
1454  // sets this to be last use of given reg
1455  LiveRangeData::MoveNodeUseSet& lastReads =
1456  bbn.basicBlock().liveRangeData_->regLastUses_[tempReg];
1457 
1458  // last write, for WaW defs
1459  LiveRangeData::MoveNodeUseSet& lastDefs =
1460  bbn.basicBlock().liveRangeData_->regDefines_[tempReg];
1461 
1462  if (originalMove.move().isUnconditional()) {
1463  lastReads.clear();
1464  lastDefs.clear();
1465  // TODO: what about updating the kill bookkeeping?
1466  }
1467 
1468  // last read for WaR deps
1469  lastReads.insert(
1470  MoveNodeUse(useMove));
1471 
1472  // last write for WaW deps
1473  lastDefs.insert(
1474  MoveNodeUse(defMove));
1475  }
1476  }
1477 }
1478 
1479 
1480 /**
1481  * Fixes edges in DDG after creating the temporary register chain
1482  * for the Immediate Transport.
1483  *
1484  * @todo currently leaves some inter-bb-antidependencies out,
1485  * these are caught later when doing delay slot filling in order
1486  * to get it working.
1487  *
1488  * @param ddg The DDG to fix.
1489  * @param originalMove The move which got the temp reg chain added.
1490  * @param firstMove First move in the chain.
1491  * @param regToRegCopy A register to register copy in case of a chain of
1492  * length 2 (NULL otherwise).
1493  * @param lastMove The last move in the chain.
1494  * @param tempRF1 The RF used for the 1st temp move.
1495  * @param tempRF2 The RF used for the 2nd temp move (optional).
1496  * @param tempRegisterIndex1 The index of the 1st temp register.
1497  * @param tempRegisterIndex2 The index of the 2nd temp register.
1498  *
1499  */
1500 void
1502  DataDependenceGraph& ddg,
1503  MoveNode& originalMove,
1504  MoveNode* firstMove,
1505  MoveNode* regToRegCopy,
1506  MoveNode* lastMove,
1507  const TTAMachine::RegisterFile* tempRF1,
1508  const TTAMachine::RegisterFile* tempRF2,
1509  int tempRegisterIndex1,
1510  int tempRegisterIndex2,
1511  BasicBlockNode& currentBBNode) {
1512 
1513  // move all incoming edges
1514  DataDependenceGraph::EdgeSet inEdges =
1515  ddg.rootGraph()->inEdges(originalMove);
1516  for (DataDependenceGraph::EdgeSet::iterator i = inEdges.begin();
1517  i != inEdges.end(); ++i) {
1518  DataDependenceEdge& edge = **i;
1519  // only move ra and reg edges
1522  edge.headPseudo()) {
1523  continue;
1524  }
1525 
1526  // guard is copied to all.
1527  if (edge.guardUse() &&
1529  ddg.copyInEdge(*firstMove, edge);
1530  if (regToRegCopy != NULL) {
1531  ddg.copyInEdge(*regToRegCopy, edge);
1532  }
1533  } else {
1534  // operand move?
1535  if (lastMove == &originalMove) {
1537  ddg.moveInEdge(originalMove, *firstMove, edge);
1538  }
1539  } else { // result move
1540  assert (firstMove == &originalMove);
1543  ddg.moveInEdge(originalMove, *lastMove, edge);
1544  }
1545  }
1546  }
1547  }
1548 
1549  // move all outgoing edges
1550  DataDependenceGraph::EdgeSet outEdges =
1551  ddg.rootGraph()->outEdges(originalMove);
1552  for (DataDependenceGraph::EdgeSet::iterator i = outEdges.begin();
1553  i != outEdges.end(); ++i) {
1554  DataDependenceEdge& edge = **i;
1555 
1556  // only move ra and reg edges
1559  edge.tailPseudo()) {
1560  continue;
1561  }
1562 
1563  // operand move?
1564  if (lastMove == &originalMove) {
1566  // guard war's leave from all nodes.
1567  if (!edge.guardUse()) {
1568  ddg.moveOutEdge(originalMove, *firstMove, edge);
1569  } // todo: should be copyOutEdge in else branch but
1570  // it causes some ddg to not be dag
1571  }
1572  } else { // result move
1575  ddg.moveOutEdge(originalMove, *lastMove, edge);
1576  }
1577  // copy outgoing guard war
1579  edge.guardUse()) {
1580  ddg.copyOutEdge(*lastMove, edge);
1581  }
1582  }
1583  }
1584 
1585  TCEString reg1 = tempRF1->name() + '.' +
1586  Conversion::toString(tempRegisterIndex1);
1587 
1588  // add the new edge(s)
1589  if (regToRegCopy != NULL) {
1590 
1591  // todo: also update output list.
1592  TCEString reg2 = tempRF2->name() + '.' +
1593  Conversion::toString(tempRegisterIndex2);
1594 
1595  DataDependenceEdge* edge1 =
1596  new DataDependenceEdge(
1599  ddg.connectNodes(*firstMove, *regToRegCopy, *edge1);
1600 
1601  DataDependenceEdge* edge2 =
1602  new DataDependenceEdge(
1605  ddg.connectNodes(*regToRegCopy, *lastMove, *edge2);
1606 
1608  *firstMove, *regToRegCopy, originalMove,
1609  *tempRF1, tempRegisterIndex1, ddg, currentBBNode,
1610  buScheduler_, false);
1611 
1612  } else { // regcopy == nul
1613  DataDependenceEdge* edge1 =
1614  new DataDependenceEdge(
1617  ddg.connectNodes(*firstMove, *lastMove, *edge1);
1618 
1620  *firstMove, *lastMove, originalMove,
1621  *tempRF1, tempRegisterIndex1, ddg, currentBBNode, buScheduler_, false);
1622  }
1623 }
1624 
1625 /**
1626  * Adds register copies required for the given RR transport.
1627  *
1628  * Returns 0 in case there is a connection already.
1629  *
1630  * @param moveNode The transport.
1631  * @param fu The assumed function unit assigned to the operation of the move.
1632  * @param countOnly whether to just count or really do the reg copies.
1633  * @param ddg ddg to be updated.
1634  * @param addedNode place to put data about added regcopies.
1635  * @return Returns the count of register copies required.
1636  */
1637 int
1639  MoveNode& moveNode,
1640  DataDependenceGraph* ddg,
1641  DataDependenceGraph::NodeSet* addedNodes) {
1642 
1643  // collect the set of possible candidate destination ports (in case of
1644  // RFs, there can be multiple ports)
1645  TTAProgram::Terminal& dest = moveNode.move().destination();
1646  std::set<const TTAMachine::Port*> dstPorts;
1647  if (dest.isGPR()) {
1648  // add all write ports of the RF to the dstPorts
1649  const TTAMachine::RegisterFile& rf = dest.registerFile();
1650  const int ports = rf.portCount();
1651  for (int p = 0; p < ports; ++p) {
1652  const TTAMachine::RFPort* port = rf.port(p);
1653  if (port->isInput())
1654  dstPorts.insert(port);
1655  }
1656  } else {
1657  if (dest.isRA()) {
1658  dstPorts.insert(&(dest.port()));
1659  } else {
1661  "Unsupported move destination type in move '" +
1662  moveNode.toString() + "'.");
1663  }
1664  }
1665 
1666  // collect the set of possible candidate source ports (in case of
1667  // RFs, there can be multiple)
1668  std::set<const TTAMachine::Port*> srcPorts;
1669  TTAProgram::Terminal& source = moveNode.move().source();
1670  if (source.isGPR()) {
1671  // add all read ports of the RF to the srcPorts
1672  const TTAMachine::RegisterFile& rf = source.registerFile();
1673  const int ports = rf.portCount();
1674  for (int p = 0; p < ports; ++p) {
1675  const TTAMachine::RFPort* port = rf.port(p);
1676  if (port->isOutput()) {
1677  srcPorts.insert(port);
1678  }
1679  }
1680  } else if (source.isImmediate() && dest.isGPR()) {
1681  // IMM -> REG should always be possible, at least after LIMM
1682  // conversion (all IUs must be connected to all RFs), so no temp
1683  // registers needed
1684  // register copy adder should not get single immediate moves,
1685  // only operations anyways
1686  return 0;
1687  } else {
1689  "Unsupported move source type in move '" +
1690  moveNode.toString() + "'.");
1691  }
1692 
1693  // go through all srcPorts,dstPorts pairs and see which of them require
1694  // least connection registers and finally select one pair and add
1695  // connection registers accordingly
1696 
1697  typedef std::set<
1698  std::pair<const TTAMachine::Port*, const TTAMachine::Port*>,
1700  CombinationSet;
1701 
1702  CombinationSet pairs = AssocTools::pairs<TTAMachine::Port::PairComparator>(
1703  srcPorts, dstPorts);
1704 
1705  // check if some portpairs already has connection
1706  for (CombinationSet::const_iterator i = pairs.begin(); i != pairs.end();
1707  ++i) {
1708  const TTAMachine::Port& src = *(*i).first;
1709  const TTAMachine::Port& dst = *(*i).second;
1710 
1712  return 0;
1713  }
1714 
1715  const std::pair<const TTAMachine::Port*, const TTAMachine::Port*>*
1716  bestConnection = NULL;
1717  int registersRequired = INT_MAX;
1718  for (CombinationSet::const_iterator i = pairs.begin(); i != pairs.end();
1719  ++i) {
1720  const TTAMachine::Port& src = *(*i).first;
1721  const TTAMachine::Port& dst = *(*i).second;
1722 
1723  int regCount = addConnectionRegisterCopies(moveNode, src, dst);
1724 
1725  if (regCount == 0) {
1726  return 0;
1727  }
1728 
1729  if (regCount < registersRequired) {
1730  bestConnection = &(*i);
1731  registersRequired = regCount;
1732  }
1733  }
1734 
1735  if (bestConnection == NULL) {
1736  throw IllegalMachine(
1737  __FILE__, __LINE__, __func__,
1738  "Could not schedule move '" + moveNode.toString() +
1739  "' due to missing connectivity. "
1740  "Add a connection or a register file that connects "
1741  "the source and the destination.");
1742  }
1743 
1744  const TTAMachine::Port& src = *(bestConnection->first);
1745  const TTAMachine::Port& dst = *(bestConnection->second);
1746 
1747  // actually add the connection now that we have found the best way
1749  moveNode, src, dst, false, ddg, addedNodes);
1750 }
1751 
1752 /**
1753  * Adds register copies required for the given transport.
1754  *
1755  * Returns 0 in case there is a connection already.
1756  *
1757  * @param moveNode The transport.
1758  * @param fu The assumed function unit assigned to the operation of the move.
1759  * @param countOnly whether to just count or really do the reg copies.
1760  * @param ddg ddg to be updated.
1761  * @param addedNode place to put data about added regcopies.
1762  * @return Returns the count of register copies required.
1763  */
1764 int
1766  MoveNode& moveNode,const TTAMachine::FunctionUnit& fu,
1767  bool countOnly, DataDependenceGraph* ddg,
1768  DataDependenceGraph::NodeSet* addedNodes,
1769  int neededCopies) {
1770 
1771  // collect the set of possible candidate destination ports (in case of
1772  // RFs, there can be multiple ports)
1773  TTAProgram::Terminal& dest = moveNode.move().destination();
1774  std::set<const TTAMachine::Port*> dstPorts;
1775  if (dest.isGPR()) {
1776  // add all write ports of the RF to the dstPorts
1777  const TTAMachine::RegisterFile& rf = dest.registerFile();
1778  const int ports = rf.portCount();
1779  for (int p = 0; p < ports; ++p) {
1780  const TTAMachine::RFPort* port = rf.port(p);
1781  if (port->isInput())
1782  dstPorts.insert(port);
1783  }
1784  } else if (dest.isFUPort()) {
1785  if (dynamic_cast<const TTAMachine::SpecialRegisterPort*>(
1786  &dest.port())) {
1787  dstPorts.insert(fu.machine()->controlUnit()->returnAddressPort());
1788  } else {
1789  // regular FU port
1790  dstPorts.insert(
1791  fu.operation(
1792  dest.hintOperation().name())->port(dest.operationIndex()));
1793  }
1794  } else {
1796  "Unsupported move destination type in move '" +
1797  moveNode.toString() + "'.");
1798  }
1799 
1800  // collect the set of possible candidate source ports (in case of
1801  // RFs, there can be multiple)
1802  std::set<const TTAMachine::Port*> srcPorts;
1803  TTAProgram::Terminal& source = moveNode.move().source();
1804  if (source.isGPR()) {
1805  // add all read ports of the RF to the srcPorts
1806  const TTAMachine::RegisterFile& rf = source.registerFile();
1807  const int ports = rf.portCount();
1808  for (int p = 0; p < ports; ++p) {
1809  const TTAMachine::RFPort* port = rf.port(p);
1810  if (port->isOutput()) {
1811  srcPorts.insert(port);
1812  }
1813  }
1814  } else if (source.isFUPort()) {
1815 
1816  if (dynamic_cast<const TTAMachine::SpecialRegisterPort*>(
1817  &source.port())) {
1818  // source is the return address port, it might be still pointing
1819  // to the universal_bus, so we'll check where the RA port is
1820  // connected in the target machine
1821  srcPorts.insert(fu.machine()->controlUnit()->returnAddressPort());
1822  } else {
1823  // a normal FU port
1824  srcPorts.insert(
1825  fu.operation(
1826  source.hintOperation().name())->port(
1827  source.operationIndex()));
1828  }
1829  } else if (source.isImmediate() && dest.isFUPort()) {
1830  /** Check that there is a bus with wide enough immediate slot
1831  that is connected to the target, if not, convert the "constant to
1832  an operand move" to "a constant to a register move".
1833 
1834  This way we ensure connectivity after IU assignment. */
1835 
1836  const TTAMachine::Port* destPort = NULL;
1837  if (dynamic_cast<const TTAMachine::SpecialRegisterPort*>(
1838  &dest.port())) {
1839  // the return address port
1840  destPort = fu.machine()->controlUnit()->returnAddressPort();
1841  } else {
1842  destPort =
1843  fu.operation(
1844  dest.hintOperation().name())->port(dest.operationIndex());
1845  }
1846 
1847  if (destPort == NULL) {
1848  throw IllegalProgram(
1849  __FILE__, __LINE__, __func__,
1850  (boost::format(
1851  "Could not find destination FU port candidate for "
1852  "move '%s'. Is the operand-port binding missing?")
1853  % moveNode.toString()).str());
1854  }
1855  const bool connectionFound =
1857  dynamic_cast<const TTAProgram::TerminalImmediate&>(
1858  moveNode.move().source()), *destPort);
1859 
1860  // no temp move required, there's at least one bus that can transport
1861  // the IMM to the target FU directly
1862  if (connectionFound) {
1863  return 0;
1864  }
1865 
1866  // is there a bus (at all) with a wide enough immediate field?
1867  const bool busFound = rm_.canTransportImmediate(moveNode);
1868 
1869  /**
1870  Convert:
1871 
1872  IMM -> FU
1873 
1874  to
1875 
1876  IMM -> RF
1877  RF -> FU
1878 
1879  In case IMM does not fit in any bus, after scheduler's LIMM
1880  conversion, this should end up being:
1881 
1882  [IMM -> IU] (long immediate transport)
1883  IU -> RF
1884  RF -> FU
1885 
1886  This should fix the following cases:
1887  1) IMM only fits in a bus that is not directly connected to the FU.
1888  2) IMM does not fit in any bus, thus should be transported through
1889  an IU. In that case, ensure connectivity between a IU and FU.
1890  */
1891 
1892  if (busFound && !connectionFound) {
1893  // case 1)
1894  // add SIMM -> RF, RF -> FU, (needs a temp register)
1895  } else if (!busFound && !connectionFound) {
1896  // case 2)
1897  /* Ensure there's at least one IU connecting to the target,
1898  if there is, no temp register is needed as the connectivity
1899  appears after LIMM conversion (IU is a register file that
1900  is guaranteed to be connected at least to a RF that is
1901  connected to the target, if not directly to the target). */
1904  for (int i = 0; i < nav.count(); ++i) {
1905  const TTAMachine::ImmediateUnit* iu = nav.item(i);
1906  if (MachineConnectivityCheck::isConnected(*iu, *destPort)) {
1907  return 0;
1908  }
1909  }
1910  /* None of the IUs are connected to the target FU,
1911  need to add one or more temp registers. */
1912  } else {
1913  abortWithError("Should be an impossible situation.");
1914  }
1916  moveNode, *(*dstPorts.begin()), countOnly, ddg, addedNodes);
1917  } else if (source.isImmediate() && dest.isGPR()) {
1918  // IMM -> REG should always be possible, at least after LIMM
1919  // conversion (all IUs must be connected to all RFs), so no temp
1920  // registers needed
1921  // register copy adder should not get single immediate moves,
1922  // only operations anyways
1923  return 0;
1924  } else {
1926  "Unsupported move source type in move '" +
1927  moveNode.toString() + "'.");
1928  }
1929 
1930  // go through all srcPorts,dstPorts pairs and see which of them require
1931  // least connection registers and finally select one pair and add
1932  // connection registers accordingly
1933 
1934  typedef std::set<
1935  std::pair<const TTAMachine::Port*, const TTAMachine::Port*>,
1937  CombinationSet;
1938 
1939  CombinationSet pairs = AssocTools::pairs<TTAMachine::Port::PairComparator>(
1940  srcPorts, dstPorts);
1941 
1942  // check if some portpairs already has connection
1943  for (CombinationSet::const_iterator i = pairs.begin(); i != pairs.end();
1944  ++i) {
1945  const TTAMachine::Port& src = *(*i).first;
1946  const TTAMachine::Port& dst = *(*i).second;
1947 
1949  return 0;
1950  }
1951 
1952 
1953  const std::pair<const TTAMachine::Port*, const TTAMachine::Port*>*
1954  bestConnection = NULL;
1955  int registersRequired = INT_MAX;
1956  for (CombinationSet::const_iterator i = pairs.begin(); i != pairs.end();
1957  ++i) {
1958  const TTAMachine::Port& src = *(*i).first;
1959  const TTAMachine::Port& dst = *(*i).second;
1960 
1961  int regCount = addConnectionRegisterCopies(moveNode, src, dst);
1962 
1963  if (regCount == 0) {
1964  return 0;
1965  }
1966 
1967  if (regCount < registersRequired) {
1968  bestConnection = &(*i);
1969  registersRequired = regCount;
1970  }
1971  }
1972 
1973  if (countOnly) {
1974  return registersRequired;
1975  }
1976 
1977  if (bestConnection == NULL) {
1978  throw IllegalMachine(
1979  __FILE__, __LINE__, __func__,
1980  "Could not schedule move '" + moveNode.toString() +
1981  "' due to missing connectivity. "
1982  "Add a connection or a register file that connects "
1983  "the source and the destination.");
1984  }
1985 
1986  const TTAMachine::Port& src = *(bestConnection->first);
1987  const TTAMachine::Port& dst = *(bestConnection->second);
1988 
1989  // actually add the connection now that we have found the best way
1991  moveNode, src, dst, countOnly, ddg, addedNodes, neededCopies);
1992 }
1993 
1994 /**
1995  * Adds candidate FU annotations to the operation moves in case there is
1996  * a limited set of FUs the operation can be assigned to.
1997  *
1998  * @param programOperation The operation of which moves to annotate.
1999  * @param machine The machine which contains the FUs.
2000  */
2001 void
2003  ProgramOperation& programOperation,
2004  const TTAMachine::Machine& machine) {
2005 
2007  registerCopiesRequired =
2008  requiredRegisterCopiesForEachFU(machine, programOperation);
2009 
2010  std::set<std::string> candidates;
2011  // check if there's an FU that requires more than 0 copies even now
2012  bool allGoodFUCandidates = true;
2013  // if the long immediate conversion should be performed to ensure
2014  // connectivity, in that case we add IU candidate sets for the
2015  // sources of the input moves that have such immediates
2016 
2017  for (std::map<const TTAMachine::FunctionUnit*, int,
2018  TTAMachine::FunctionUnit::Comparator>::const_iterator
2019  i = registerCopiesRequired.begin();
2020  i != registerCopiesRequired.end(); ++i) {
2021 
2022  const TTAMachine::FunctionUnit* u = (*i).first;
2023  if (!isAllowedUnit(*u, programOperation)) {
2024  continue;
2025  }
2026  if (registerCopiesRequired[u] > 0) {
2027  allGoodFUCandidates = false;
2028  } else {
2029  candidates.insert(u->name());
2030  }
2031  }
2032 
2033  // no annotations needed if any selection for the FU is equally good
2034  // in the connectivity point of view
2035  if (allGoodFUCandidates) {
2036  return;
2037  }
2038 
2039 
2040 
2041  // add annotations to moves of the ProgramOperation that restrict the
2042  // choice of FU to the ones that are possible to assign with the current
2043  // register copies
2044  for (int input = 0; input < programOperation.inputMoveCount(); ++input) {
2045  MoveNode& m = programOperation.inputMove(input);
2046 
2047  for (std::set<std::string>::const_iterator i = candidates.begin();
2048  i != candidates.end(); ++i) {
2049  std::string candidateFU = (*i);
2050  TTAProgram::ProgramAnnotation dstCandidate(
2052  candidateFU);
2053  m.move().addAnnotation(dstCandidate);
2054  }
2055  }
2056 
2057  for (int output = 0; output < programOperation.outputMoveCount();
2058  ++output) {
2059  MoveNode& m = programOperation.outputMove(output);
2060 
2061  for (std::set<std::string>::const_iterator i = candidates.begin();
2062  i != candidates.end(); ++i) {
2063  std::string candidateFU = (*i);
2064  TTAProgram::ProgramAnnotation srcCandidate(
2066  candidateFU);
2067  m.move().addAnnotation(srcCandidate);
2068  }
2069  }
2070 }
2071 
2072 /**
2073  * Called after all operands of a move are scheduled.
2074  * This creates the dependence edges between them.
2075  *
2076  * @param copies information about all regcopies of the po
2077  * @param ddg ddg to update
2078  */
2080  AddedRegisterCopies& copies,
2081  DataDependenceGraph& ddg) {
2082 
2083  DataDependenceGraph::NodeSet inputMoves;
2084  // TODO: sort by cycle, smallest first.
2085  // input operands scheduled, set the ddg edges between temp reg copies.
2086  for (RegisterCopyAdder::AddedRegisterCopyMap::iterator iter =
2087  copies.operandCopies_.begin();
2088  iter != copies.operandCopies_.end();
2089  iter++) {
2090  MoveNode* result = const_cast<MoveNode*>(iter->first);
2091  assert(result->isScheduled());
2092  inputMoves.insert(result);
2093  for (DataDependenceGraph::NodeSet::iterator i2 =
2094  iter->second.begin(); i2 != iter->second.end(); i2++) {
2095  inputMoves.insert(*i2);
2096  }
2097  }
2099 }
2100 
2101 /**
2102  * Called after all results of a move are scheduled.
2103  * This creates the dependence edges between them.
2104  *
2105  * @param copies information about all regcopies of the po
2106  * @param ddg ddg to update
2107  */
2109  AddedRegisterCopies& copies,
2110  DataDependenceGraph& ddg) {
2111 
2112  DataDependenceGraph::NodeSet outputMoves;
2113  // TODO: sort by cycle, smallest first.
2114  // input operands scheduled, set the ddg edges between temp reg copies.
2115  for (RegisterCopyAdder::AddedRegisterCopyMap::iterator iter =
2116  copies.resultCopies_.begin(); iter != copies.resultCopies_.end();
2117  iter++) {
2118  MoveNode* result = const_cast<MoveNode*>(iter->first);
2119  assert(result->isScheduled());
2120  outputMoves.insert(result);
2121  for (DataDependenceGraph::NodeSet::iterator i2 =
2122  iter->second.begin(); i2 != iter->second.end(); i2++) {
2123  // Temporary result moves could get bypassed.
2124  if ((*i2)->isScheduled())
2125  outputMoves.insert(*i2);
2126  }
2127  }
2129 }
2130 
2131 
2132 /**
2133  * Find the temporary registers usef for reg copies
2134  */
2135 void
2137  const TTAMachine::Machine& mach, InterPassData& ipd) {
2138 
2139  auto tempRegRFs = MachineConnectivityCheck::tempRegisterFiles(mach);
2140 
2141  typedef SimpleInterPassDatum<
2142  std::vector<std::pair<const TTAMachine::RegisterFile*,int> > >
2143  TempRegData;
2144 
2145  typedef std::pair<const TTAMachine::RegisterFile*, int> Register;
2146 
2147  std::set<Register> guardRegs;
2148  TempRegData* tempRegData = new TempRegData;
2149 
2150  // find all registers that can be used for guards
2152  for (int i = 0; i < busNav.count(); i++) {
2153  const TTAMachine::Bus* bus = busNav.item(i);
2154  for (int j = 0; j < bus->guardCount(); j++) {
2155  const TTAMachine::RegisterGuard* regGuard =
2156  dynamic_cast<const TTAMachine::RegisterGuard*>(bus->guard(j));
2157  if (regGuard != NULL) {
2158  guardRegs.insert(
2159  Register(
2160  regGuard->registerFile(), regGuard->registerIndex()));
2161  }
2162  }
2163  }
2164 
2165  std::vector<const TTAMachine::RegisterFile*> tempRegRFVec;
2166  for (auto rf: tempRegRFs) {
2167  tempRegRFVec.push_back(rf);
2168  }
2169  // Sort temp RFs by width (narrowest first) so reg copies with small
2170  // registers are preferred.
2171  auto rfLessFn = [] (const TTAMachine::RegisterFile* rf0,
2172  const TTAMachine::RegisterFile* rf1) -> bool {
2173  return rf0->width() < rf1->width();
2174  };
2175  std::sort(tempRegRFVec.begin(), tempRegRFVec.end(), rfLessFn);
2176 
2177  // then mark last (non-guard) register of all gotten reg files
2178  // as tempregcopy reg.
2179  for (unsigned int i = 0; i < tempRegRFVec.size(); i++) {
2180  const TTAMachine::RegisterFile* rf = tempRegRFVec.at(i);
2181  for (int j = rf->size()-1; j >= 0; j--) {
2182  // if does not have a guard, only then used.
2183  // if has guard, try next.
2184  if (!AssocTools::containsKey(guardRegs, Register(rf,j))) {
2185  tempRegData->push_back(
2186  std::pair<const TTAMachine::RegisterFile*,int>(rf, j));
2187  break; // goto next rf
2188  }
2189  }
2190  }
2191 
2192  ipd.setDatum("SCRATCH_REGISTERS", tempRegData);
2193 }
2194 
2195 bool
2197  const TTAMachine::FunctionUnit& fu, const ProgramOperation& po) {
2198 
2199  for (int i = 0; i < po.inputMoveCount(); i++) {
2200  const TTAProgram::Move& move = po.inputMove(i).move();
2201  if (move.hasAnnotations(
2203  !move.hasAnnotation(
2205  fu.name()))
2206  return false;
2207  if (move.hasAnnotations(
2209  !move.hasAnnotation(
2211  fu.name()))
2212  return false;
2213  }
2214 
2215  for (int i = 0; i < po.outputMoveCount(); i++) {
2216  const TTAProgram::Move& move = po.outputMove(i).move();
2217  if (move.hasAnnotations(
2219  !move.hasAnnotation(
2221  fu.name()))
2222  return false;
2223  if (move.hasAnnotations(
2225  !move.hasAnnotation(
2227  fu.name()))
2228  return false;
2229  }
2230  return true;
2231 }
2232 
2233 /**
2234  * Constructor.
2235  *
2236  * @param count count of register copies needed.
2237  */
2239  count_(count) {}
2240 
TTAProgram::Move::copy
std::shared_ptr< Move > copy() const
Definition: Move.cc:413
ProgramOperation::operation
const Operation & operation() const
Definition: ProgramOperation.cc:590
TTAProgram::Terminal::isFUPort
virtual bool isFUPort() const
Definition: Terminal.cc:118
RegisterCopyAdder::AddedRegisterCopies
Definition: RegisterCopyAdder.hh:104
SimpleInterPassDatum
Definition: InterPassDatum.hh:64
MachineConnectivityCheck::requiredImmediateWidth
static int requiredImmediateWidth(bool signExtension, const TTAProgram::TerminalImmediate &source, const TTAMachine::Machine &mach)
Definition: MachineConnectivityCheck.cc:1247
BoostGraph::connectNodes
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
RegisterCopyAdder::addConnectionRegisterCopiesImmediate
int addConnectionRegisterCopiesImmediate(MoveNode &originalMove, const TTAMachine::Port &destinationPort, bool countOnly=true, DataDependenceGraph *ddg=NULL, DataDependenceGraph::NodeSet *addedNodes=NULL)
Definition: RegisterCopyAdder.cc:767
DataDependenceGraph::lastScheduledRegisterWrites
NodeSet lastScheduledRegisterWrites(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1206
TTAMachine::Component::name
virtual TCEString name() const
Definition: MachinePart.cc:125
MoveNode::toString
std::string toString() const
Definition: MoveNode.cc:576
RegisterCopyAdder::addCandidateSetAnnotations
void addCandidateSetAnnotations(ProgramOperation &programOperation, const TTAMachine::Machine &machine)
Definition: RegisterCopyAdder.cc:2002
MachineConnectivityCheck.hh
machine
TTAMachine::Machine * machine
the architecture definition of the estimated processor
Definition: EstimatorCmdLineUI.cc:59
RegisterCopyAdder::fixDDGEdgesInTempRegChainImmediate
void fixDDGEdgesInTempRegChainImmediate(DataDependenceGraph &ddg, MoveNode &originalMove, MoveNode *firstMove, MoveNode *regToRegCopy, MoveNode *lastMove, const TTAMachine::RegisterFile *tempRF1, const TTAMachine::RegisterFile *tempRF2, int tempRegisterIndex1, int tempRegisterIndex2, BasicBlockNode &currentBBNode)
Definition: RegisterCopyAdder.cc:1501
Exception.hh
TTAMachine::RegisterGuard::registerIndex
int registerIndex() const
LiveRangeData::MoveNodeUseSet
std::set< MoveNodeUse > MoveNodeUseSet
Definition: LiveRangeData.hh:51
TTAProgram::Terminal::registerFile
virtual const TTAMachine::RegisterFile & registerFile() const
Definition: Terminal.cc:225
TTAProgram::Move::isReturn
bool isReturn() const
Definition: Move.cc:259
RegisterCopyAdder::interPassData_
InterPassData & interPassData_
the inter pass data from which to fetch the scratch register list
Definition: RegisterCopyAdder.hh:238
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::Move::isUnconditional
bool isUnconditional() const
Definition: Move.cc:154
RegisterCopyAdder::AddedRegisterCopies::AddedRegisterCopies
AddedRegisterCopies()
Definition: RegisterCopyAdder.cc:2241
MachineConnectivityCheck::canTransportImmediate
static bool canTransportImmediate(const TTAProgram::TerminalImmediate &immediate, const TTAMachine::BaseRegisterFile &destRF, const TTAMachine::Guard *guard=NULL)
Definition: MachineConnectivityCheck.cc:181
MoveNodeUse
Definition: MoveNodeUse.hh:20
TTAMachine::Bus
Definition: Bus.hh:53
TTAProgram::AnnotatedInstructionElement::setAnnotation
void setAnnotation(const ProgramAnnotation &annotation)
Definition: AnnotatedInstructionElement.cc:79
TTAMachine::Port::width
virtual int width() const =0
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
LiveRangeData::regDefines_
MoveNodeUseMapSet regDefines_
Definition: LiveRangeData.hh:78
BoostGraph::copyInEdge
virtual void copyInEdge(const Node &destination, Edge &edge, const Node *tail=NULL)
RegisterCopyAdder::AddedRegisterCopies::operandCopies_
AddedRegisterCopyMap operandCopies_
Definition: RegisterCopyAdder.hh:108
TTAProgram::Terminal::hintOperation
virtual Operation & hintOperation() const
Definition: Terminal.cc:341
RegisterCopyAdder::RegisterCopyCountIndex
std::map< const TTAMachine::FunctionUnit *, int, TTAMachine::FunctionUnit::Comparator > RegisterCopyCountIndex
container for storing the required register copies if the operation was bound to the given FU
Definition: RegisterCopyAdder.hh:231
DataDependenceGraph::createRegisterAntiDependenciesBetweenNodes
void createRegisterAntiDependenciesBetweenNodes(NodeSet &nodes)
Definition: DataDependenceGraph.cc:4381
RegisterCopyAdder::addRegisterCopies
AddedRegisterCopies addRegisterCopies(ProgramOperation &programOperation, const TTAMachine::FunctionUnit &fu, bool countOnly=true, DataDependenceGraph *ddg=NULL, int neededCopies=0)
Definition: RegisterCopyAdder.cc:257
DataDependenceGraph.hh
ProgramOperation
Definition: ProgramOperation.hh:70
TTAProgram::Move::toString
std::string toString() const
Definition: Move.cc:436
MoveNode
Definition: MoveNode.hh:65
MoveNode::isSourceConstant
bool isSourceConstant() const
Definition: MoveNode.cc:238
RegisterCopyAdder::fixDDGEdgesInTempReg
static void fixDDGEdgesInTempReg(DataDependenceGraph &ddg, MoveNode &originalMove, MoveNode *firstMove, MoveNode *lastMove, const TTAMachine::RegisterFile *lastRF, int lastRegisterIndex, BasicBlockNode &currentBBNode, bool bottomUpScheduling, bool loopScheduling)
Definition: RegisterCopyAdder.cc:1048
DataDependenceGraph::rWarEdgesOut
int rWarEdgesOut(MoveNode &mn)
Definition: DataDependenceGraph.cc:3930
RegisterCopyAdder::RegisterCopyAdder
RegisterCopyAdder(InterPassData &data, SimpleResourceManager &rm, MoveNodeSelector &selector, bool buScheduler=false)
Definition: RegisterCopyAdder.cc:74
DataDependenceEdge::EDGE_REGISTER
@ EDGE_REGISTER
Definition: DataDependenceEdge.hh:53
Application::logStream
static std::ostream & logStream()
Definition: Application.cc:155
TTAMachine::Machine::Navigator::count
int count() const
BoostGraph::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
RegisterCopyAdder::requiredRegisterCopiesForEachFU
RegisterCopyCountIndex requiredRegisterCopiesForEachFU(const TTAMachine::Machine &targetMachine, ProgramOperation &programOperation)
Definition: RegisterCopyAdder.cc:95
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
DataDependenceGraph::lastScheduledRegisterKill
MoveNode * lastScheduledRegisterKill(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1285
TTAMachine::RFPort
Definition: RFPort.hh:45
RegisterCopyAdder::isAllowedUnit
bool isAllowedUnit(const TTAMachine::FunctionUnit &fu, const ProgramOperation &po)
Definition: RegisterCopyAdder.cc:2196
TerminalRegister.hh
DataDependenceGraph::mergeAndKeepUser
bool mergeAndKeepUser(MoveNode &resultNode, MoveNode &userNode, bool force=false)
Definition: DataDependenceGraph.cc:2079
POMDisassembler.hh
BoostGraph::moveInEdge
virtual void moveInEdge(const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
MoveNodeSelector.hh
TCEString.hh
BasicBlockNode::basicBlock
TTAProgram::BasicBlock & basicBlock()
Definition: BasicBlockNode.cc:126
assert
#define assert(condition)
Definition: Application.hh:86
TTAMachine::FunctionUnit
Definition: FunctionUnit.hh:55
BoostGraph::copyOutEdge
virtual void copyOutEdge(const Node &destination, Edge &edge, const Node *head=NULL)
TTAMachine::HWOperation::port
virtual FUPort * port(int operand) const
Definition: HWOperation.cc:320
DataDependenceGraphBuilder.hh
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::Move::setDestination
void setDestination(Terminal *dst)
Definition: Move.cc:333
TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_SRC
@ ANN_CONN_CANDIDATE_UNIT_SRC
Src. unit candidate.
Definition: ProgramAnnotation.hh:115
TTAMachine::Machine::controlUnit
virtual ControlUnit * controlUnit() const
Definition: Machine.cc:345
TTAProgram::Terminal::operationIndex
virtual int operationIndex() const
Definition: Terminal.cc:364
abortWithError
#define abortWithError(message)
Definition: Application.hh:72
HWOperation.hh
TTAMachine::SpecialRegisterPort
Definition: SpecialRegisterPort.hh:48
BoostGraph::rootGraph
BoostGraph * rootGraph()
BoostGraph< MoveNode, DataDependenceEdge >::EdgeSet
std::set< DataDependenceEdge *, typename DataDependenceEdge ::Comparator > EdgeSet
Definition: BoostGraph.hh:87
RegisterCopyAdder::addRegisterCopiesToRRMove
AddedRegisterCopies addRegisterCopiesToRRMove(MoveNode &moveNode, DataDependenceGraph *ddg)
Definition: RegisterCopyAdder.cc:212
Instruction.hh
TTAProgram::BasicBlock::liveRangeData_
LiveRangeData * liveRangeData_
Definition: BasicBlock.hh:111
DataDependenceEdge::DEP_RAW
@ DEP_RAW
Definition: DataDependenceEdge.hh:47
TTAMachine::Machine::immediateUnitNavigator
virtual ImmediateUnitNavigator immediateUnitNavigator() const
Definition: Machine.cc:416
InterPassDatum.hh
BusBroker.hh
RegisterCopyAdder::findTempRegisters
static void findTempRegisters(const TTAMachine::Machine &machine, InterPassData &ipd)
Definition: RegisterCopyAdder.cc:2136
TTAMachine::RegisterGuard
Definition: Guard.hh:137
TTAMachine::Port
Definition: Port.hh:54
TTAProgram::AnnotatedInstructionElement::hasAnnotation
bool hasAnnotation(ProgramAnnotation::Id id, const TCEString &data) const
Definition: AnnotatedInstructionElement.cc:174
TTAMachine::Port::PairComparator
Definition: Port.hh:88
MachineConnectivityCheck::isConnected
static bool isConnected(const TTAMachine::Port &sourcePort, const TTAMachine::Port &destinationPort, const TTAMachine::Guard *guard=NULL)
Definition: MachineConnectivityCheck.cc:128
IllegalProgram
Definition: Exception.hh:895
LiveRangeData::regFirstDefines_
MoveNodeUseMapSet regFirstDefines_
Definition: LiveRangeData.hh:87
__func__
#define __func__
Definition: Application.hh:67
TTAMachine::Machine::functionUnitNavigator
virtual FunctionUnitNavigator functionUnitNavigator() const
Definition: Machine.cc:380
BasicBlockNode
Definition: BasicBlockNode.hh:64
RegisterCopyAdder::operandsScheduled
void operandsScheduled(AddedRegisterCopies &copies, DataDependenceGraph &ddg)
Definition: RegisterCopyAdder.cc:2079
LiveRangeData::regLastUses_
MoveNodeUseMapSet regLastUses_
Definition: LiveRangeData.hh:79
RegisterCopyAdder::AddedRegisterCopies::count_
int count_
Definition: RegisterCopyAdder.hh:107
TTAProgram::Terminal::isGPR
virtual bool isGPR() const
Definition: Terminal.cc:107
InterPassData
Definition: InterPassData.hh:48
Guard.hh
Operation.hh
TTAProgram::Move
Definition: Move.hh:55
TTAMachine::FunctionUnit::hasOperation
virtual bool hasOperation(const std::string &name) const
Definition: FunctionUnit.cc:330
MoveNodeSelector
Definition: MoveNodeSelector.hh:45
Machine.hh
InterPassData::hasDatum
bool hasDatum(const std::string &key) const
Definition: InterPassData.cc:75
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
TTAMachine::Bus::guardCount
int guardCount() const
Definition: Bus.cc:441
TTAMachine::Port::isOutput
virtual bool isOutput() const
Definition: Port.cc:308
TTAMachine::Bus::guard
Guard * guard(int index) const
Definition: Bus.cc:456
DataDependenceEdge::DEP_WAW
@ DEP_WAW
Definition: DataDependenceEdge.hh:49
TTAMachine::Unit::portCount
virtual int portCount() const
Definition: Unit.cc:135
TTAProgram::AnnotatedInstructionElement::hasAnnotations
bool hasAnnotations(ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID) const
Definition: AnnotatedInstructionElement.cc:165
BoostGraph::inEdges
virtual EdgeSet inEdges(const Node &node) const
RegisterCopyAdder::rm_
SimpleResourceManager & rm_
the resource manager to check for machine resources in heuristics
Definition: RegisterCopyAdder.hh:242
MachineConnectivityCheck::tempRegisterFiles
static std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator > tempRegisterFiles(const TTAMachine::Machine &machine)
Definition: MachineConnectivityCheck.cc:1038
ProgramOperation::outputMoveCount
int outputMoveCount() const
Definition: ProgramOperation.cc:610
ProgramOperation.hh
TTAProgram::TerminalImmediate
Definition: TerminalImmediate.hh:44
BoostGraph::outEdges
virtual EdgeSet outEdges(const Node &node) const
DataDependenceEdge::guardUse
bool guardUse() const
Definition: DataDependenceEdge.hh:100
DataDependenceGraph::addNode
void addNode(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:144
TTAProgram::AnnotatedInstructionElement::addAnnotation
void addAnnotation(const ProgramAnnotation &annotation)
Definition: AnnotatedInstructionElement.cc:63
MoveNode::move
TTAProgram::Move & move()
TTAMachine::BaseRegisterFile::port
virtual RFPort * port(const std::string &name) const
Definition: BaseRegisterFile.cc:129
ProgramOperation::toString
std::string toString() const
Definition: ProgramOperation.cc:746
RegisterCopyAdder::~RegisterCopyAdder
virtual ~RegisterCopyAdder()
Definition: RegisterCopyAdder.cc:84
DisassemblyRegister.hh
RegisterCopyAdder::AddedRegisterCopies::resultCopies_
AddedRegisterCopyMap resultCopies_
Definition: RegisterCopyAdder.hh:109
TTAProgram::ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN
@ ANN_STACKFRAME_PROCEDURE_RETURN
precedure return jmp
Definition: ProgramAnnotation.hh:76
IllegalMachine
Definition: Exception.hh:878
TerminalImmediate.hh
RegisterCopyAdder::resultsScheduled
void resultsScheduled(AddedRegisterCopies &copies, DataDependenceGraph &ddg)
Definition: RegisterCopyAdder.cc:2108
SimpleResourceManager::canTransportImmediate
virtual bool canTransportImmediate(const MoveNode &node, const TTAMachine::Bus *preAssignedBus=NULL) const
Definition: SimpleResourceManager.cc:411
DataDependenceGraph::exclusingGuards
bool exclusingGuards(const MoveNode &mn1, const MoveNode &mn2) const
Definition: DataDependenceGraph.cc:4480
InterPassData.hh
TTAProgram::TerminalRegister::copy
virtual Terminal * copy() const
Definition: TerminalRegister.cc:147
TTAMachine::Component::machine
virtual Machine * machine() const
AssocTools.hh
TCEString
Definition: TCEString.hh:53
FUPort.hh
DataDependenceGraph::guardsAllowBypass
bool guardsAllowBypass(const MoveNode &defNode, const MoveNode &useNode, bool loopBypass=false)
Definition: DataDependenceGraph.cc:4543
BasicBlock.hh
DataDependenceGraph::firstScheduledRegisterKill
MoveNode * firstScheduledRegisterKill(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1320
ControlUnit.hh
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
TTAMachine::Machine::busNavigator
virtual BusNavigator busNavigator() const
Definition: Machine.cc:356
SpecialRegisterPort.hh
RegisterCopyAdder::createAntidepsForReg
static void createAntidepsForReg(const MoveNode &defMove, const MoveNode &useMove, const MoveNode &originalMove, const TTAMachine::RegisterFile &rf, int index, DataDependenceGraph &ddg, BasicBlockNode &bbn, bool backwards, bool loopScheduling)
Definition: RegisterCopyAdder.cc:1312
TTAProgram::Terminal::copy
virtual Terminal * copy() const =0
TTAMachine::Port::isInput
virtual bool isInput() const
Definition: Port.cc:298
RegisterCopyAdder.hh
DataDependenceGraph::firstScheduledRegisterWrites
NodeSet firstScheduledRegisterWrites(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1245
TTAProgram::Terminal
Definition: Terminal.hh:60
SimpleResourceManager.hh
DataDependenceEdge
Definition: DataDependenceEdge.hh:43
MoveNode::isScheduled
bool isScheduled() const
Definition: MoveNode.cc:409
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
SimpleResourceManager
Definition: SimpleResourceManager.hh:58
TTAProgram::ProgramAnnotation::ANN_CONNECTIVITY_MOVE
@ ANN_CONNECTIVITY_MOVE
A reg to reg move that was added because of missing connectivity between the original target and dest...
Definition: ProgramAnnotation.hh:123
TTAProgram::Terminal::port
virtual const TTAMachine::Port & port() const
Definition: Terminal.cc:378
TTAMachine::Machine::Navigator::item
ComponentType * item(int index) const
DisassemblyRegister::registerName
static TCEString registerName(const TTAMachine::RegisterFile &rf, int index, char delim='.')
Definition: DisassemblyRegister.cc:95
TTAMachine::FunctionUnit::operation
virtual HWOperation * operation(const std::string &name) const
Definition: FunctionUnit.cc:363
TTAMachine::RegisterFile
Definition: RegisterFile.hh:47
TTAProgram::ProgramAnnotation
Definition: ProgramAnnotation.hh:49
InterPassData::datum
InterPassDatum & datum(const std::string &key)
Definition: InterPassData.cc:62
RegisterCopyAdder::fixDDGEdgesInTempRegChain
void fixDDGEdgesInTempRegChain(DataDependenceGraph &ddg, MoveNode &originalMove, MoveNode *firstMove, std::vector< MoveNode * > intMoves, MoveNode *lastMove, const TTAMachine::RegisterFile *firstRF, std::vector< const TTAMachine::RegisterFile * > intRF, const TTAMachine::RegisterFile *lastRF, int firstRegisterIndex, std::vector< int > intRegisterIndex, int lastRegisterIndex, int regsRequired, BasicBlockNode &currentBBNode)
Definition: RegisterCopyAdder.cc:1170
Move.hh
RegisterCopyAdder::countAndAddConnectionRegisterCopiesToRR
int countAndAddConnectionRegisterCopiesToRR(MoveNode &moveNode, DataDependenceGraph *ddg=NULL, DataDependenceGraph::NodeSet *addedNodes=NULL)
Definition: RegisterCopyAdder.cc:1638
InterPassData::setDatum
void setDatum(const std::string &key, InterPassDatum *datum)
Definition: InterPassData.cc:89
DataDependenceEdge::headPseudo
bool headPseudo() const
Definition: DataDependenceEdge.hh:115
TTAMachine::ControlUnit::returnAddressPort
SpecialRegisterPort * returnAddressPort() const
Definition: ControlUnit.cc:307
TTAProgram::Terminal::isImmediate
virtual bool isImmediate() const
Definition: Terminal.cc:63
TTAMachine::BaseRegisterFile::size
virtual int size() const
DataDependenceEdge::DEP_WAR
@ DEP_WAR
Definition: DataDependenceEdge.hh:48
TTAProgram::Terminal::isRA
virtual bool isRA() const
Definition: Terminal.cc:129
TTAMachine::MachinePart::Comparator
Definition: MachinePart.hh:59
TTAMachine::BaseRegisterFile::width
virtual int width() const
DataDependenceGraph::lastScheduledRegisterReads
NodeSet lastScheduledRegisterReads(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1080
RegisterCopyAdder::addConnectionRegisterCopies
int addConnectionRegisterCopies(MoveNode &originalMove, const TTAMachine::Port &sourcePort, const TTAMachine::Port &destinationPort, bool countOnly=true, DataDependenceGraph *ddg=NULL, DataDependenceGraph::NodeSet *addedNodes=NULL, int neededCopies=0)
Definition: RegisterCopyAdder.cc:328
TTAMachine::RegisterGuard::registerFile
const RegisterFile * registerFile() const
ProgramOperation::outputMove
MoveNode & outputMove(int index) const
Definition: ProgramOperation.cc:632
DataDependenceEdge::EDGE_RA
@ EDGE_RA
Definition: DataDependenceEdge.hh:57
ProgramAnnotation.hh
TTAMachine::Machine::Navigator
Definition: Machine.hh:186
DataDependenceGraph::getBasicBlockNode
const BasicBlockNode & getBasicBlockNode(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:186
TTAProgram::TerminalRegister
Definition: TerminalRegister.hh:53
RegisterCopyAdder::buScheduler_
bool buScheduler_
Indicate that register copy adder is called from bottom up scheduler, this causes search for first sc...
Definition: RegisterCopyAdder.hh:246
DataDependenceEdge::edgeReason
EdgeReason edgeReason() const
Definition: DataDependenceEdge.hh:91
LiveRangeData::regFirstUses_
MoveNodeUseMapSet regFirstUses_
Definition: LiveRangeData.hh:86
TTAProgram::Move::setSource
void setSource(Terminal *src)
Definition: Move.cc:312
ProgramOperation::inputMove
MoveNode & inputMove(int index) const
Definition: ProgramOperation.cc:621
TTAMachine::Machine
Definition: Machine.hh:73
RegisterCopyAdder::addMinimumRegisterCopies
AddedRegisterCopies addMinimumRegisterCopies(ProgramOperation &programOperation, const TTAMachine::Machine &targetMachine, DataDependenceGraph *ddg)
Definition: RegisterCopyAdder.cc:139
TTAProgram::ProgramAnnotation::ANN_CONN_CANDIDATE_UNIT_DST
@ ANN_CONN_CANDIDATE_UNIT_DST
Dst. unit candidate.
Definition: ProgramAnnotation.hh:116
TTAMachine::Port::parentUnit
Unit * parentUnit() const
TTAMachine::ImmediateUnit
Definition: ImmediateUnit.hh:50