OpenASIP  2.0
ControlFlowGraph.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2015 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 ControlFlowGraph.cc
26  *
27  * Implementation of prototype control flow graph of TTA program
28  * representation.
29  *
30  * @author Andrea Cilio 2005 (cilio-no.spam-cs.tut.fi)
31  * @author Vladimir Guzma 2006 (vladimir.guzma-no.spam-tut.fi)
32  * @author Heikki Kultala 2011 (heikki.kultala-no.spam-tut.fi)
33  * @author Pekka Jääskeläinen 2011,2015
34  * @note rating: red
35  */
36 
37 // LLVM_CPPFLAGS might disable debugging
38 #ifdef NDEBUG
39 #undef NDEBUG
40 #endif
41 
42 #include <vector>
43 #include <algorithm>
44 #include <functional>
45 
46 #pragma GCC diagnostic ignored "-Wunused-parameter"
47 #include "CompilerWarnings.hh"
48 IGNORE_CLANG_WARNING("-Wunused-local-typedef")
49 #include <boost/graph/depth_first_search.hpp>
51 #include <llvm/CodeGen/MachineFunction.h>
52 #include <llvm/Target/TargetMachine.h>
53 #include "tce_config.h"
54 #include <llvm/CodeGen/TargetInstrInfo.h>
55 
56 #include <llvm/IR/Function.h>
57 #include <llvm/IR/Module.h>
58 #include <llvm/CodeGen/TargetSubtargetInfo.h>
59 #include <llvm/MC/MCContext.h>
60 #pragma GCC diagnostic warning "-Wunused-parameter"
61 
62 #include "ControlFlowGraph.hh"
63 
64 #include "BaseType.hh"
65 #include "MapTools.hh"
66 
67 #include "Program.hh"
68 #include "Procedure.hh"
69 #include "Instruction.hh"
70 #include "NullInstruction.hh"
71 #include "Immediate.hh"
72 #include "Move.hh"
73 #include "MoveGuard.hh"
74 #include "Terminal.hh"
75 #include "InstructionReference.hh"
77 #include "Address.hh"
78 #include "DataMemory.hh"
79 #include "DataDefinition.hh"
80 #include "Exception.hh"
81 #include "Application.hh"
82 #include "Operation.hh"
83 #include "SpecialRegisterPort.hh"
84 #include "POMDisassembler.hh"
85 #include "FunctionUnit.hh"
86 #include "ControlUnit.hh"
87 #include "Machine.hh"
88 #include "TerminalRegister.hh"
89 #include "TerminalImmediate.hh"
90 #include "BasicBlock.hh"
91 #include "CFGStatistics.hh"
92 #include "Conversion.hh"
93 #include "InterPassData.hh"
94 #include "InterPassDatum.hh"
97 #include "CodeGenerator.hh"
98 #include "UniversalMachine.hh"
99 #include "Guard.hh"
100 #include "DataDependenceGraph.hh"
101 #include "TerminalFUPort.hh"
102 #include "HWOperation.hh"
103 #include "FUPort.hh"
104 #include "LiveRangeData.hh"
105 
106 using TTAProgram::Program;
110 using TTAProgram::Move;
115 using TTAProgram::Address;
120 using TTAMachine::Port;
123 
124 //#define DEBUG_BB_OPTIMIZER
125 
126 /**
127  * Removes nodes and edge from the graph.
128  *
129  * Removal of nodes automatically frees also the edges.
130  *
131  * @todo: this routine is O(n�)
132  */
134  while (nodeCount() > 0) {
135  BasicBlockNode* b = &node(0);
136  removeNode(*b);
137  delete b;
138  }
139 }
140 
141 /**
142  * Create empty CFG with given name
143  *
144  */
146  const TCEString name,
149  program_(program),
150  startAddress_(TTAProgram::NullAddress::instance()),
151  endAddress_(TTAProgram::NullAddress::instance()),
152  passData_(NULL) {
154 }
155 
156 /**
157  * Read a procedure of TTA program and build a control flow graph
158  * out of it.
159  *
160  * Create a control flow graph using the procedure of POM. Procedure must be
161  * registered in Program to get access to relocations.
162  */
164  const TTAProgram::Procedure& procedure) :
165  BoostGraph<BasicBlockNode, ControlFlowEdge>(procedure.name()),
166  program_(NULL),
167  procedure_(&procedure),
168  startAddress_(TTAProgram::NullAddress::instance()),
169  endAddress_(TTAProgram::NullAddress::instance()),
170  passData_(NULL) {
171  buildFrom(procedure);
172 }
173 
174 /**
175  * Read a procedure of TTA program and build a control flow graph
176  * out of it.
177  *
178  * A version that allows adding inter pass data with additional data
179  * to add to the CFG (currently inner loop BB trip counts).
180  *
181  * Create a control flow graph using the procedure of POM. Procedure must be
182  * registered in Program to get access to relocations.
183  */
185  const TTAProgram::Procedure& procedure,
186  InterPassData& passData) :
187  BoostGraph<BasicBlockNode, ControlFlowEdge>(procedure.name()),
188  program_(NULL),
189  procedure_(&procedure),
190  startAddress_(TTAProgram::NullAddress::instance()),
191  endAddress_(TTAProgram::NullAddress::instance()),
192  passData_(&passData) {
193  buildFrom(procedure);
194 }
195 
196 /**
197  * Constructs the CFG from the given procedure.
198  */
199 void
201  procedure_ = &procedure;
202  procedureName_ = procedure.name();
203  if (procedure.isInProgram()) {
204  program_ = &procedure.parent();
205  }
206  startAddress_ = procedure.startAddress();
207  endAddress_ = procedure.endAddress();
208  alignment_ = procedure.alignment();
209 
210  // Set of instructions that start a new basic block
211  InstructionAddressMap leaders;
212  InstructionAddressMap dataCodeRellocations;
213 
214  computeLeadersFromRefManager(leaders, procedure);
215  /// While finding jump successors, also test if there is indirect jump
216  /// in procedure, in such case also rellocations are used to find
217  /// basic block starts.
218  if (computeLeadersFromJumpSuccessors(leaders, procedure)) {
220  leaders, dataCodeRellocations, procedure);
221  }
222 
223  createAllBlocks(leaders, procedure);
224 
225  // Creates edges between basic blocks
226  createBBEdges(procedure, leaders, dataCodeRellocations);
227  detectBackEdges();
228  addExit();
229 }
230 
231 /**
232  * Creates edges between basic blocks.
233  *
234  * @param procedure Procedure that holds the instructions.
235  * @param leaders Leader instructions, first instructions in basic blocks.
236  * @param dataCodeRellocations Set of dataCodeRellocations that applies to the
237  * given procedure.
238  */
239 void
241  const TTAProgram::Procedure& procedure,
242  InstructionAddressMap& leaders,
243  InstructionAddressMap& dataCodeRellocations) {
244 
245  InstructionAddress leaderAddr;
246  bool hasCFMove = false;
247 
248  InstructionAddress exitAddr = 0;
249  bool hasExit = false;
250  if (procedure.isInProgram()) {
251  /// Look for __exit procedure, if it is found, calls to it will not
252  /// have fall through edges in CFG to avoid possible endless loops
253  /// and create possible unreachable basic blocks
254 
255  if (program_->hasProcedure("__exit")) {
256  exitAddr =
258  location();
259  hasExit = true;
260  } else {
261  /// The __exit procedure was not found, we do not detect calls to
262  /// __exit in calls
263  hasExit = false;
264  }
265  }
266 
267  const int iCount = procedure.instructionCount();
268  for (int insIndex = 0; insIndex < iCount; insIndex++) {
269  Instruction* instruction = &procedure.instructionAtIndex(insIndex);
270  InstructionAddress addr =
271  procedure.startAddress().location() + insIndex;
272 
273  if (MapTools::containsKey(leaders, addr)) {
274  leaderAddr = addr;
275  hasCFMove = false;
276  }
277  // We only deal with one JUMP or CALL per instruction,
278  // there is restriction that there can be no control flow
279  // operations in delay slots of previous operation
280  for (int i = 0, count = instruction->moveCount(); i < count; i++) {
281  if (instruction->move(i).isCall()) {
282  // There is some CF move in a basic block
283  hasCFMove = true;
284  int nextIndex = findNextIndex(procedure, insIndex, i);
285  if (iCount > nextIndex) {
286  /// Do not create fall through edge after call to __exit
287  if (hasExit &&
288  instruction->move(i).source().isInstructionAddress()) {
291  (&instruction->move(i).source());
292  Instruction& destination =
293  address->instructionReference().instruction();
294  if (destination.address().location() == exitAddr) {
295  break;
296  }
297  }
298  Instruction& iNext =
299  procedure.instructionAtIndex(nextIndex);
301  *leaders[leaderAddr], iNext,
304 
305  }
306  break;
307  }
308  if (instruction->move(i).isJump()) {
309  // There is some CF move in basic block
310  hasCFMove = true;
311  createJumps(
312  leaders, leaderAddr, dataCodeRellocations,
313  procedure, insIndex, i);
314  continue;
315  }
316  }
317  if (iCount > insIndex+1) {
318  Instruction& nextInstruction =
319  procedure.instructionAtIndex(insIndex+1);
320  // Look if next instruction is beginning of basic block
321  // and if there was no CF move in current basic block
322  // add fall true edge in such case
323  int nextInsAddr = procedure.startAddress().location() + insIndex+1;
324  if (hasCFMove == false &&
325  MapTools::containsKey(leaders, nextInsAddr)) {
326  BasicBlockNode& blockSource(*blocks_[leaderAddr]);
327  BasicBlockNode& blockTarget(
328  *blocks_[nextInsAddr]);
329  if (!hasEdge(blockSource, blockTarget)) {
331  *leaders[leaderAddr],nextInstruction,
334  }
335  }
336  } else {
337  break;
338  }
339  }
340 }
341 
342 /**
343  * Internal helper. Find the leader instructions from program
344  * reference manager. Should also find startAddress of procedure.
345  *
346  * @param leaders Set of leader instructions to update.
347  * @param procedure The procedure to analyse, uses it's parent() program to
348  * find referenceManager.
349  */
350 void
352  InstructionAddressMap& leaders,
353  const Procedure& procedure) {
354 
355  if (!procedure.isInProgram()) {
356  throw InvalidData(
357  __FILE__, __LINE__, __func__,
358  "For access to reference manager procedure \
359  must be registered in Program!");
360  }
361  InstructionReferenceManager& refManager =
362  procedure.parent().instructionReferenceManager();
363  // Add first instruction of procedure by default,
364  // testing starts from second
365  leaders[startAddress_.location()] = &procedure.firstInstruction();
366 
367  // this can get slow if there are zillion instructionreferences?
368  for (InstructionReferenceManager::Iterator i = refManager.begin();
369  i != refManager.end(); ++i) {
370  Instruction& instruction = i->instruction();
371  InstructionAddress insAddr = instruction.address().location();
372  if (insAddr > startAddress_.location() &&
373  insAddr < endAddress_.location()) {
374  assert(&instruction.parent() == &procedure);
375  leaders[insAddr] = &instruction;
376  }
377  }
378 }
379 
380 
381 /**
382  * Internal helper. Finds the leader instructions that are referred to via
383  * addressed stored in data memory and recorded as data-to-code relocation
384  * entries.
385  *
386  * Adds to a given instruction set all instructions whose address is stored
387  * in data memory (thus are potential targets of an indirect jump) and is
388  * recorded in a data-to-code relocation entry.
389  *
390  * @param leaders Set of leader instructions to update.
391  * @param dataCodeRellocations Set of dataCodeRellocations that applies for
392  * given procedure
393  * @param procedure The procedure to analyse, uses it's parent() program to
394  * access data memory
395  */
396 void
398  InstructionAddressMap& leaders,
399  InstructionAddressMap& dataCodeRellocations,
400  const Procedure& procedure) {
401 
402  if (!procedure.isInProgram()) {
403  throw InvalidData(
404  __FILE__, __LINE__, __func__,
405  "For access to Relocations procedure \
406  must be registered in Program!");
407  }
408  Program& program = procedure.parent();
409  for (int j = 0; j < program.dataMemoryCount(); j++) {
410  const DataMemory& d(program.dataMemory(j));
411  for (int i = 0, count = d.dataDefinitionCount();
412  i < count;
413  i++) {
414  const DataDefinition& dataDef(d.dataDefinition(i));
415  if (!dataDef.isInstructionAddress()) {
416  continue;
417  }
418  const Address& targetAddress(
419  dataDef.destinationAddress());
420  if (targetAddress.location() >= startAddress_.location() &&
421  targetAddress.location() < endAddress_.location()) {
422  Instruction& iTarget(
423  procedure.instructionAt(targetAddress.location())) ;
424  leaders[targetAddress.location()] = &iTarget;
425  dataCodeRellocations[targetAddress.location()] = &iTarget;
426  }
427  }
428  }
429 }
430 
431 
432 /**
433  * Computes starts of basic blocks which follows jumps or calls or are
434  * targets of jump.
435  *
436  * Also detect if any of jumps is indirect, which will require data-code
437  * rellocation information for creating jumps as well.
438  *
439  * @param leaders Set of leader instructions to update.
440  * @param procedure The procedure to analyse.
441  * @return true indicates there is indirect jump in procedure
442  */
443 bool
445  InstructionAddressMap& leaders,
446  const Procedure& procedure) {
447 
448  bool indirectJump = false;
449  // record target instructions of jumps, because they are
450  // leaders of basic block too
451  InstructionAddressMap targets;
452  // The procedure start point is always a block leader.
453 
454  const unsigned int iCount = procedure.instructionCount();
455  for (unsigned int insIndex = 0;insIndex < iCount;) {
456  Instruction* instruction = &procedure.instructionAtIndex(insIndex);
457  // Only one control flow operation per cycle
458  bool increase = true;
459  for (int i = 0; i < instruction->moveCount(); i++) {
460  Move& m(instruction->move(i));
461  if (m.isControlFlowMove()) {
462  // if it is direct jump we store target address
463  if (m.source().isInstructionAddress() && m.isJump()) {
464  Instruction& iTarget =
466  InstructionAddress targetAddr =
467  iTarget.address().location();
468  // If an instruction that is target of a jump has not
469  // been yet identified as a leader, do it here.
470  leaders[targetAddr] = &iTarget;
471  }
472  if (m.isJump() &&
473  (m.source().isGPR() ||
474  m.source().isImmediateRegister())) {
475  indirectJump = true;
476  }
477  increase = false;
478  unsigned int nextIndex = findNextIndex(procedure, insIndex, i);
479  if (iCount > nextIndex) {
480  insIndex = nextIndex;
481  instruction = &procedure.instructionAtIndex(insIndex);
482  leaders[instruction->address().location()] = instruction;
483  } else {
484  return indirectJump; // end of procedure.
485  }
486  break;
487  }
488  }
489  if (increase) {
490  insIndex++;
491  }
492  }
493  return indirectJump;
494 }
495 
496 /**
497  * Split Procedure into the set of basic blocks.
498  *
499  * @param leaders Set of instructions which starts basic block.
500  * @param procedure Procedure that is analysed.
501  */
502 void
504  InstructionAddressMap& leaders,
505  const Procedure& procedure) {
506 
507  // leaders are not sorted so to create basic blocks we need
508  // to sort beginning addresses of blocks
509  std::set<InstructionAddress> iAddresses;
510  iAddresses = MapTools::keys<InstructionAddress>(leaders);
512  sortedLeaders(iAddresses.begin(), iAddresses.end());
513  sort(sortedLeaders.begin(), sortedLeaders.end());
514  int blockSize = sortedLeaders.size();
515  if (blockSize > 0) {
516  int i;
517  for (i = 0; i < blockSize - 1; i++) {
518  createBlock(
519  procedure.instructionAt(sortedLeaders[i]),
520  procedure.instructionAt(sortedLeaders[i+1] - 1));
521  }
522  createBlock(
523  procedure.instructionAt(sortedLeaders[i]),
524  procedure.lastInstruction());
525  }
526 }
527 /**
528  * Internal helper. Create a basic block.
529  *
530  * Given the first and last instructions of a basic block, create a new basic
531  * block of graph. It is assumed that the graph does not have a basic block
532  * for the given pair of instructions yet. If such a block exists,
533  * this method aborts.
534  *
535  * @param leader The first instruction of the basic block to create.
536  * @param endBlock The last instruction of the basic block to create.
537  * @return The created basic block node.
538  */
541  Instruction& leader,
542  const Instruction& endBlock) {
543 
544  InstructionAddress blockStart = leader.address().location();
545  InstructionAddress blockEnd = endBlock.address().location();
546 
547  CodeSnippet& proc = leader.parent();
548 
549  unsigned int blockStartIndex = blockStart - proc.startAddress().location();
550  unsigned int blockEndIndex = blockEnd - proc.startAddress().location();
551 
552  if (MapTools::containsKey(blocks_, blockStart)) {
553  throw InvalidData(
554  __FILE__, __LINE__, __func__,
555  "Basic block with given start address already exists!");
556  }
557  if (blockStart > blockEnd) {
558  throw InvalidData(
559  __FILE__, __LINE__, __func__,
560  "Basic block start address is higher then it's end address!");
561  }
562 
563  BasicBlockNode* node = new BasicBlockNode(blockStart, blockEnd);
564 
565  for (unsigned int i = blockStartIndex; i <= blockEndIndex; i++) {
566  Instruction *newInstruction = proc.instructionAtIndex(i).copy();
567  node->basicBlock().add(newInstruction);
568  }
569 
570  addNode(*node);
571  // Create entry node and add edge from it into current BB
572  // if it's start is also start of procedure
573  if (leader.address().location() == startAddress_.location()){
574  BasicBlockNode* entry = new BasicBlockNode(0, 0, true);
575  addNode(*entry);
576  ControlFlowEdge* edge = new ControlFlowEdge;//(edgeCount());
577  connectNodes(*entry, *node, *edge);
578  }
579 
582  node->basicBlock().setTripCount(0); // 0 indicates unknown trip count
583 
584  if (leader.hasAnnotations(
586 
587  unsigned tripCount =
588  static_cast<unsigned>(
589  leader.annotation(
591  intValue());
592  if (tripCount > 0) {
593  node->basicBlock().setTripCount(tripCount);
594  }
595  }
596  }
597  blocks_[blockStart] = node;
598  return *node;
599 }
600 
601 /**
602  * Internal helper. Create a control flow edge between two basic blocks.
603  *
604  * Given the leader instructions of two basic blocks, create a new control
605  * flow edge connecting the blocks. The basic blocks are assumed to be
606  * already existing and added to the graph. If either basic block does not
607  * exist, this method aborts. A new edge is created even if the blocks are
608  * already connected. Thus, parallel edges are possible.
609  *
610  * @param iTail The first instruction of the tail basic block (from).
611  * @param iHead The first instruction of the head basic block (to).
612  * @param edgePredicate The value of an edge (true, false, normal, call)
613  * @param edgeType Defines if edge represents jump or call or fall-through,
614  * default jump
615  * @return The created control flow edge.
616  */
619  const Instruction& iTail,
620  const Instruction& iHead,
621  ControlFlowEdge::CFGEdgePredicate edgePredicate,
622  ControlFlowEdge::CFGEdgeType edgeType) {
623 
624  InstructionAddress sourceAddr = iTail.address().location();
625  InstructionAddress targetAddr = iHead.address().location();
626  if (!MapTools::containsKey(blocks_, sourceAddr)) {
627  if (Application::verboseLevel() >= 1) {
628  TCEString msg = (boost::format(
629  "Source instruction %d:%s\nDestination instruction %d:%s\n")
630  % Conversion::toString(sourceAddr)
632  % Conversion::toString(targetAddr)
633  % POMDisassembler::disassemble(iHead)).str();
634  Application::logStream() << msg;
635  }
636  throw InvalidData(
637  __FILE__, __LINE__, __func__,
638  "Source basic block is missing!");
639  }
640  if (!MapTools::containsKey(blocks_, targetAddr)) {
641  if (Application::verboseLevel() >= 1) {
642  TCEString msg =(boost::format(
643  "Source instruction %d:%s\nDestination instruction %d:%s\n")
644  % Conversion::toString(sourceAddr)
646  % Conversion::toString(targetAddr)
647  % POMDisassembler::disassemble(iHead)).str();
648  Application::logStream() << msg;
649  }
650  throw InvalidData(
651  __FILE__, __LINE__, __func__,
652  "Destination basic block is missing!");
653  }
654 
655  BasicBlockNode& blockSource(*blocks_[sourceAddr]);
656  BasicBlockNode& blockTarget(*blocks_[targetAddr]);
657 
658  ControlFlowEdge* theEdge;
659  theEdge = new ControlFlowEdge(edgePredicate, edgeType);
660 
661  if (edgeType == ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH) {
662  assert(blockSource.originalEndAddress() +1 ==
663  blockTarget.originalStartAddress());
664  }
665 
666  connectNodes(blockSource, blockTarget, *theEdge);
667  return *theEdge;
668 }
669 
670 /**
671  * Creates edges for direct jump (source is immediate value).
672  *
673  * @param leaders Set of beginnings of basic blocks
674  * @param leaderAddr Address of beginning of current basic block
675  * @param instruction Instruction to analyse (only one move in instruction)
676  * @param procedure Procedure we are working with
677  */
678 void
680  InstructionAddressMap& leaders,
681  const InstructionAddress& leaderAddr,
682  int insIndex, int cfMoveIndex,
683  const TTAProgram::Instruction& instructionTarget,
684  const TTAProgram::Procedure& procedure) {
685 
686  Instruction& instruction = procedure.instructionAtIndex(insIndex);
687  // find other jumps from same ins.
688  bool hasAnotherJump = hasInstructionAnotherJump(instruction, cfMoveIndex);
689  TTAProgram::Move& move = instruction.move(cfMoveIndex);
690  InstructionAddress targetAddr = instructionTarget.address().location();
691  if (!MapTools::containsKey(leaders, targetAddr)) {
692  throw InvalidData(
693  __FILE__, __LINE__, __func__,
694  "Target basic block of jump is missing!");
695  }
696 
697  if (!move.isUnconditional()) {
698  // if jump is conditional we consider guard
699  // if we add also fall-through edge to next block,
700  // for inverted value of guard
701  // no other jump in same BB.
702 
703  Instruction* iNext = NULL;
704  if (!hasAnotherJump) {
705  int nextIndex = findNextIndex(procedure, insIndex, cfMoveIndex);
706  if (nextIndex >= procedure.instructionCount()) {
707  throw InvalidData(
708  __FILE__, __LINE__, __func__,
709  (boost::format(
710  "Fall-through of jump missing:"
711  "Address: %d jump: %s\n")
712  % (procedure.startAddress().location() + insIndex)
713  % POMDisassembler::disassemble(instruction)).str());
714  }
715  iNext = &procedure.instructionAtIndex(nextIndex);
716  InstructionAddress nextAddr =
717  procedure.startAddress().location() + nextIndex;
718  if (!MapTools::containsKey(leaders, nextAddr)) {
719  throw InvalidData(
720  __FILE__, __LINE__, __func__,
721  "Fall through basic block is missing!");
722  }
723  }
724  if (move.guard().isInverted()) {
725  // jumps on !bool, fall-through on bool
727  *leaders[leaderAddr], instructionTarget,
729  if (iNext != NULL) {
731  *leaders[leaderAddr], *iNext,
734  }
735  } else {
737  *leaders[leaderAddr], instructionTarget,
739  if (iNext != NULL) {
741  *leaders[leaderAddr], *iNext,
744  }
745  }
746  } else {
747  createControlFlowEdge(*leaders[leaderAddr], instructionTarget);
748  }
749 }
750 
751 /**
752  * Tells whether an instruction has another jump in addition to the given.
753  *
754  * @param ins instruction to check
755  * @param moveIndex index of the move triggering the known jump.
756  */
757 bool
759  const Instruction& ins, int moveIndex) {
760  for (int i = 0; i < ins.moveCount(); i++) {
761  if (i != moveIndex && ins.move(i).isJump()) {
762  return true;
763  }
764  }
765  return false;
766 }
767 
768 
769 /**
770  * Creates edges for indirect jump (source is NOT immediate value).
771  *
772  * @param leaders Set of beginnings of basic blocks
773  * @param leaderAddr Address of beginning of current basic block
774  * @param dataCodeRellocations Rellocation information for targets of jump
775  * @param instruction Instruction to analyse (only one move in instruction)
776  * @param procedure Procedure we are working with
777  */
778 void
780  InstructionAddressMap& leaders,
781  const InstructionAddress& leaderAddr,
782  InstructionAddressMap& dataCodeRellocations,
783  int insIndex, int cfMoveIndex,
784  const TTAProgram::Procedure& procedure) {
785 
786  Instruction& instruction = procedure.instructionAtIndex(insIndex);
787  InstructionAddressMap::iterator dataCodeIterator =
788  dataCodeRellocations.begin();
789  bool hasAnotherJump = hasInstructionAnotherJump(instruction, cfMoveIndex);
790  TTAProgram::Move& move = instruction.move(cfMoveIndex);
791 
792  if (move.hasAnnotations(ProgramAnnotation::ANN_JUMP_TO_NEXT)) {
793  int nextIndex = findNextIndex(procedure, insIndex, cfMoveIndex);
794  if (nextIndex < procedure.instructionCount()) {
795  const Instruction& iNext = procedure.instructionAtIndex(nextIndex);
797  *leaders[leaderAddr], iNext,
799  }
800  else {
801  throw IllegalProgram(
802  __FILE__,__LINE__,__func__,
803  "Jump to next annotation without next instruction");
804  }
805  return;
806  }
807 
808  ControlFlowEdge::CFGEdgePredicate edgePredicate =
810  ControlFlowEdge::CFGEdgePredicate fallPredicate =
812  if (instruction.move(cfMoveIndex).isUnconditional() == false) {
813  if (instruction.move(cfMoveIndex).guard().isInverted()) {
814  edgePredicate = ControlFlowEdge::CFLOW_EDGE_FALSE;
815  fallPredicate = ControlFlowEdge::CFLOW_EDGE_TRUE;
816  } else {
817  edgePredicate = ControlFlowEdge::CFLOW_EDGE_TRUE;
818  fallPredicate = ControlFlowEdge::CFLOW_EDGE_FALSE;
819  }
820  }
821 
822  if (!instruction.move(cfMoveIndex).isUnconditional() &&
823  !hasAnotherJump) {
824  int nextIndex = findNextIndex(procedure, insIndex, cfMoveIndex);
825  InstructionAddress nextAddr =
826  procedure.startAddress().location() + nextIndex;
827  if (nextIndex >= procedure.instructionCount() ||
828  !MapTools::containsKey(leaders, nextAddr)) {
829  throw InvalidData(
830  __FILE__, __LINE__, __func__,
831  "Fall through basic block is missing!");
832  }
833  Instruction& iNext = procedure.instructionAtIndex(nextIndex);
835  *leaders[leaderAddr], iNext,fallPredicate,
837  }
838 
839  // Check if this jump is a return.
840  const Port* port =
841  &instruction.move(cfMoveIndex).source().port();
842 
843  if (dynamic_cast<const SpecialRegisterPort*>(port) != NULL ||
844  move.hasAnnotations(
845  ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN)) {
846  returnSources_.insert(
847  ReturnSource(leaderAddr, edgePredicate));
848  return;
849  }
850 
851  while (dataCodeIterator != dataCodeRellocations.end()) {
852  // Target of jump is reachable also from it's predecessor
853  // block, in case there is no unconditional jump at the end.
854  // If the end of previous BB is conditional jump it will be
855  // added elsewhere.
856  // Target is limited to present procedure, no interprocedural
857  // indirect jump for now.
859  *leaders[leaderAddr], *(*dataCodeIterator).second,
860  edgePredicate);
861  dataCodeIterator++;
862  }
863 }
864 
865 /**
866  * Finds the index of the next instruction after jump and delay slots
867  * in the procedure.
868  *
869  * Also checks for control flow moves in delay slots, and throws if found,
870  * or if the procedure ends before all delays slots.
871  *
872  * @param procedure procedure we are processing
873  * @param jumpInsIndex index of the jump inside in the procedure
874  * @param index of the jump move in the jump instruction.
875  */
876 unsigned int
878  const TTAProgram::Procedure& proc, int jumpInsIndex, int jumpMoveIndex) {
879  Instruction& instruction = proc.instructionAtIndex(jumpInsIndex);
880 
881  // POM allows mixed scheduled an unscheduled code, so each jump
882  // must check from machine how many delay slots it needs
883  FunctionUnit& unit = const_cast<FunctionUnit&>(
884  instruction.move(jumpMoveIndex).destination().functionUnit());
885  ControlUnit* control = dynamic_cast<ControlUnit*>(&unit);
886  if (control == NULL) {
887  throw ModuleRunTimeError(
888  __FILE__, __LINE__, __func__, (boost::format(
889  "Control flow move '%s' has destination unit %s, "
890  "not global control unit!")
891  % POMDisassembler::disassemble(instruction.move(jumpMoveIndex))
892  % unit.name()).str());
893  }
894  int delaySlots = control->delaySlots();
895  int nextIndex = jumpInsIndex + delaySlots + 1;
896  if (nextIndex > proc.instructionCount()) {
897  throw InvalidData(
898  __FILE__, __LINE__, __func__,
899  "Procedure ends before all delay slot instructions");
900  }
901  // Then check for control flow instructions inside delay slots.
902  for (int i = jumpInsIndex + 1; i < nextIndex; i++) {
903  Instruction &dsIns = proc.instructionAtIndex(i);
904  if (dsIns.hasControlFlowMove()) {
905  throw InvalidData(
906  __FILE__, __LINE__, __func__,
907  (boost::format(
908  "Control flow operation in delay slot"
909  " in %d! Instruction:\n%s")
910  % dsIns.address().location()
912  ).str());
913  }
914  }
915  return nextIndex;
916 }
917 
918 /**
919  * Adds artificial block named 'Exit' to the graph
920  */
921 void
923  BasicBlockNode* exit = new BasicBlockNode(0, 0, false, true);
924  addNode(*exit);
925 
926  // the actual code which inserts the exit on normal case.
927  for (ReturnSourceSet::iterator i = returnSources_.begin();
928  i != returnSources_.end(); i++) {
929 
930  InstructionAddress sourceAddr = i->first;
931  if (!MapTools::containsKey(blocks_, sourceAddr)) {
932  if (Application::verboseLevel() >= 1) {
933  TCEString msg = (
934  boost::format(
935  "Source instr %d:%s\nDestination instr %d:%s\n")
936  % Conversion::toString(sourceAddr)
937  ).str();
938  Application::logStream() << msg;
939  }
940  throw InvalidData(
941  __FILE__, __LINE__, __func__,
942  "Source basic block of edge to exit is missing!");
943  }
944  BasicBlockNode& blockSource(*blocks_[sourceAddr]);
945  ControlFlowEdge* theEdge =
947  connectNodes(blockSource, *exit, *theEdge);
948  }
949 
950  addExitFromSinkNodes(exit);
951 }
952 
954  BasicBlockNode* exitNode = new BasicBlockNode(0, 0, false, true);
955  addNode(*exitNode);
956 
957  for (auto blockSource: retSourceNodes) {
958  ControlFlowEdge* theEdge = new ControlFlowEdge;
959  connectNodes(*blockSource, *exitNode, *theEdge);
960  }
961 
963 }
964 
965 void
967 
968  // kludge needed for start and exit methods which do nto have ret inst.
969  for (int i = 0; i < nodeCount(); i++) {
970  BasicBlockNode& block(node(i));
971  if (outDegree(block) == 0 && exitNode != &block) {
975  connectNodes(block, *exitNode, *edge);
976  }
977  }
978 }
979 
980 /**
981  * Creates reversed underlying graph.
982  *
983  * Control Flow Graph has member graph_ which stores actual data.
984  * This function returns reversed graph_ (edge directions changed).
985  *
986  * @return Reversed underlying graph.
987  */
991  return *R;
992 }
993 
994 /**
995  * Return the entry node of the graph.
996  *
997  * @return The entry node of the graph.
998  * @exception InstanceNotFound if the graph does not have a entry node.
999  * @exception InvalidData if the graph has multiple nodes that are
1000  * recognised as entry nodes.
1001  */
1004  BasicBlockNode* result = NULL;
1005  bool found = false;
1006  for (int i = 0; i < nodeCount(); i++) {
1007  if (inDegree(node(i)) == 0) {
1008  // sanity check
1009  if (!static_cast<BasicBlockNode&>(node(i)).isEntryBB()) {
1010  // probably the entry node is not present
1011  // or there are more nodes which are not reachable from
1012  // entry nodes... likely caused by frontend not doing
1013  // any of -O{1,2} optimizations (in case of gcc)
1014  continue;
1015  }
1016  if (found == true) {
1017  throw InvalidData(
1018  __FILE__, __LINE__, __func__,
1019  "Corrupted graph. Found multiple entry nodes.");
1020  }
1021  result = &node(i);
1022  found = true;
1023  }
1024  }
1025  if (found == false || result == NULL) {
1026  TCEString errorMsg("Graph does not have entry node.");
1027  throw InvalidData(__FILE__, __LINE__, __func__, errorMsg);
1028  }
1029  return *result;
1030 }
1031 
1035  if (entrySucc.size() != 1) {
1036  throw InvalidData(__FILE__,__LINE__,__func__,
1037  "Entry node has not exactly one successor");
1038  }
1039  BasicBlockNode* firstNode = *entrySucc.begin();
1040  if (!firstNode->isNormalBB()) {
1041  throw InvalidData(__FILE__,__LINE__,__func__,
1042  "Successor of entry node is not normal bb");
1043  }
1044  return *firstNode;
1045 }
1046 
1047 
1048 /**
1049  * Return the stop/exit node of the graph.
1050  *
1051  *
1052  * @return The stop node of the graph.
1053  * @exception InstanceNotFound if the graph does not have a stop node.
1054  * @exception InvalidData if the graph has multiple nodes that are
1055  * recognised as stop nodes.
1056  */
1059 
1060  BasicBlockNode* result = NULL;
1061  bool found = false;
1062  bool unlinkedExitNode = false;
1063 
1064  for (int i = 0; i < nodeCount(); i++) {
1065  if (outDegree(node(i)) == 0) {
1066  // sanity check
1067  if (!static_cast<BasicBlockNode&>(node(i)).isExitBB()) {
1068  // probably the stop node is not present
1069  unlinkedExitNode = true;
1070  continue;
1071  }
1072  if (found == true) {
1073  throw InvalidData(
1074  __FILE__, __LINE__, __func__,
1075  "Corrupted graph. Found multiple exit nodes.");
1076  }
1077  result = &node(i);
1078  found = true;
1079  }
1080  }
1081  if (found == false || result == NULL || unlinkedExitNode == true) {
1082  TCEString errorMsg("Graph does not have exit node.");
1083  throw InvalidData(__FILE__, __LINE__, __func__, errorMsg);
1084  }
1085  return *result;
1086 }
1087 
1088 /**
1089  * Create a "false" edge between Entry and Exit. Replaces edges from
1090  * Entry to graph with "true" edges.
1091  * This is not strictly part of Control Flow Graph, it is used
1092  * during construction of control dependencies.
1093  *
1094  * The entry node is connected to exit node
1095  */
1096 void
1098  // edge from Entry to first "real" node of CFG needs to be true
1099  // artificial edge to Exit node needs to be false
1100  BasicBlockNode& entry = entryNode();
1101  std::vector<std::pair<BasicBlockNode*, int> > fromEntry;
1102  for (int i = 0; i < outDegree(entry); i++) {
1103  fromEntry.push_back(
1104  std::pair<BasicBlockNode*, int>(
1105  &headNode(outEdge(entry,i)), outEdge(entry,i).edgeID()));
1106  }
1107  for (unsigned int i = 0; i < fromEntry.size(); i++) {
1108  disconnectNodes(entry, *(fromEntry[i].first));
1111  connectNodes(entry, *(fromEntry[i].first), *edge);
1112  }
1116 }
1117 
1118 /**
1119  * Remove a "false" edge between Entry and Exit after control
1120  * dependencies are created.
1121  *
1122  * The entry node is connected to exit
1123  */
1124 void
1126  // Edge from Entry to Exit node of CFG needs to be removed
1127  // it is not really control flow edge
1128  BasicBlockNode& entry = entryNode();
1129  std::vector<std::pair<BasicBlockNode*, int> > fromEntry;
1130  for (int i = 0; i < outDegree(entry); i++) {
1131  fromEntry.push_back(
1132  std::pair<BasicBlockNode*, int>(
1133  &headNode(outEdge(entry,i)), outEdge(entry,i).edgeID()));
1134  }
1135  for (unsigned int i = 0; i < fromEntry.size(); i++) {
1136  disconnectNodes(entry, *(fromEntry[i].first));
1137  ControlFlowEdge* edge = new ControlFlowEdge; //(fromEntry[i].second);
1138  connectNodes(entry, *(fromEntry[i].first), *edge);
1139  }
1141 }
1142 
1143 /**
1144  * Returns a name of procedure the graph represents taken from original POM
1145  * object.
1146  *
1147  * @return The name of procedure as a string
1148  */
1149 TCEString
1151  return procedureName_;
1152 }
1153 
1154 /**
1155  * Returns alignment value copied from original POM procedure
1156  *
1157  * @return The alignment of procedure.
1158  */
1159 int
1161  return alignment_;
1162 }
1163 
1164 /**
1165  * Returns a pointer to the POM Program object procedure was part
1166  * of in POM.
1167  *
1168  * @return The pointer to POM Program
1169  */
1172  return program_;
1173 }
1174 
1175 /**
1176  * Helper function to find target address of a jump in case source of jump
1177  * is immediate register or general purpose register.
1178  *
1179  * @param leaders Starting instructions of all basic blocks
1180  * @param leaderAddr Address of a first instruction of present Basic Block
1181  * @param dataCodeRellocations Read from POM, the possible targets of indirect
1182  * jumps are in data code rellocation information
1183  * @param instruction Currect instruction containing jump
1184  * @param procedure The reference to current procedure
1185  * @param moveIndex Index of move with jump in current instruction
1186  * @note Abort when the source of jump is immediateregister and no write to
1187  * such register is found in same basic block.
1188  */
1189 void
1191  InstructionAddressMap& leaders,
1192  const InstructionAddress& leaderAddr,
1193  InstructionAddressMap& dataCodeRellocations,
1194  const TTAProgram::Procedure& procedure,
1195  int insIndex,
1196  int moveIndex) {
1197 
1198  const Instruction& instruction = procedure.instructionAtIndex(insIndex);
1199  if (instruction.move(moveIndex).source().isInstructionAddress()) {
1200  Move* tmp = &instruction.move(moveIndex);
1201  directJump(
1202  leaders, leaderAddr, insIndex, moveIndex,
1204  procedure);
1205  return;
1206  }
1207  if (instruction.move(moveIndex).source().isImmediateRegister() ||
1208  instruction.move(moveIndex).source().isGPR()) {
1209  const Instruction* iPrev = &instruction;
1210  TTAProgram::TerminalRegister* sourceTerm =
1211  dynamic_cast<TTAProgram::TerminalRegister*>(
1212  &instruction.move(moveIndex).source());
1213  while (iPrev->address().location() > leaderAddr) {
1214  iPrev = &procedure.previousInstruction(*iPrev);
1215  const TTAProgram::TerminalRegister* destTerm = NULL;
1216  if (sourceTerm->isImmediateRegister()) {
1217  for (int j = 0; j < iPrev->immediateCount(); j++){
1218  destTerm =
1219  dynamic_cast<const TTAProgram::TerminalRegister*>(
1220  &iPrev->immediate(j).destination());
1221  TTAProgram::Immediate* tmpImm = &iPrev->immediate(j);
1222  if (sourceTerm->equals(*destTerm)) {
1223  directJump(
1224  leaders, leaderAddr, insIndex, moveIndex,
1225  tmpImm->value().instructionReference().
1226  instruction(),
1227  procedure);
1228  return;
1229  }
1230  }
1231  }
1232  if (sourceTerm->isGPR()) {
1233  for (int j = 0; j < iPrev->moveCount(); j++){
1234  destTerm =
1235  dynamic_cast<const TTAProgram::TerminalRegister*>(
1236  &iPrev->move(j).destination());
1237  if (destTerm == NULL) {
1238  continue;
1239  }
1240  TTAProgram::Terminal* tmpTerm = &iPrev->move(j).source();
1241  if (sourceTerm->equals(*destTerm)) {
1242  if (tmpTerm->isInstructionAddress()){
1243  directJump(
1244  leaders, leaderAddr, insIndex, moveIndex,
1245  tmpTerm->instructionReference().instruction(),
1246  procedure);
1247  return;
1248  }
1249  if (tmpTerm->isGPR() ||
1250  tmpTerm->isImmediateRegister()) {
1251  sourceTerm =
1252  dynamic_cast<TTAProgram::TerminalRegister*>(
1253  tmpTerm);
1254  break;
1255  }
1256  if (tmpTerm->isFUPort()) {
1257  indirectJump(
1258  leaders, leaderAddr,
1259  dataCodeRellocations, insIndex, moveIndex,
1260  procedure);
1261  return;
1262  }
1263  }
1264  }
1265  }
1266  }
1267  } else {
1268  if (instruction.move(moveIndex).source().isImmediateRegister()) {
1269  throw InvalidData(
1270  __FILE__, __LINE__, __func__,
1271  "Source of immediate write not found!");
1272  }
1273  indirectJump(
1274  leaders, leaderAddr, dataCodeRellocations,
1275  insIndex, moveIndex, procedure);
1276  return;
1277  }
1278 }
1279 
1280 /**
1281  * Returns basic statistics about control flow graph as a string.
1282  *
1283  * @return String with basic statistics about control flow graph.
1284  */
1285 TCEString
1287  const CFGStatistics& stats = statistics();
1288 
1289  TCEString result = "";
1290  result += (boost::format("Procedure '%s' has %d moves, %d immediate"
1291  " writes, %d instructions and %d bypassed moves in %d basic blocks.")
1292  % procedureName() % stats.moveCount() % stats.immediateCount()
1293  % stats.instructionCount() % stats.bypassedCount()
1294  % stats.normalBBCount()).str();
1295  result += (boost::format("\n\tLargest basic block has %d moves, %d"
1296  " immediate writes, %d instructions and %d bypassed moves.\n")
1297  % stats.maxMoveCount() % stats.maxImmediateCount()
1298  % stats.maxInstructionCount() % stats.maxBypassedCount()).str();
1299  return result;
1300 }
1301 
1302 /**
1303  * Returns basic statistics about control flow graph in statistic object.
1304  *
1305  * @return Object with basic statistics about control flow graph.
1306  */
1307 const CFGStatistics&
1309 
1310  CFGStatistics* result = new CFGStatistics;
1311  int moveCount = 0;
1312  int immediateCount = 0;
1313  int instructionCount = 0;
1314  int bypassCount = 0;
1315  int normalBBCount = 0;
1316  int maxMoveCount = 0;
1317  int immediateCountInMax = 0;
1318  int instructionCountInMax = 0;
1319  int bypassCountInMax = 0;
1320  for (int i = 0; i < nodeCount(); i++) {
1321  if (node(i).isNormalBB()) {
1322  const TTAProgram::BasicBlockStatistics& stats =
1323  node(i).statistics();
1324  moveCount += stats.moveCount();
1325  immediateCount += stats.immediateCount();
1326  instructionCount += stats.instructionCount();
1327  bypassCount += stats.bypassedCount();
1328  normalBBCount++;
1329  if (stats.moveCount() > maxMoveCount) {
1330  maxMoveCount = stats.moveCount();
1331  immediateCountInMax = stats.immediateCount();
1332  instructionCountInMax = stats.instructionCount();
1333  bypassCountInMax = stats.bypassedCount();
1334  }
1335  }
1336  }
1337 
1338  result->setMoveCount(moveCount);
1339  result->setImmediateCount(immediateCount);
1340  result->setInstructionCount(instructionCount);
1341  result->setBypassedCount(bypassCount);
1342  result->setNormalBBCount(normalBBCount);
1343  result->setMaxMoveCount(maxMoveCount);
1344  result->setMaxInstructionCount(instructionCountInMax);
1345  result->setMaxImmediateCount(immediateCountInMax);
1346  result->setMaxBypassedCount(bypassCountInMax);
1347  return *result;
1348 }
1349 
1350 
1351 /**
1352  * Finds a node where control falls thru from the give node.
1353  *
1354  * @param bbn basic block node whose successor we are searching
1355  * @return node where control falls thru from given node or NULL if not exist.
1356  */
1359  if (bbn.isExitBB()) {
1360  return NULL;
1361  }
1362 
1363  EdgeSet oEdges = outEdges(bbn);
1364  for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
1365  if ((*i)->isFallThroughEdge() || (*i)->isCallPassEdge()) {
1366  return &headNode(**i);
1367  }
1368  }
1369  return NULL;
1370 }
1371 
1372 /**
1373  * Finds a node where control falls thru to the give node.
1374  *
1375  * @param bbn basic block node whose successor we are searching
1376  * @return node where control falls thru from given node or NULL if not exist.
1377  */
1380  if (bbn.isEntryBB()) {
1381  return NULL;
1382  }
1383 
1384  EdgeSet iEdges = inEdges(bbn);
1385  for (auto i: iEdges) {
1386  if (i->isFallThroughEdge() || i->isCallPassEdge()) {
1387  return &tailNode(*i);
1388  }
1389  }
1390  return NULL;
1391 }
1392 
1393 
1394 /**
1395  * Returns true if given basic blocks has a predecessor which
1396  * falls thru to it.
1397  *
1398  * @param bbn bbn to check for fall-thru predecessors
1399  * @return if control can fall-thru to this BB.
1400  */
1402  EdgeSet iEdges = inEdges(bbn);
1403  for (EdgeSet::iterator i = iEdges.begin(); i != iEdges.end(); i++) {
1404  if ((*i)->isFallThroughEdge() || (*i)->isCallPassEdge()) {
1405  return true;
1406  }
1407  }
1408  return false;
1409 }
1410 
1411 /**
1412  * Does a breadth first search to find all reachable nodes.
1413  */
1416  NodeSet queuedBBs;
1417  NodeSet processedBBs;
1418 
1420  AssocTools::append(firstBBs,queuedBBs);
1421 
1422  while (queuedBBs.size() != 0) {
1423  BasicBlockNode& current = **queuedBBs.begin();
1424  if (current.isNormalBB()) {
1425  processedBBs.insert(&current);
1426  NodeSet succs = successors(current);
1427  for (NodeSet::iterator i = succs.begin(); i != succs.end(); i++) {
1428  if (!AssocTools::containsKey(processedBBs,*i)) {
1429  queuedBBs.insert(*i);
1430  }
1431  }
1432  processedBBs.insert(&current);
1433  }
1434  queuedBBs.erase(&current);
1435  }
1436  return processedBBs;
1437 }
1438 
1439 /**
1440  * Copies the CFG into a procedure.
1441  *
1442  * Clears the procedure and replaces all instructions in it with ones
1443  * in CFG. Tries to get rid of some unnecessary jumps.
1444  *
1445  * @param proc procedure where the copy the cfg.
1446  */
1447 void
1450 
1451  // todo: make sure not indeterministic.
1452  // two-way maps between copied and in cfg instructions.
1453  typedef std::map<TTAProgram::Instruction*,TTAProgram::Instruction*>
1454  InsMap;
1455  InsMap copiedInsFromCFG;
1456 
1457  std::vector<Instruction*> oldInstructions;
1458 
1459  int jumpsRemoved = 0;
1461  assert(firstBBs.size() == 1);
1462  BasicBlockNode* firstBBN = *firstBBs.begin();
1463  BasicBlockNode* currentBBN = firstBBN;
1464 
1465  // fix refs to old first to point to first in cfg - later fixed to
1466  // first in program
1467  if (irm == NULL) {
1469  assert(irm != NULL);
1470  }
1471  if (!firstBBN->isNormalBB()) {
1472  std::cerr << "First Basic block is not normal basic block. "
1473  << "This is propably due function that is completely empty,"
1474  << " not containg even return jump. The cause of this "
1475  << "might be LLVM optimizing away code it considers dead."
1476  << std::endl
1477  << "Control flow graph written to empty_fn.dot"
1478  << std::endl;
1479  writeToDotFile("empty_fn.dot");
1480  }
1481  assert(firstBBN->isNormalBB());
1482 
1483  // procedure should not have any references.
1484  for (int i = 0; i < proc.instructionCount(); i++) {
1485  assert(!irm->hasReference(proc.instructionAtIndex(i)));
1486  }
1487 
1488  proc.clear();
1489 
1490  // find and queue reachable nodes
1491  NodeSet queuedNodes = findReachableNodes();
1492  NodeSet unreachableNodes = findUnreachableNodes(queuedNodes);
1493 
1494  // then loop as long as we have BBs which have not been written to
1495  // the procedure.
1496  while (currentBBN != NULL) {
1497  BasicBlockNode* nextNode = NULL;
1498  TTAProgram::BasicBlock& bb = currentBBN->basicBlock();
1499  // todo: if refs to skipped instructions, breaks?
1500 
1501  for (int i = 0; i < bb.skippedFirstInstructions(); i++) {
1502  Instruction& ins = bb.instructionAtIndex(i);
1503  if (irm->hasReference(ins)) {
1504  std::cerr << "\tSkipped inst has refs, proc: " << proc.name()
1505  << " index: " << i << std::endl;
1506  writeToDotFile("skipped_has_ref.dot");
1507  PRINT_VAR(bb.toString());
1508  }
1509  assert(!irm->hasReference(ins));
1510  }
1511 
1512  // copy instructions of a BB to procedure.
1513  for (int i = bb.skippedFirstInstructions();
1514  i < bb.instructionCount(); i++) {
1515  Instruction* ins = &bb.instructionAtIndex(i);
1516  Instruction* copiedIns = ins->copy();
1517  copiedInsFromCFG[ins] = copiedIns;
1518 
1519  // CodeSnippet:: is a speed optimization here.
1520  // only later fix the addresses of followind functions.
1521  proc.CodeSnippet::add(copiedIns);
1522  }
1523 
1524  queuedNodes.erase(currentBBN);
1525 
1526  // then start searching for the next node.
1527 
1528  // if has fall-turu-successor, select it so no need to add
1529  // extra jump
1530  BasicBlockNode* ftNode = fallThruSuccessor(*currentBBN);
1531  if (ftNode != NULL && ftNode->isNormalBB()) {
1532 
1533  if (queuedNodes.find(ftNode) == queuedNodes.end()) {
1534  std::cerr << "not-queued fall-thru: " << ftNode->toString()
1535  << " current: " << currentBBN->toString() <<
1536  std::endl;
1537  writeToDotFile("copyToProcedureFallThruBBNotQueued.dot");
1538  }
1539  // must not be already processed.
1540  assert(queuedNodes.find(ftNode) != queuedNodes.end());
1541  currentBBN = ftNode;
1542  continue;
1543  }
1544 
1545  // Select some node, preferably successors without ft-preds
1546  // The jump can then be removed.
1547  EdgeSet oEdges = outEdges(*currentBBN);
1548  for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
1549  ControlFlowEdge& e = **i;
1550  BasicBlockNode& head = headNode(e);
1551  if (!hasFallThruPredecessor(head) && head.isNormalBB() &&
1552  queuedNodes.find(&head) != queuedNodes.end()) {
1553  // try to remove the jump as it's jump to the next BB.
1555  proc, head.basicBlock().firstInstruction(),
1556  proc.instructionCount() -
1558  if (rjd != JUMP_NOT_REMOVED) {
1559  jumpsRemoved++;
1560  // if BB got empty,
1561  // move refs to beginning of the next BB.
1562  if (rjd == LAST_ELEMENT_REMOVED) {
1563  Instruction& ins = bb.instructionAtIndex(0);
1564  if (irm->hasReference(ins)) {
1565  irm->replace(
1566  ins, head.basicBlock().instructionAtIndex(
1567  head.basicBlock().
1568  skippedFirstInstructions()));
1569  }
1570  }
1571  // we removed a jump so convert the jump edge into
1572  // fall-through edge.
1573  ControlFlowEdge* ftEdge = new ControlFlowEdge(
1574  e.edgePredicate(),
1576  removeEdge(e);
1577  connectNodes(*currentBBN, head, *ftEdge);
1578  nextNode = &head;
1579  break;
1580  }
1581  }
1582  }
1583 
1584  // need to select SOME node as successor.
1585  // first without ft-predecessor usually is a good candidate.
1586  // smarter heuristic does not seem to help at all.
1587  // try to select
1588  if (nextNode == NULL) {
1589  bool ftPred = false;
1590  for (NodeSet::iterator i = queuedNodes.begin();
1591  i != queuedNodes.end(); i++) {
1592  if (!hasFallThruPredecessor(**i)) {
1593  nextNode = *i;
1594  break;
1595  } else {
1596  ftPred = true;
1597  }
1598  }
1599 
1600  // unreachable node having ft may have prevented us from
1601  // managing some node whose fall-thru succs prevent
1602  // futher nodes. try to select some unreached node.
1603  if (nextNode == NULL && ftPred) {
1604  for (NodeSet::iterator i = unreachableNodes.begin();
1605  i != unreachableNodes.end(); i++) {
1606  if (fallThruSuccessor(**i) != NULL) {
1607  nextNode = *i;
1608  unreachableNodes.erase(*i);
1609  break;
1610  }
1611  }
1612  }
1613 
1614  // did not help. we cannot select node which has
1615  // fall-thru predecessor.
1616  if (nextNode == NULL && ftPred) {
1618  "CopyToProcedure_multiple_fall_thorough_nodes.dot");
1619  assert(0 && "CFG may have multiple fall-thorough nodes!");
1620  }
1621  }
1622  currentBBN = nextNode;
1623  }
1624 
1625  // now all instructions are copied.
1626 
1627  // this can happen in indeterministic order.
1628  // but it should not cause any indeterministicity
1629  // effects on the schedule.
1630 
1631  // Update refs from cfg into final program
1632  // only works for refs
1633  for (InsMap::iterator i = copiedInsFromCFG.begin();
1634  i != copiedInsFromCFG.end(); i++) {
1635  std::pair<Instruction*,Instruction*> insPair = *i;
1636  if (irm->hasReference(*insPair.first)) {
1637  irm->replace(*insPair.first, *insPair.second);
1638  }
1639  }
1640 
1641  // move the following procedures to correct place
1642  if (proc.instructionCount() != 0 && proc.isInProgram()) {
1643  if (!(&proc == &proc.parent().lastProcedure())) {
1644  proc.parent().moveProcedure(
1645  proc.parent().nextProcedure(proc),
1646  proc.instructionCount());
1647  }
1648  }
1649 
1650  // make sure no refs to dead code?
1651 /*
1652  for (NodeSet::iterator i = unreachableNodes.begin();
1653  i != unreachableNodes.end(); i++) {
1654  BasicBlockNode& bbn = **i;
1655  if (bbn.isNormalBB()) {
1656  BasicBlock& bb = bbn.basicBlock();
1657  for (int i = 0; i < bb.instructionCount();i++) {
1658  Instruction& ins = bb.instructionAtIndex(i);
1659  assert(!irm.hasReference(ins));
1660  }
1661  }
1662  }
1663 */
1664 }
1665 
1666 
1667 /**
1668  * Copies the CFG into an LLVM MachineFunction.
1669  *
1670  * Assumes an operation triggered target and that all scheduler restrictions
1671  * to produce valid code for such an target have been enabled in ADF while
1672  * producing the schedule.
1673  *
1674  * @param mf The MachineFunction where to copy the cfg.
1675  * @param irm InstructionReferenceManager for resolving instruction refs.
1676  */
1677 
1678 void
1680  llvm::MachineFunction& mf,
1682 
1683  // todo: make sure not indeterministic.
1684  // two-way maps between copied and in cfg instructions.
1685  typedef std::map<TTAProgram::Instruction*,TTAProgram::Instruction*>
1686  InsMap;
1687  InsMap copiedInsFromCFG;
1688 
1689  std::vector<Instruction*> oldInstructions;
1690 
1692  assert(firstBBs.size() == 1);
1693  BasicBlockNode* firstBBN = *firstBBs.begin();
1694  BasicBlockNode* currentBBN = firstBBN;
1695 
1696  // fix refs to old first to point to first in cfg - later fixed to
1697  // first in program
1698  if (irm == NULL) {
1700  assert(irm != NULL);
1701  }
1702  assert(firstBBN->isNormalBB());
1703 
1704 #if 0
1705  // procedure should not have any references.
1706  for (int i = 0; i < proc.instructionCount(); i++) {
1707  assert(!irm->hasReference(proc.instructionAtIndex(i)));
1708  }
1709 #endif
1710 
1711  while (!mf.empty())
1712  mf.erase(mf.begin());
1713 
1714  // find and queue reachable nodes
1715  NodeSet queuedNodes = findReachableNodes();
1716  NodeSet unreachableNodes;
1717 
1718  // find dead nodes
1719  for (int i = 0; i < nodeCount(); i++) {
1720  BasicBlockNode& n = node(i);
1721  if (!AssocTools::containsKey(queuedNodes,&n) &&
1722  n.isNormalBB()) {
1723  unreachableNodes.insert(&n);
1724  }
1725  }
1726 
1727  /// This loop now only creates empty basic blocks in same order as they were
1728  /// transfered from LLVM to POM previously.
1729  /// Actuall copying of the content is done afterwords.
1730  while (currentBBN != NULL) {
1731  BasicBlockNode* nextNode = NULL;
1732  TTAProgram::BasicBlock& bb = currentBBN->basicBlock();
1733 
1734  /// This will create MachineBasicblock corresponding to BB if it does
1735  /// not exists already.
1736  getMBB(mf, bb);
1737 
1738  queuedNodes.erase(currentBBN);
1739 
1740  // then start searching for the next node.
1741 
1742  // if has fall-thru-successor, select it so no need to add
1743  // extra jump
1744  BasicBlockNode* ftNode = fallThruSuccessor(*currentBBN);
1745  if (ftNode != NULL && ftNode->isNormalBB()) {
1746 
1747  if (queuedNodes.find(ftNode) == queuedNodes.end()) {
1748  std::cerr << "not-queued fall-thru: " << ftNode->toString()
1749  << " current: " << currentBBN->toString() <<
1750  std::endl;
1751  writeToDotFile("copyToProcedureFallThruBBNotQueued.dot");
1752  }
1753  // must not be already processed.
1754  assert(queuedNodes.find(ftNode) != queuedNodes.end());
1755  currentBBN = ftNode;
1756  continue;
1757  }
1758 
1759  // Select some node, preferably successors without ft-preds
1760  // The jump can then be removed.
1761  EdgeSet oEdges = outEdges(*currentBBN);
1762 
1763  // need to select SOME node as successor.
1764  // first without ft-predecessor usually is a good candidate.
1765  // smarter heuristic does not seem to help at all.
1766  // try to select
1767  if (nextNode == NULL) {
1768  bool ftPred = false;
1769  for (NodeSet::iterator i = queuedNodes.begin();
1770  i != queuedNodes.end(); i++) {
1771  if (!hasFallThruPredecessor(**i)) {
1772  nextNode = *i;
1773  break;
1774  } else {
1775  ftPred = true;
1776  }
1777  }
1778 
1779  // unreachable node having ft may have prevented us from
1780  // managing some node whose fall-thru succs prevent
1781  // futher nodes. try to select some unreached node.
1782  if (nextNode == NULL && ftPred) {
1783  for (NodeSet::iterator i = unreachableNodes.begin();
1784  i != unreachableNodes.end(); i++) {
1785  if (fallThruSuccessor(**i) != NULL) {
1786  nextNode = *i;
1787  unreachableNodes.erase(*i);
1788  break;
1789  }
1790  }
1791  }
1792 
1793  // did not help. we cannot select node which has
1794  // fall-thru predecessor.
1795  if (nextNode == NULL && ftPred) {
1797  "CopyToProcedure_multiple_fall_thorough_nodes.dot");
1798  assert(0 && "CFG may have multiple fall-thorough nodes!");
1799  }
1800  }
1801  currentBBN = nextNode;
1802  }
1803 
1804  // now all instructions are copied.
1805 
1806  // this can happen in indeterministic order.
1807  // but it should not cause any indeterministicity
1808  // effects on the schedule.
1809 
1810  // Update refs from cfg into final program
1811  // only works for refs
1812  // TODO: Is this really necessary or usefull here?
1813  for (InsMap::iterator i = copiedInsFromCFG.begin();
1814  i != copiedInsFromCFG.end(); i++) {
1815  std::pair<Instruction*,Instruction*> insPair = *i;
1816  if (irm->hasReference(*insPair.first)) {
1817  irm->replace(*insPair.first, *insPair.second);
1818  }
1819  }
1820 
1821  /// Fill in created machine basic blocks with machine instructions
1822  /// based on corresponding basic blocks.
1823  unsigned int nCount = nodeCount();
1824  for (unsigned int j = 0; j < nCount; j++) {
1826  llvm::MachineBasicBlock* mbb = &getMBB(mf, bb);
1827  buildMBBFromBB(*mbb, bb);
1828  }
1829 
1830  /// Add the dummy instructions denoting labels to instructions
1831  /// that are not basic block starts. This is only for the SPU's
1832  /// branch hint instructions at the moment. It instantiates
1833  /// an LLVM/SPU-backend-specific dummy instruction HBR_LABEL at
1834  /// the moment.
1835  for (std::set<std::pair<ProgramOperationPtr, llvm::MCSymbol*> >::const_iterator i =
1836  tpos_.begin(); i != tpos_.end(); ++i) {
1837  ProgramOperationPtr po = (*i).first;
1838  llvm::MCSymbol* symbol = (*i).second;
1839  assert(programOperationToMIMap_.find(po.get()) != programOperationToMIMap_.end());
1840  llvm::MachineInstr* mi = programOperationToMIMap_[po.get()];
1841  assert(mi != NULL);
1842  const llvm::TargetInstrInfo& tii =
1843  *mf.getTarget().getSubtargetImpl(mf.getFunction())->getInstrInfo();
1844  const llvm::MCInstrDesc& tid =
1845  findLLVMTargetInstrDesc("HBR_LABEL", tii);
1846  llvm::MachineInstr* labelInstruction =
1847  mf.CreateMachineInstr(tid, llvm::DebugLoc());
1848  labelInstruction->addOperand(
1849  llvm::MachineOperand::CreateMCSymbol(symbol));
1850  mi->getParent()->insert(
1851  llvm::MachineBasicBlock::instr_iterator (mi), labelInstruction);
1852  }
1853  tpos_.clear();
1854  programOperationToMIMap_.clear();
1855  /// Based on CFG edges, add successor information to the generated
1856  /// machine function.
1857  unsigned int eCount = edgeCount();
1858  for (unsigned int i = 0; i < eCount; i++) {
1859  ControlFlowEdge& testEdge = edge(i);
1860  if (!headNode(testEdge).isNormalBB() ||
1861  !tailNode(testEdge).isNormalBB())
1862  continue;
1863 
1864  llvm::MachineBasicBlock& hNode =
1865  getMBB(mf, headNode(testEdge).basicBlock());
1866  llvm::MachineBasicBlock& tNode =
1867  getMBB(mf, tailNode(testEdge).basicBlock());
1868  if (hNode.isSuccessor(&tNode))
1869  continue;
1870  tNode.addSuccessor(&hNode);
1871  }
1872 
1873 }
1874 
1875 //#define DEBUG_POM_TO_MI
1876 
1877 /**
1878  * Finds the TargetInstrDesc for the given LLVM instruction name.
1879  */
1880 const llvm::MCInstrDesc&
1882  TCEString name,
1883  const llvm::MCInstrInfo& tii) const {
1884  for (unsigned opc = 0; opc < tii.getNumOpcodes(); ++opc) {
1885  if (name.ciEqual(tii.getName(opc).str())) {
1886  return tii.get(opc);
1887  }
1888  }
1889  abortWithError(TCEString("Could not find ") << name << " in the TII.");
1890 }
1891 
1892 void
1894  llvm::MachineBasicBlock& mbb,
1895  const TTAProgram::BasicBlock& bb) const {
1896 
1897 #ifdef DEBUG_POM_TO_MI
1899  << "TTA instructions:" << std::endl
1900  << bb.toString() << std::endl << std::endl
1901  << "OTA instructions:" << std::endl;
1902 #endif
1903 
1904  /* Find the target machine from an instruction link. Ugly,
1905  should probably pass it as a parameter instead. */
1906  const TTAMachine::Machine* mach = NULL;
1907  for (int i = bb.skippedFirstInstructions(); i < bb.instructionCount();
1908  ++i) {
1909  const TTAProgram::Instruction& instr =
1910  bb.instructionAtIndex(i);
1911  if (!instr.isNOP()) {
1912  mach = instr.move(0).bus().machine();
1913  break;
1914  }
1915  }
1916  if (mach == NULL)
1917  return; // The BB has only NOPs. Empty MBB is correct already.
1918 
1919  // the order of function unit operations in the instruction bundle
1920  typedef std::vector<const TTAMachine::FunctionUnit*> BundleOrderIndex;
1921  BundleOrderIndex bundleOrder;
1922 
1923  // Currently the bundle order is hard coded to the order of appearance
1924  // in the ADF file.
1925  for (int fuc = 0; fuc < mach->functionUnitNavigator().count(); ++fuc) {
1927  bundleOrder.push_back(fu);
1928  }
1929 
1930  for (int i = bb.skippedFirstInstructions(); i < bb.instructionCount();
1931  ++i) {
1932  const TTAProgram::Instruction& instr =
1933  bb.instructionAtIndex(i);
1934  // First collect all started operations at this cycle
1935  // on each FU.
1936  typedef std::map<const TTAMachine::FunctionUnit*,
1937  const TTAMachine::HWOperation*> OpsMap;
1938  OpsMap startedOps;
1939  typedef std::map<const TTAMachine::FunctionUnit*,
1940  ProgramOperationPtr> POMap;
1941  POMap startedPOs;
1942  for (int m = 0; m < instr.moveCount(); ++m) {
1943  const TTAProgram::Move& move = instr.move(m);
1944  if (move.isTriggering()) {
1946  dynamic_cast<TTAProgram::TerminalFUPort&>(
1947  move.destination());
1948  startedOps[&move.destination().functionUnit()] =
1949  tfup.hwOperation();
1950  startedPOs[&move.destination().functionUnit()] =
1951  tfup.programOperation();
1952  }
1953  }
1954 
1955  // in OTAs with data hazard detection, we do not need to emit
1956  // completely empty instruction bundles at all
1957  if (startedOps.size() == 0)
1958  continue;
1959 
1960  typedef std::map<const TTAMachine::HWOperation*,
1961  std::vector<TTAProgram::Terminal*> > OperandMap;
1962  OperandMap operands;
1963  // On a second pass through the moves we now should know the operand
1964  // numbers of all the moves. The result moves should be at an
1965  // instruction at the operation latency.
1966  OperationPool operations;
1967 
1968  for (OpsMap::const_iterator opsi = startedOps.begin();
1969  opsi != startedOps.end(); ++opsi) {
1970  const TTAMachine::HWOperation* hwOp = (*opsi).second;
1971  const Operation& operation =
1972  operations.operation(hwOp->name().c_str());
1973  // first find the outputs
1974  for (int out = 0; out < operation.numberOfOutputs(); ++out) {
1975  const TTAProgram::Instruction& resultInstr =
1976  bb.instructionAtIndex(i + hwOp->latency());
1977  for (int m = 0; m < resultInstr.moveCount(); ++m) {
1978  const TTAProgram::Move& move = resultInstr.move(m);
1979  // assume it's a register write, the potential (implicit)
1980  // bypass move is ignored
1981  if (move.source().isFUPort() &&
1982  &move.source().functionUnit() ==
1983  hwOp->parentUnit() &&
1984  (move.destination().isGPR() ||
1985  move.destination().isRA())) {
1986  operands[hwOp].push_back(&move.destination());
1987  }
1988  }
1989  }
1990  if ((std::size_t)operation.numberOfOutputs() !=
1991  operands[hwOp].size()) {
1992  PRINT_VAR(operation.name());
1993  PRINT_VAR(operands[hwOp].size());
1994  PRINT_VAR(operation.numberOfOutputs());
1995  assert((std::size_t)operation.numberOfOutputs() ==
1996  operands[hwOp].size());
1997  abort();
1998  }
1999 
2000  // then the inputs
2001  for (int input = 0; input < operation.numberOfInputs();
2002  ++input) {
2003  for (int m = 0; m < instr.moveCount(); ++m) {
2004  const TTAProgram::Move& move = instr.move(m);
2005  if (move.destination().isFUPort() &&
2006  &move.destination().functionUnit() ==
2007  hwOp->parentUnit() &&
2008  dynamic_cast<const TTAMachine::Port*>(
2009  hwOp->port(input + 1)) ==
2010  &move.destination().port()) {
2011  // if the result is forwarded (bypass), find the
2012  // result move
2013  if (move.source().isFUPort()) {
2014  for (int mm = 0; mm < instr.moveCount(); ++mm) {
2015  const TTAProgram::Move& move2 =
2016  instr.move(mm);
2017  if (move2.destination().isGPR() &&
2018  move2.source().isFUPort() &&
2019  &move2.source().port() ==
2020  &move.source().port()) {
2021  operands[hwOp].push_back(&move2.destination());
2022  }
2023  }
2024  } else {
2025  // otherwise assume it's not bypassed but
2026  // read from the RF
2027  operands[hwOp].push_back(&move.source());
2028  }
2029  }
2030  }
2031  }
2032 
2033  if ((std::size_t)operation.numberOfInputs() +
2034  operation.numberOfOutputs() !=
2035  operands[hwOp].size()) {
2036  PRINT_VAR(operation.name());
2037  PRINT_VAR(operands[hwOp].size());
2038  PRINT_VAR(operation.numberOfInputs());
2039  PRINT_VAR(operation.numberOfOutputs());
2040  assert(
2041  operation.numberOfInputs() + operation.numberOfOutputs() ==
2042  (int)operands[hwOp].size());
2043  }
2044  }
2045 
2046  for (BundleOrderIndex::const_iterator boi = bundleOrder.begin();
2047  boi != bundleOrder.end(); ++boi) {
2048  llvm::MachineInstr* mi = NULL;
2049  const llvm::TargetInstrInfo& tii =
2050  *mbb.getParent()->getTarget().getSubtargetImpl(
2051  mbb.getParent()->getFunction())->getInstrInfo();
2052  if (startedOps.find(*boi) == startedOps.end()) {
2053 #if 0
2054  // TODO: figure out a generic way to find the NOP opcode for
2055  // the current "lane", it's SPU::ENOP and SPU::LNOP for SPU.
2056  // Could call the TargetInstrInfo::insertNoop() if it was
2057  // implemented for SPU.
2058  // Just omit NOP instructions for now and assume the NOP inserter
2059  // pass takes care of it.
2060  mi = mbb.getParent()->CreateMachineInstr(
2061  findLLVMTargetInstrDesc("nop", tii),
2062  llvm::DebugLoc());
2063 #endif
2064 
2065 #ifdef DEBUG_POM_TO_MI
2066  Application::logStream() << "nop";
2067 #endif
2068  } else {
2069  const TTAMachine::HWOperation* hwop =
2070  (*startedOps.find(*boi)).second;
2071  assert(hwop->name() != "");
2072 #ifdef DEBUG_POM_TO_MI
2073  Application::logStream() << "hwop: '" << hwop->name() << "' " << std::endl;
2074 #endif
2075 
2076  const llvm::MCInstrDesc& tid =
2077  findLLVMTargetInstrDesc(hwop->name(), tii);
2078  mi = mbb.getParent()->CreateMachineInstr(
2079  tid, llvm::DebugLoc());
2080 
2081 #ifdef DEBUG_POM_TO_MI
2082  Application::logStream() << "MI: ";
2083  //mi->dump();
2084 #endif
2085 
2086 
2087  std::vector<TTAProgram::Terminal*>& opr = operands[hwop];
2088 
2089  unsigned counter = 0;
2090  // add the MachineOperands to the instruction via
2091  // POM Terminal --> MachineOperand conversion
2092  for (std::vector<TTAProgram::Terminal*>::const_iterator opri =
2093  opr.begin(); opri != opr.end() &&
2094  (counter < tid.getNumOperands() || mi->getDesc().isReturn());
2095  ++opri, ++counter) {
2096  TTAProgram::Terminal* terminal = *opri;
2097  if (terminal->isCodeSymbolReference()) {
2098  // has to be a global variable at this point?
2099  // Constant pool indeces are converted to
2100  // dummy references when LLVM->POM conversion
2101  // in the form of ".CP_INDEX_OFFSET"
2102  if (terminal->toString().startsWith(".CP_")) {
2103  std::vector<TCEString> refs =
2104  terminal->toString().split("_");
2105  unsigned index = Conversion::toInt(refs.at(1));
2106  unsigned offset = Conversion::toInt(refs.at(2));
2107  mi->addOperand(
2108  llvm::MachineOperand::CreateCPI(index, offset));
2109  } else if (terminal->toString().startsWith(".JTI_")) {
2110  TCEString ref = terminal->toString().substr(5);
2111  unsigned index = Conversion::toInt(ref);
2112  mi->addOperand(
2113  llvm::MachineOperand::CreateJTI(index, 0));
2114  } else {
2115  mi->addOperand(
2116  llvm::MachineOperand::CreateES(
2117  terminal->toString().c_str()));
2118  }
2119  } else if (terminal->isBasicBlockReference()) {
2120  llvm::MachineBasicBlock& mbb2 =
2121  getMBB(*mbb.getParent(), terminal->basicBlock());
2122  mi->addOperand(
2123  llvm::MachineOperand::CreateMBB(&mbb2));
2124  mbb.addSuccessor(&mbb2);
2125  } else if (terminal->isProgramOperationReference()) {
2127  dynamic_cast<
2129  *terminal);
2130  llvm::MCSymbol* symbol =
2131  mbb.getParent()->getContext().getOrCreateSymbol(
2132  llvm::StringRef(tpo.label()));
2133  mi->addOperand(llvm::MachineOperand::CreateMCSymbol(symbol));
2134  // need to keep book of the TPOs in order to recreate the
2135  // label instructions
2136  tpos_.insert(std::make_pair(tpo.programOperation(), symbol));
2137  } else if (terminal->isImmediate()) {
2138  if (!mi->getDesc().isReturn()) {
2139  mi->addOperand(
2140  llvm::MachineOperand::CreateImm(
2141  terminal->value().intValue()));
2142  }
2143  } else if (terminal->isGPR()) {
2144  // in case it's an output, it's a def, the outputs are always the
2145  // first operands in the LLVM instruction
2146  bool isDef = counter < tid.getNumDefs();
2147  bool isImp = false;
2148  // RET on spu seems to have implicit operand
2149  // TODO: implement real implicit property to OSAL
2150  // operands.
2151  if (mi->getDesc().isReturn()) {
2152  isImp = true;
2153  }
2154 
2155  // LLVM register index starts from 1,
2156  // we count register from 0
2157  // thus add 1 to get correct data to the LLVM
2158  if (!mi->getDesc().isReturn()) {
2159  mi->addOperand(
2160  llvm::MachineOperand::CreateReg(
2161  terminal->index() + 1, isDef, isImp));
2162  }
2163 
2164  } else {
2166  "Unsupported Terminal -> MachineOperand conversion attempted.");
2167  }
2168 #ifdef DEBUG_POM_TO_MI
2169  if (counter > 0)
2170  Application::logStream() << ", ";
2171  Application::logStream() << terminal->toString();
2172 #endif
2173  }
2174  }
2175  if (mi != NULL) {
2176  mbb.push_back(mi);
2177  assert(startedPOs.find(*boi) != startedPOs.end());
2178  ProgramOperationPtr po = (*startedPOs.find(*boi)).second;
2179  assert(po.get() != NULL);
2180  if (po.get() != NULL) {
2181  programOperationToMIMap_[po.get()] = mi;
2182  } else {
2183  //assert(po.get() != NULL);
2184  }
2185  }
2186 #ifdef DEBUG_POM_TO_MI
2187  Application::logStream() << "\t# " << (*boi)->name() << std::endl;
2188 #endif
2189  }
2190 #ifdef DEBUG_POM_TO_MI
2191  Application::logStream() << std::endl;
2192 #endif
2193  }
2194 
2195 #ifdef DEBUG_POM_TO_MI
2196  Application::logStream() << std::endl << std::endl;
2197 #endif
2198 }
2199 
2200 
2201 /**
2202  * Updates instruction references from procedure to cfg
2203  * Which is constructed from the procedure.
2204  *
2205  */
2206 void
2208 
2209  // make all refs point to the new copied instructions.
2210  for (int i = 0; i < nodeCount(); i++) {
2211  BasicBlockNode& bbn = node(i);
2213  }
2214 
2215 #if 0 // TODO: why does this irm claim to be unuser variable??
2217  // procedure should not have any references.
2218  for (int i = 0; i < procedure_->instructionCount(); i++) {
2220  }
2221 #endif
2222 }
2223 
2224 
2225 /**
2226  * Return an incoming fall-thru edge to a node.
2227  * Jump and entry is also considered fall-thru
2228  *
2229  * @param bbn the node
2230  * @return the edge or null, if none found.
2231  */
2234 
2235  auto edges = boost::in_edges(descriptor(bbn), graph_);
2236  for (auto i = edges.first; i != edges.second; ++i) {
2237  auto edge = graph_[(*i)];
2238  if (!edge->isJumpEdge()) {
2239  edgeDescriptors_[edge] = *i;
2240  return edge;
2241  }
2242  }
2243  return nullptr;
2244 }
2245 
2246 /**
2247  * Tells whether a node has incoming jumps that are not from
2248  * a single-basic block loop, ie source is not the same node.
2249  *
2250  * @param bbn the node
2251  */
2252 bool
2255 
2256  for (auto e: jumpEdges) {
2257  if (&tailNode(*e) != &bbn) {
2258  return true;
2259  }
2260  }
2261  return false;
2262 }
2263 
2266 
2267  auto edges = boost::in_edges(descriptor(bbn), graph_);
2268  EdgeSet result;
2269  for (auto i = edges.first; i != edges.second; ++i) {
2270  auto edge = graph_[(*i)];
2271  if (edge->isJumpEdge()) {
2272  edgeDescriptors_[edge] = *i;
2273  result.insert(edge);
2274  }
2275  }
2276  return result;
2277 }
2278 
2279 /**
2280  * Finds a jump that jumps to target from a codesnippet and removes the
2281  * jump.
2282  *
2283  * @param cs CodeSnippet where to remove the jump from.
2284  * @param target jump target instruction.
2285  * @param idx index which after to check for existing moves and immeds
2286  * @return whther not removed, removed and some moves last after idx,
2287  * or if removed and no moves/immeds left after idx.
2288  * @TODO should be able to handle also jumps where address is LIMM
2289  */
2292  CodeSnippet& cs, const Instruction& target, int idx,
2293  DataDependenceGraph* ddg) {
2294  int index = cs.instructionCount() -1; // - delaySlots;
2295 
2296  Move* lastJump = NULL;
2297  for (;index >= idx ; index--) {
2298  Instruction& ins = cs.instructionAtIndex(index);
2299  for (int j = 0; j < ins.moveCount(); j++) {
2300  Move& move = ins.move(j);
2301  if (!move.isJump()) {
2302  continue;
2303  }
2304 
2305  TTAProgram::Terminal& term = move.source();
2306  if (term.isInstructionAddress()) {
2309  term);
2311  tia.instructionReference();
2312 
2313  // found jump to target? remove this?
2314  if (&ir.instruction() == &target) {
2315  if (lastJump != NULL) {
2316  // TODO: should also check that no other moves
2317  // as the lastJump after the delay slots of
2318  // the move.
2319  if (lastJump->isUnconditional()) {
2320  // if removing conditional jump,
2321  // make the other jump have opposite guard
2322  if (!move.isUnconditional()) {
2323 
2324  TTAProgram::MoveGuard* invG = NULL;
2325  // if already scheduled,
2326  // guard must be in same bus
2327  if (!lastJump->bus().machine()->
2328  isUniversalMachine()) {
2329  invG = CodeGenerator::createInverseGuard(
2330  move.guard(), &lastJump->bus());
2331  } else {
2332  invG = CodeGenerator::createInverseGuard(
2333  move.guard());
2334  }
2335  if (invG == NULL) {
2336  return JUMP_NOT_REMOVED;
2337  }
2338  lastJump->setGuard(invG);
2339  }
2340 
2341  if (ddg != NULL) {
2342 #ifdef DEBUG_BB_OPTIMIZER
2343  std::cerr << "removing jump node from ddg."
2344  << std::endl;
2345 #endif
2346  MoveNode* mn = &ddg->nodeOfMove(move);
2347  ddg->removeNode(*mn);
2348  delete mn;
2349  }
2350 
2351  ins.removeMove(move);
2352  return JUMP_REMOVED;
2353  } else {
2354  // two conditional jumps? nasty. no can do
2355  return JUMP_NOT_REMOVED;
2356  }
2357  } else {
2358  if (ddg != NULL) {
2359 #ifdef DEBUG_BB_OPTIMIZER
2360  std::cerr << "removing jump node from ddg(2)."
2361  << std::endl;
2362 #endif
2363  MoveNode* mn = &ddg->nodeOfMove(move);
2364  ddg->removeNode(*mn);
2365  delete mn;
2366  }
2367 
2368  ins.removeMove(move);
2369  // check if there are moves/immeds left.
2370  // if not, update refs.
2371  for (; idx < cs.instructionCount(); idx++) {
2372  Instruction& ins2 = cs.instructionAtIndex(idx);
2373  if (ins2.moveCount() > 0 ||
2374  ins2.immediateCount() > 0) {
2375  return JUMP_REMOVED;
2376  }
2377  }
2378  return LAST_ELEMENT_REMOVED;
2379  }
2380  }
2381  }
2382  lastJump = &move;
2383  }
2384  }
2385  return JUMP_NOT_REMOVED;
2386 }
2387 
2388 /**
2389  * Removes and deletes a basic block node from the grpahs and
2390  * updates all references that point to it to point elsewhere.
2391  *
2392  * @param node basic block node to be removed and deleted.
2393  */
2394 void
2396  removeNode(node);
2397  delete &node;
2398 }
2399 
2402  if (program_ == NULL) {
2403  return *irm_;
2404  throw NotAvailable(__FILE__,__LINE__,__func__,
2405  "cfg does not have program");
2406  }
2408 }
2409 
2412  for (int i = 0; i < outDegree(bbn); i++) {
2413  Edge& e = outEdge(bbn,i);
2414  if (e.isJumpEdge()) {
2415  return &headNode(e);
2416  }
2417  }
2418  return NULL;
2419 }
2420 
2421 /**
2422  * Tests created control flow graph using depth first search algorithm
2423  * of boost graph library and mark back edges.
2424  */
2425 void
2427  DFSBackEdgeVisitor vis;
2428  /// Default starting vertex is vertex(g).first, which is actually
2429  /// first basic block created. Entry is created as second and
2430  /// there is connection added from entry to first BB.
2431  /// Using default parameter for root_vertex is therefore sufficient
2432  boost::depth_first_search(graph_, visitor(vis));
2433 }
2434 
2435 
2437 
2438  for (int i = 0; i < nodeCount(); i++) {
2439  BasicBlockNode& bbn = node(i);
2440 
2441  if (bbn.isNormalBB()) {
2442  TTAProgram::BasicBlock& bb = bbn.basicBlock();
2443 
2444  for (int j = 0; j < bb.instructionCount(); j++) {
2446 
2447  for (int k = 0; k < ins.moveCount(); k++) {
2448  TTAProgram::Move& move = ins.move(k);
2449  TTAProgram::Terminal& src = move.source();
2450 
2451  if (src.isBasicBlockReference()) {
2452  const TTAProgram::BasicBlock& target =
2453  src.basicBlock();
2454  assert(target.instructionCount() > 0);
2455  move.setSource(
2457  instructionReferenceManager().createReference(
2458  target.firstInstruction())));
2459  }
2460  }
2461 
2462  for (int k = 0; k < ins.immediateCount(); k++) {
2463  TTAProgram::Immediate& imm = ins.immediate(k);
2464  TTAProgram::Terminal& immVal = imm.value();
2465 
2466  if (immVal.isBasicBlockReference()) {
2467  const TTAProgram::BasicBlock& target =
2468  immVal.basicBlock();
2469  assert(target.instructionCount() > 0);
2470  imm.setValue(
2472  instructionReferenceManager().createReference(
2473  target.firstInstruction())));
2474  }
2475  }
2476  }
2477  }
2478  }
2479 }
2480 
2481 /**
2482  * Reverses predicate of outgoing edges.
2483  *
2484  */
2485 void
2487  for (int i = 0; i < outDegree(bbn); i++) {
2488  Edge& e = outEdge(bbn,i);
2489  if (e.isTrueEdge()) {
2491  } else if (e.isFalseEdge()) {
2493  } else {
2494  std::cerr << "node in question: " << bbn.toString() <<
2495  " edge: " << e.toString() << std::endl;
2496  writeToDotFile("invalid_predicate.dot");
2497  assert(false && "Can only reverse predicate true or false");
2498  }
2499  }
2500 }
2501 
2504  const ControlFlowGraph::NodeSet& reachableNodes) {
2505  NodeSet unreachableNodes;
2506  // find dead nodes
2507  for (int i = 0; i < nodeCount(); i++) {
2508  BasicBlockNode& n = node(i);
2509  if (!AssocTools::containsKey(reachableNodes,&n) &&
2510  n.isNormalBB()) {
2511  unreachableNodes.insert(&n);
2512  }
2513  }
2514  return unreachableNodes;
2515 }
2516 
2517 /**
2518  * The algorithm is same as in CopyToProcedure, but without the copying.
2519  * Still removes jump, and also does BB mergeing.
2520  */
2521 void
2523  bool removeDeadCode, InstructionReferenceManager& irm,
2524  DataDependenceGraph* ddg) {
2525 
2526 #ifdef DEBUG_BB_OPTIMIZER
2528  (boost::format("%s_before_optimize_cfg.dot") %
2529  name()).str());
2530 #endif
2531 
2533  assert(firstBBs.size() == 1);
2534  BasicBlockNode* firstBBN = *firstBBs.begin();
2535  BasicBlockNode* currentBBN = firstBBN;
2536  entryNode().link(firstBBN);
2537 
2538  // find and queue reachable nodes
2539  NodeSet queuedNodes = findReachableNodes();
2540  NodeSet unreachableNodes = findUnreachableNodes(queuedNodes);
2541 
2542  if (removeDeadCode) {
2543  removeUnreachableNodes(unreachableNodes, ddg);
2544  }
2545 
2546  // then loop as long as we have BBs which have not been written to
2547  // the procedure.
2548  while (currentBBN != NULL) {
2549 
2550 #ifdef DEBUG_BB_OPTIMIZER
2551  std::cerr << "current node: " << currentBBN->toString() <<
2552  std::endl;
2553 #endif
2554  BasicBlockNode* nextNode = NULL;
2555  TTAProgram::BasicBlock& bb = currentBBN->basicBlock();
2556  queuedNodes.erase(currentBBN);
2557 
2558  // if has a fall-through node, it has to be the next node
2559  BasicBlockNode* ftNode = fallThruSuccessor(*currentBBN);
2560  bool unhandledFT = false;
2561  while (ftNode != NULL && ftNode->isNormalBB()) {
2562  if (queuedNodes.find(ftNode) == queuedNodes.end()) {
2563  std::cerr << "not-queued fall-thru: " << ftNode->toString()
2564  << " current: " << currentBBN->toString() <<
2565  std::endl;
2566  writeToDotFile("optimizeCFGFallThruBBNotQueued.dot");
2567  }
2568  // must not be already processed.
2569  assert(queuedNodes.find(ftNode) != queuedNodes.end());
2570 
2571 #ifdef DEBUG_BB_OPTIMIZER
2572  std::cerr << "\tfound FT node: " << ftNode->toString() << std::endl;
2573 #endif
2574  const ControlFlowEdge& cfe =
2575  **connectingEdges(*currentBBN, *ftNode).begin();
2576 
2577  // if fall-through node has no other predecessors, merge.
2578  if (inDegree(*ftNode) == 1 && !cfe.isCallPassEdge()
2579  && ftNode->isScheduled() == currentBBN->isScheduled() // *1
2580  && (outDegree(*currentBBN) == 1 || ftNode->basicBlock().isEmpty())) {
2581 
2582  // *1: No merging of inline asm block (they are set as
2583  // scheduled before others). After all is scheduled this
2584  // might be ok.
2585 #ifdef DEBUG_BB_OPTIMIZER
2586  std::cerr << "Merging: " << currentBBN->toString()
2587  << " with: " << ftNode->toString() << std::endl;
2588  writeToDotFile("before_merge.dot");
2589  if (cfe.isBackEdge()) {
2590  std::cerr << "Warning: merging over back edge." <<
2591  std::endl;
2592  }
2593 #endif
2594  queuedNodes.erase(ftNode);
2595  mergeNodes(*currentBBN, *ftNode, ddg, cfe);
2596 #ifdef DEBUG_BB_OPTIMIZER
2597  writeToDotFile("after_merge.dot");
2598  std::cerr << "Merged with ft node." << std::endl;
2599 #endif
2600  ftNode = fallThruSuccessor(*currentBBN);
2601  } else {
2602  currentBBN->link(ftNode);
2603 #ifdef DEBUG_BB_OPTIMIZER
2604  writeToDotFile("linked.dot");
2605 #endif
2606  currentBBN = ftNode;
2607  unhandledFT = true;
2608  break;
2609  }
2610  }
2611 
2612  if (unhandledFT) continue;
2613 
2614  // Select some node, preferably successors without ft-preds
2615  // The jump can then be removed.
2616  EdgeSet oEdges = outEdges(*currentBBN);
2617  for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
2618  ControlFlowEdge& e = **i;
2619  BasicBlockNode& head = headNode(e);
2620  if (!hasFallThruPredecessor(head) && head.isNormalBB() &&
2621  queuedNodes.find(&head) != queuedNodes.end()
2622  && currentBBN->isScheduled() == head.isScheduled() /* *1 */) {
2623  // *1: No merging of inline asm block (they are set as
2624  // scheduled before others). After all is scheduled this
2625  // might be ok.
2626 
2627  // try to remove the jump as it's jump to the next BB.
2629  bb, head.basicBlock().firstInstruction(), 0, ddg);
2630  if (rjd != JUMP_NOT_REMOVED) {
2631  // if BB got empty,
2632  // move refs to beginning of the next BB.
2633  if (rjd == LAST_ELEMENT_REMOVED) {
2634  Instruction& ins = bb.instructionAtIndex(0);
2635  if (irm.hasReference(ins)) {
2636  irm.replace(
2637  ins, head.basicBlock().instructionAtIndex(
2638  head.basicBlock().
2639  skippedFirstInstructions()));
2640  }
2642  queuedNodes.erase(&head);
2643  mergeNodes(*currentBBN, head, ddg, e);
2644 #ifdef DEBUG_BB_OPTIMIZER
2645  std::cerr << "Merged with after jump removal(1)" <<
2646  std::endl;
2647 #endif
2648  nextNode = currentBBN;
2649  break;
2650  }
2651  // we removed a jump so convert the jump edge into
2652  // fall-through edge, OR merge BBs.
2653 
2654  if (inDegree(head) == 1 && outDegree(*currentBBN) == 1) {
2655 #ifdef DEBUG_BB_OPTIMIZER
2656  std::cerr << "Merging after jump removal.." << std::endl;
2657 #endif
2658  // should not be allowd to do this if has return
2659 
2660  queuedNodes.erase(&head);
2661  mergeNodes(*currentBBN, head, ddg, e);
2662  nextNode = currentBBN;
2663 #ifdef DEBUG_BB_OPTIMIZER
2664  std::cerr << "Merged with after jump removal(2)" <<
2665  std::endl;
2666 #endif
2667  } else {
2668  ControlFlowEdge* ftEdge = new ControlFlowEdge(
2669  e.edgePredicate(),
2671  removeEdge(e);
2672  connectNodes(*currentBBN, head, *ftEdge);
2673  nextNode = &head;
2674  }
2675  // if we did remove a back edge, we need to scan the cfg
2676  // again for back edges.
2677  // TODO: should we also then mark ddg edges that
2678  // do over this cfg edge?
2679  if (e.isBackEdge()) {
2680  detectBackEdges();
2681  }
2682  break; // continue outer;
2683  }
2684  }
2685  }
2686  if (nextNode != NULL) {
2687  continue;
2688  }
2689 
2690  // need to select SOME node as successor.
2691  // first without ft-predecessor usually is a good candidate.
2692  // smarter heuristic does not seem to help at all.
2693  // try to select
2694  bool ftPred = false;
2695  for (NodeSet::iterator i = queuedNodes.begin();
2696  i != queuedNodes.end(); i++) {
2697  if (!hasFallThruPredecessor(**i)) {
2698  nextNode = *i;
2699  break;
2700  } else {
2701  ftPred = true;
2702  }
2703  }
2704 
2705  if (!removeDeadCode) {
2706  // unreachable node having ft may have prevented us from
2707  // managing some node whose fall-thru succs prevent
2708  // futher nodes. try to select some unreached node.
2709  if (nextNode == NULL && ftPred) {
2710  for (NodeSet::iterator i = unreachableNodes.begin();
2711  i != unreachableNodes.end(); i++) {
2712  if (fallThruSuccessor(**i) != NULL) {
2713  nextNode = *i;
2714  unreachableNodes.erase(*i);
2715  break;
2716  }
2717  }
2718  }
2719  }
2720  if (nextNode == NULL) {
2721  currentBBN->link(&exitNode());
2722  break;
2723  }
2724  else {
2725  currentBBN->link(nextNode);
2726  currentBBN = nextNode;
2727  }
2728  }
2729 #ifdef DEBUG_BB_OPTIMIZER
2731  (boost::format("%s_after_optimize_cfg.dot") %
2732  name()).str());
2733 #endif
2734 }
2735 
2736 /**
2737  * TODO: what to do with exit node?
2738  */
2739 void
2741  const NodeSet& nodes, DataDependenceGraph* ddg) {
2742  for (NodeSet::iterator i = nodes.begin(); i != nodes.end(); i++) {
2743  BasicBlockNode* bbn = *i;
2744  removeNode(*bbn);
2745  if (ddg != NULL) {
2746  TTAProgram::BasicBlock& bb = bbn->basicBlock();
2747  for (int j = 0; j < bb.instructionCount(); j++) {
2748  Instruction& ins = bb.instructionAtIndex(j);
2749  for (int k = 0; k < ins.moveCount(); k++) {
2750  Move& move = ins.move(k);
2751  MoveNode* mn = &ddg->nodeOfMove(move);
2752  ddg->removeNode(*mn);
2753  delete mn;
2754  }
2755  }
2756  delete bbn;
2757  }
2758  }
2759 }
2760 
2761 void
2763  BasicBlockNode& node1, BasicBlockNode& node2,
2764  DataDependenceGraph* ddg, const ControlFlowEdge& connectingEdge) {
2765 
2766  if (ddg != NULL &&
2767  (!ddg->hasAllRegisterAntidependencies() &&
2769  ddg->fixInterBBAntiEdges(node1, node2, false);
2770  }
2771  assert(node1.isNormalBB());
2772  assert(node2.isNormalBB());
2773  TTAProgram::BasicBlock& bb1 = node1.basicBlock();
2774  TTAProgram::BasicBlock& bb2 = node2.basicBlock();
2775  for (int i = bb2.instructionCount() -1; i >= 0; i--) {
2776  Instruction& ins = bb2.instructionAtIndex(i);
2777  if (ddg != NULL) {
2778  for (int k = 0; k < ins.moveCount(); k++) {
2779  Move& move = ins.move(k);
2780  MoveNode* mn = &ddg->nodeOfMove(move);
2781  ddg->setBasicBlockNode(*mn, node1);
2782  }
2783  }
2784  }
2785 
2786  if (node1.basicBlock().liveRangeData_ != NULL &&
2787  node2.basicBlock().liveRangeData_ != NULL) {
2788  node1.basicBlock().liveRangeData_->merge(
2789  *node2.basicBlock().liveRangeData_);
2790  }
2791 
2792  for (int i = bb2.skippedFirstInstructions(),
2793  end = bb2.instructionCount();
2794  i < end; i++) {
2795  Instruction& ins = bb2[bb2.skippedFirstInstructions()];
2796  bb2.remove(ins);
2797  bb1.add(&ins);
2798  }
2799 
2800  EdgeSet n2in = inEdges(node2);
2801  for (EdgeSet::iterator i = n2in.begin(); i != n2in.end(); i++) {
2802  ControlFlowEdge* e = *i;
2803  const BasicBlockNode& tail = tailNode(*e);
2804  if (&tail != &node1) {
2805  moveInEdge(node2, node1, *e);
2806  }
2807  }
2808 
2809  EdgeSet n2out = outEdges(node2);
2810  for (EdgeSet::iterator i = n2out.begin(); i != n2out.end(); i++) {
2811  ControlFlowEdge* e = *i;
2812  if (!connectingEdge.isNormalEdge()) {
2813  assert(e->isNormalEdge());
2814  e->setPredicate(connectingEdge.edgePredicate());
2815  }
2816  moveOutEdge(node2, node1, *e);
2817  }
2818 
2819  removeNode(node2);
2820  delete &node2;
2821  // TODO: CFG edges
2822 }
2823 
2824 /**
2825  * Fetch machine basic block corresponding to the BasicBlock passed, if
2826  * it does not exist create empty one.
2827  */
2828 llvm::MachineBasicBlock&
2830  llvm::MachineFunction& mf,
2831  const TTAProgram::BasicBlock& bb) const {
2832 
2833  if (MapTools::containsKey(bbMap_, &bb)) {
2834  return *bbMap_[&bb];
2835  } else {
2836  llvm::MachineBasicBlock* mbb = mf.CreateMachineBasicBlock();
2837  mf.push_back(mbb);
2838  bbMap_[&bb] = mbb;
2839  return *mbb;
2840  }
2841 }
2842 
2843 /**
2844  * Checks if the basic blocks have calls in the middle of them and splits
2845  * them to multiple basic blocks with call edge chains.
2846  *
2847  * TCE scheduler assumes there cannot be calls in the middle of basic block.
2848  */
2849 void
2851  std::set<BasicBlockNode*> bbsToHandle;
2852  for (int i = 0; i < nodeCount(); ++i) {
2853  BasicBlockNode& bb = node(i);
2854  bbsToHandle.insert(&bb);
2855  }
2856 
2857  while (bbsToHandle.size() > 0) {
2858  BasicBlockNode* bbn = *bbsToHandle.begin();
2859  TTAProgram::BasicBlock& bb = bbn->basicBlock();
2860 
2861  for (int ii = 0; ii < bb.instructionCount(); ++ii) {
2862  TTAProgram::Instruction& instr = bb.instructionAt(ii);
2863  if (instr.hasCall() && &instr != &bb.lastInstruction()) {
2864  bbsToHandle.insert(splitBasicBlockAtIndex(*bbn, ii+1));
2865  break;
2866  }
2867  assert (irm_ != NULL);
2868  if (ii != 0 && irm_->hasReference(instr)) {
2869  bbsToHandle.insert(splitBasicBlockAtIndex(*bbn, ii));
2870  break;
2871  }
2872  }
2873  bbsToHandle.erase(bbn);
2874  }
2875 }
2876 
2879  BasicBlockNode& bbn, int index) {
2880 
2881  TTAProgram::BasicBlock& bb = bbn.basicBlock();
2883  BasicBlockNode* newbbn = new BasicBlockNode(*newbb);
2884  // Inline Asm BBs are set scheduled, copy the property.
2885  newbbn->setScheduled(bbn.isScheduled());
2886  addNode(*newbbn);
2887 
2888  // the BB can contain multiple calls, handle them
2889  // in the new BB
2890  moveOutEdges(bbn, *newbbn);
2891 
2892  // move the instructions after the call in the old BB to
2893  // the new one.
2894  // no index update because remove puts to same index
2895  for (int i = index; i < bb.instructionCount(); ) {
2897  bb.remove(ins);
2898  newbb->add(&ins);
2899  }
2900 
2901  ControlFlowEdge* cfe = new ControlFlowEdge(
2904  connectNodes(bbn, *newbbn, *cfe);
2905 
2906  if (bb.liveRangeData_) {
2907  newbb->liveRangeData_ = new LiveRangeData;
2914  }
2915 
2916  return newbbn;
2917 }
2918 
2920  for (int i = 0; i < outDegree(node); i++) {
2921  ControlFlowEdge& e = outEdge(node, i);
2922  if (e.isJumpEdge() && &headNode(e) == &node) {
2923  assert(e.isBackEdge());
2924  return true;
2925  }
2926  }
2927  return false;
2928 }
2929 
2930 /**
2931  * Sanitizes CFG back to a format where there are no jumps to middle of a BB,
2932  * And where the instruction index 0 of all basic blocks really mean
2933  * the first instructions.
2934  * The delay slot filler may generate such "insane" CFGs which breaks these.
2935  * So this should be run after the delay slot filler to make the CFG sane
2936  * again.
2937  */
2939 
2940  for (int i = 0; i < nodeCount(); i++) {
2941  auto& n = node(i);
2942  auto& bb = n.basicBlock();
2943  // Remove the skipped first instructions. They are totally dead!
2944  // they only exist to not mess up BB vs RM bookkeeping,
2945  // but no need for this anymore!
2946  for (int j = bb.skippedFirstInstructions(); j > 0; j--) {
2947  auto& ins = bb[0];
2948 
2949  if (instructionReferenceManager().hasReference(ins)) {
2950  std::cerr << "Skipped ins has ref: " << ins.toString()
2951  << std::endl;
2952  std::cerr << "node: " << n.toString() << std::endl;
2953  writeToDotFile("skipped_ins_has_ref.dot");
2954  }
2955  assert(!instructionReferenceManager().hasReference(ins));
2956 
2957  bb.remove(ins);
2958  }
2959  bb.skipFirstInstructions(0);
2960  // now our BB instructions start from index 0.
2961 
2962  if (!bb.instructionCount()) continue;
2963 
2964  // do we need to split this?
2965  auto& firstIns = bb[0];
2966  auto ns = inEdges(n);
2967 
2968  for (int j = 1; j < bb.instructionCount(); j++) {
2969  auto& ins = bb[j];
2970 
2971  // need to split before this instruction?
2972  if (instructionReferenceManager().hasReference(ins)) {
2973  BasicBlockNode* newBBN = splitBB(n, j);
2974 
2975  auto firstInsRef =
2978 
2979  // update in edges. jumps that don't point to original start ins
2980  // should be updated to this.
2981  for (auto e: ns) {
2982  if (!e->isJumpEdge()) {
2983  continue;
2984  }
2985  auto& srcNode = tailNode(*e);
2986  auto t = findJumpAddress(srcNode, *e);
2987  if (!tir.equals(*t)) {
2988  moveInEdge(n, *newBBN, *e, &srcNode);
2989  }
2990  }
2991  break;
2992  }
2993  }
2994  }
2995 }
2996 
2997 /**
2998  * Finds the terminal containing the target address of the jump
2999  * corresponding to the edge.
3000  *
3001  * @param src basic block node which is the tail of the edge,
3002  * containing the jump.
3003  * @param edge edge whose target address is being searched.
3004  */
3007  auto& bb = src.basicBlock();
3008  for (int i = bb.instructionCount()-1;
3009  i >= bb.skippedFirstInstructions(); i--) {
3010  auto& ins = bb[i];
3011  for (int j = 0; j < ins.moveCount(); j++) {
3012  auto& m = ins.move(j);
3013  if (!m.isJump())
3014  continue;
3016  if (e.edgePredicate() == ep) {
3017  if (m.source().isInstructionAddress()) {
3018  return &m.source();
3019  } else {
3020  auto limm = findLimmWrite(m, src, i);
3021  assert(limm != nullptr);
3022  return &limm->value();
3023  }
3024  }
3025  }
3026  }
3027  return nullptr;
3028 }
3029 
3030 /**
3031  * Finds the immediate write which is read by a move.
3032  * @param move move containing the immediate use.
3033  * @param bbn basic block containing the move
3034  * @param moveIndex index of the instruction containing the move in the BB.
3035  */
3038  TTAProgram::Move& move, BasicBlockNode& bbn, int moveIndex) {
3039  auto& bb = bbn.basicBlock();
3040  const TTAMachine::ImmediateUnit& immu = move.source().immediateUnit();
3041  int lat = immu.latency();
3042  int i = moveIndex - lat;
3043  while (i >= bb.skippedFirstInstructions()) {
3044  TTAProgram::Instruction& ins = bb[i];
3045  for (int j = 0; j < ins.immediateCount(); j++) {
3046  auto& imm = ins.immediate(j);
3047  if (&imm.destination().immediateUnit() == &immu &&
3048  move.source().index() == imm.destination().index()) {
3049  return &imm;
3050  }
3051  }
3052  i--;
3053  }
3054  if (inDegree(bbn) == 1) {
3055  BasicBlockNode* pred = *predecessors(bbn).begin();
3056  if (!pred->isNormalBB()) {
3057  return nullptr;
3058  }
3059  // search staring from last ins of prev bb
3060  return findLimmWrite(
3061  move, *pred, pred->basicBlock().instructionCount() + lat -1);
3062  }
3063  return nullptr;
3064 }
3065 
3066 /**
3067  * Splits a basic block into two parts.
3068  *
3069  * @param n basic block node being splitted
3070  * @param remainingSize remaining effective size of the first bb,
3071  * or index of the instruction starting the new BB.
3072  * @return the created new basic block node.
3073  */
3076  BasicBlockNode& n, int remainingSize) {
3079  BasicBlockNode* nbbn = new BasicBlockNode(*nbb);
3080 
3081  // TODO: this is slow O(n^2) loop
3082  for (int i = remainingSize + bb.skippedFirstInstructions();
3083  i < bb.instructionCount(); ) {
3084  TTAProgram::Instruction& ins = bb[i];
3085  bb.remove(ins); // this changes the indeces and is a very slow op.
3086  nbb->add(&ins);
3087  }
3088 
3089  if (n.isScheduled()) {
3090  nbbn->setScheduled();
3091  }
3092  // then fix cfg
3093  addNode(*nbbn);
3094  moveOutEdges(n, *nbbn);
3095  connectNodes(n, *nbbn, *(new ControlFlowEdge(
3098  n.link(nbbn);
3099  return nbbn;
3100 }
3101 
3102 bool
3104  const BasicBlockNode& bbn) const {
3105  bool hasUncondSucc = false;
3106 
3107  for (int i = 0; i < outDegree(bbn); i++) {
3108  Edge& e = outEdge(bbn,i);
3109  if (e.isNormalEdge()) {
3110  if (hasUncondSucc) {
3111  return true;
3112  } else {
3113  hasUncondSucc = true;
3114  }
3115  }
3116  }
3117  return false;
3118 }
3119 
3121  const TTAProgram::Terminal& jumpAddr, const BasicBlockNode& bbn) const {
3122  if (!bbn.isNormalBB()) {
3123  return false;
3124  }
3125  if (jumpAddr.isBasicBlockReference()) {
3126  auto& target = jumpAddr.basicBlock();
3127  return &target == &bbn.basicBlock();
3128  }
3129  if (!jumpAddr.isCodeSymbolReference() && jumpAddr.isInstructionAddress()){
3130  auto& ir = jumpAddr.instructionReference();
3131  return &ir.instruction() ==
3132  &bbn.basicBlock().firstInstruction();
3133  }
3134  return false;
3135 }
3136 
3138  const BasicBlockNode &src, const TTAProgram::Terminal& jumpAddr,
3139  const TTAMachine::Machine& mach) const {
3140 
3141  int diff = mach.controlUnit()->delaySlots() +1;
3142 
3143  // search forwards.
3144  const BasicBlockNode* ftBBN = src.successor();
3145  while (ftBBN != nullptr && ftBBN->isNormalBB()) {
3146  if (jumpToBBN(jumpAddr, *ftBBN)) {
3147  return diff;
3148  }
3149  int nextSz = ftBBN->maximumSize();
3150  // max size not known, give up.
3151  if (nextSz == INT_MAX) {
3152  break;
3153  }
3154  ftBBN = ftBBN->successor();
3155  diff += nextSz;
3156  }
3157 
3158  // Then search backwards.
3159  diff = mach.controlUnit()->delaySlots() +1;
3160  ftBBN = &src;
3161  while (ftBBN != nullptr) {
3162  int sz = ftBBN->maximumSize();
3163 
3164  // maximum size not known, give up?
3165  if (sz == INT_MAX) {
3166  return INT_MAX;
3167  }
3168  diff -= sz;
3169 
3170  if (jumpToBBN(jumpAddr, *ftBBN)) {
3171  return diff;
3172  }
3173  ftBBN = ftBBN->predecessor();
3174  }
3175  return INT_MAX;
3176 }
3177 
3179  const BasicBlockNode& src, const BasicBlockNode& dst) const {
3180  const BasicBlockNode* ftBBN = src.successor();
3181  while (ftBBN != nullptr && ftBBN->isNormalBB()) {
3182  if (ftBBN == &dst) {
3183  return true;
3184  }
3185  if (ftBBN->isScheduled()) {
3186  ftBBN = ftBBN->successor();
3187  } else {
3188  return false;
3189  }
3190  }
3191  return false;
3192 }
ControlFlowGraph::buildMBBFromBB
void buildMBBFromBB(llvm::MachineBasicBlock &mbb, const TTAProgram::BasicBlock &bb) const
Definition: ControlFlowGraph.cc:1893
CFGStatistics::maxBypassedCount
virtual int maxBypassedCount() const
Definition: CFGStatistics.cc:82
TTAProgram::BasicBlockStatistics::setInstructionCount
virtual void setInstructionCount(int)
Definition: BasicBlock.cc:230
ControlFlowGraph::program
TTAProgram::Program * program() const
Definition: ControlFlowGraph.cc:1171
TTAProgram::Terminal::isFUPort
virtual bool isFUPort() const
Definition: Terminal.cc:118
SimValue::intValue
int intValue() const
Definition: SimValue.cc:895
BoostGraph< BasicBlockNode, ControlFlowEdge >::predecessors
virtual NodeSet predecessors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
TerminalInstructionReference.hh
ControlFlowGraph::reverseGuardOnOutEdges
void reverseGuardOnOutEdges(const BasicBlockNode &bbn)
Definition: ControlFlowGraph.cc:2486
TTAProgram
Definition: Estimator.hh:65
ControlFlowGraph::findNextIndex
unsigned int findNextIndex(const TTAProgram::Procedure &proc, int jumpInsIndex, int jumpMoveIndex)
Definition: ControlFlowGraph.cc:877
TTAProgram::Immediate::value
TerminalImmediate & value() const
Definition: Immediate.cc:103
CFGStatistics::maxMoveCount
virtual int maxMoveCount() const
Definition: CFGStatistics.cc:58
TTAProgram::Instruction::removeMove
void removeMove(Move &move)
Definition: Instruction.cc:536
TTAProgram::InstructionReference::instruction
Instruction & instruction() const
Definition: InstructionReference.cc:138
BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge
virtual Edge & outEdge(const Node &node, const int index) const
BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
TTAProgram::Program
Definition: Program.hh:63
ControlFlowGraph::endAddress_
TTAProgram::Address endAddress_
Definition: ControlFlowGraph.hh:321
TTAProgram::Move::isTriggering
bool isTriggering() const
Definition: Move.cc:284
OperationPool::operation
Operation & operation(const char *name)
Definition: OperationPool.cc:99
BasicBlockNode::isExitBB
bool isExitBB() const
Definition: BasicBlockNode.cc:257
POP_CLANG_DIAGS
#define POP_CLANG_DIAGS
Definition: CompilerWarnings.hh:96
TTAProgram::TerminalRegister::isGPR
virtual bool isGPR() const
InstructionAddress
UInt32 InstructionAddress
Definition: BaseType.hh:175
TTAProgram::Instruction::isNOP
bool isNOP() const
Definition: Instruction.hh:90
ControlFlowGraph::~ControlFlowGraph
virtual ~ControlFlowGraph()
Definition: ControlFlowGraph.cc:133
BoostGraph< BasicBlockNode, ControlFlowEdge >::removeEdge
virtual void removeEdge(Edge &e)
TTAProgram::BasicBlockStatistics::moveCount
virtual int moveCount() const
Definition: BasicBlock.cc:177
ControlFlowGraph::jumpToBBN
bool jumpToBBN(const TTAProgram::Terminal &jumpAddr, const BasicBlockNode &bbn) const
Definition: ControlFlowGraph.cc:3120
TTAProgram::CodeSnippet::firstInstruction
virtual Instruction & firstInstruction() const
Definition: CodeSnippet.cc:216
BaseType.hh
ControlFlowGraph::splitBasicBlocksWithCallsAndRefs
void splitBasicBlocksWithCallsAndRefs()
Definition: ControlFlowGraph.cc:2850
TTAProgram::InstructionReferenceManager::end
Iterator end()
BoostGraph< BasicBlockNode, ControlFlowEdge >::tailNode
virtual Node & tailNode(const Edge &edge) const
TTAProgram::DataDefinition
Definition: DataDefinition.hh:52
TTAMachine::Component::name
virtual TCEString name() const
Definition: MachinePart.cc:125
TCEString::split
std::vector< TCEString > split(const std::string &delim) const
Definition: TCEString.cc:114
ControlFlowGraph::InstructionAddressVector
std::vector< InstructionAddress > InstructionAddressVector
Definition: ControlFlowGraph.hh:194
LiveRangeData::inlineAsmRegDefs_
std::set< TCEString > inlineAsmRegDefs_
Definition: LiveRangeData.hh:127
TTAProgram::Instruction::move
Move & move(int i) const
Definition: Instruction.cc:193
ControlFlowGraph::returnSources_
ReturnSourceSet returnSources_
Definition: ControlFlowGraph.hh:336
TTAProgram::Terminal::index
virtual int index() const
Definition: Terminal.cc:274
BoostGraph< BasicBlockNode, ControlFlowEdge >::hasEdge
virtual bool hasEdge(const Node &nTail, const Node &nHead) const
PRINT_VAR
#define PRINT_VAR(VARIABLE__)
Definition: Application.hh:118
TTAProgram::Terminal::isInstructionAddress
virtual bool isInstructionAddress() const
Definition: Terminal.cc:87
ControlFlowGraph::RemovedJumpData
RemovedJumpData
Definition: ControlFlowGraph.hh:296
ControlFlowGraph::alignment
int alignment() const
Definition: ControlFlowGraph.cc:1160
TTAProgram::Address
Definition: Address.hh:51
ControlFlowGraph::JUMP_REMOVED
@ JUMP_REMOVED
nothing removed
Definition: ControlFlowGraph.hh:298
TCEString::startsWith
bool startsWith(const std::string &str) const
BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode
virtual Node & headNode(const Edge &edge) const
ControlFlowGraph::copyToProcedure
void copyToProcedure(TTAProgram::Procedure &proc, TTAProgram::InstructionReferenceManager *irm=NULL)
Definition: ControlFlowGraph.cc:1448
TTAMachine::HWOperation
Definition: HWOperation.hh:52
Exception.hh
BoostGraph< BasicBlockNode, ControlFlowEdge >::node
Node & node(const int index) const
DataDependenceGraph::fixInterBBAntiEdges
void fixInterBBAntiEdges(BasicBlockNode &bbn1, BasicBlockNode &bbn2, bool loopEdges)
Definition: DataDependenceGraph.cc:3689
ControlFlowGraph::findLimmWrite
TTAProgram::Immediate * findLimmWrite(TTAProgram::Move &move, BasicBlockNode &bb, int moveIndex)
Definition: ControlFlowGraph.cc:3037
DataDependenceGraph::setBasicBlockNode
void setBasicBlockNode(const MoveNode &mn, BasicBlockNode &bbn)
Definition: DataDependenceGraph.cc:216
CFGStatistics
Definition: CFGStatistics.hh:44
ControlFlowGraph::incomingFTEdge
ControlFlowEdge * incomingFTEdge(const BasicBlockNode &bbn) const
Definition: ControlFlowGraph.cc:2233
ControlFlowGraph::reversedGraph
ReversedGraph & reversedGraph() const
Definition: ControlFlowGraph.cc:989
BasicBlockNode::originalEndAddress
InstructionAddress originalEndAddress() const
Definition: BasicBlockNode.cc:174
TTAProgram::NullInstruction
Definition: NullInstruction.hh:45
ControlFlowEdge::isJumpEdge
bool isJumpEdge() const
Definition: ControlFlowEdge.cc:148
TTAProgram::MoveGuard::isInverted
bool isInverted() const
Definition: MoveGuard.cc:76
ControlFlowGraph::alignment_
int alignment_
Definition: ControlFlowGraph.hh:322
ControlFlowGraph::removeJumpToTarget
RemovedJumpData removeJumpToTarget(TTAProgram::CodeSnippet &cs, const TTAProgram::Instruction &target, int idx, DataDependenceGraph *ddg=NULL)
Definition: ControlFlowGraph.cc:2291
ControlFlowGraph::buildFrom
void buildFrom(const TTAProgram::Procedure &procedure)
Definition: ControlFlowGraph.cc:200
AssocTools::containsKey
static bool containsKey(const ContainerType &aContainer, const KeyType &aKey)
BoostGraph< BasicBlockNode, ControlFlowEdge >::NodeSet
std::set< BasicBlockNode *, typename BasicBlockNode ::Comparator > NodeSet
Definition: BoostGraph.hh:86
TTAProgram::Instruction
Definition: Instruction.hh:57
TTAProgram::Move::isUnconditional
bool isUnconditional() const
Definition: Move.cc:154
ControlFlowEdge::toString
TCEString toString() const
Definition: ControlFlowEdge.cc:64
MapTools.hh
ControlFlowGraph::printStatistics
TCEString printStatistics()
Definition: ControlFlowGraph.cc:1286
Procedure.hh
LiveRangeData::inlineAsmClobbers_
std::set< TCEString > inlineAsmClobbers_
Definition: LiveRangeData.hh:128
LiveRangeData::merge
void merge(LiveRangeData &succ)
Definition: LiveRangeData.cc:47
IGNORE_CLANG_WARNING
#define IGNORE_CLANG_WARNING(X)
Definition: CompilerWarnings.hh:85
ControlFlowEdge::edgePredicateFromMove
static ControlFlowEdge::CFGEdgePredicate edgePredicateFromMove(const TTAProgram::Move &move)
Definition: ControlFlowEdge.cc:187
TTAProgram::TerminalInstructionReference::instructionReference
virtual const InstructionReference & instructionReference() const
Definition: TerminalInstructionReference.cc:78
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
ControlFlowGraph::createAllBlocks
void createAllBlocks(InstructionAddressMap &leaders, const TTAProgram::Procedure &procedure)
Definition: ControlFlowGraph.cc:503
BasicBlockNode::link
void link(BasicBlockNode *succ)
Definition: BasicBlockNode.cc:352
ControlFlowGraph::startAddress_
TTAProgram::Address startAddress_
Definition: ControlFlowGraph.hh:320
ControlFlowGraph::hasMultipleUnconditionalSuccessors
bool hasMultipleUnconditionalSuccessors(const BasicBlockNode &node) const
Definition: ControlFlowGraph.cc:3103
TTAProgram::CodeSnippet::remove
virtual void remove(Instruction &ins)
Definition: CodeSnippet.cc:558
CFGStatistics::maxInstructionCount
virtual int maxInstructionCount() const
Definition: CFGStatistics.cc:74
ControlFlowGraph::updateReferencesFromProcToCfg
void updateReferencesFromProcToCfg()
Definition: ControlFlowGraph.cc:2207
ControlFlowGraph::computeLeadersFromRefManager
void computeLeadersFromRefManager(InstructionAddressMap &leaders, const TTAProgram::Procedure &procedure)
Definition: ControlFlowGraph.cc:351
TTAProgram::BasicBlockStatistics::setImmediateCount
virtual void setImmediateCount(int)
Definition: BasicBlock.cc:220
TTAProgram::InstructionReferenceManager::createReference
InstructionReference createReference(Instruction &ins)
Definition: InstructionReferenceManager.cc:73
ControlFlowGraph::irm_
TTAProgram::InstructionReferenceManager * irm_
Definition: ControlFlowGraph.hh:343
ControlFlowEdge::CFGEdgePredicate
CFGEdgePredicate
Definition: ControlFlowEdge.hh:52
TTAProgram::DataMemory::dataDefinitionCount
int dataDefinitionCount() const
Definition: DataMemory.cc:129
Operation::numberOfInputs
virtual int numberOfInputs() const
Definition: Operation.cc:192
TTAProgram::Terminal::isBasicBlockReference
virtual bool isBasicBlockReference() const
Definition: Terminal.cc:139
TTAProgram::Move::bus
const TTAMachine::Bus & bus() const
Definition: Move.cc:373
TTAProgram::TerminalRegister::isImmediateRegister
virtual bool isImmediateRegister() const
DataDependenceGraph.hh
TTAProgram::Move::setGuard
void setGuard(MoveGuard *guard)
Definition: Move.cc:360
MoveNode
Definition: MoveNode.hh:65
ControlFlowGraph::createBlock
BasicBlockNode & createBlock(TTAProgram::Instruction &leader, const TTAProgram::Instruction &endBlock)
Definition: ControlFlowGraph.cc:540
ControlFlowEdge::isBackEdge
bool isBackEdge() const
Definition: ControlFlowEdge.cc:179
ControlFlowGraph::ControlFlowGraph
ControlFlowGraph(const TCEString name, TTAProgram::Program *program=NULL)
Definition: ControlFlowGraph.cc:145
Application::verboseLevel
static int verboseLevel()
Definition: Application.hh:176
CFGStatistics::setNormalBBCount
virtual void setNormalBBCount(int)
Definition: CFGStatistics.cc:138
TTAProgram::CodeSnippet::startAddress
virtual Address startAddress() const
Definition: CodeSnippet.cc:780
ControlFlowGraph::ReturnSource
std::pair< InstructionAddress, ControlFlowEdge::CFGEdgePredicate > ReturnSource
Definition: ControlFlowGraph.hh:201
CFGStatistics::normalBBCount
virtual int normalBBCount() const
Definition: CFGStatistics.cc:90
Terminal.hh
Application::logStream
static std::ostream & logStream()
Definition: Application.cc:155
BoostGraph< BasicBlockNode, ControlFlowEdge >::addNode
virtual void addNode(Node &node)
BasicBlockNode::isScheduled
bool isScheduled() const
Definition: BasicBlockNode.hh:93
ControlFlowGraph::splitBasicBlockAtIndex
BasicBlockNode * splitBasicBlockAtIndex(BasicBlockNode &bbn, int index)
Definition: ControlFlowGraph.cc:2878
TTAProgram::Terminal::instructionReference
virtual const InstructionReference & instructionReference() const
Definition: Terminal.cc:188
ControlFlowGraph::programOperationToMIMap_
std::map< ProgramOperation *, llvm::MachineInstr * > programOperationToMIMap_
For LLVM conversion: mapping of created MachineInstructions to TCE ProgramOperations.
Definition: ControlFlowGraph.hh:355
TTAProgram::BasicBlockStatistics::setBypassedCount
virtual void setBypassedCount(int)
Definition: BasicBlock.cc:239
BoostGraph< BasicBlockNode, ControlFlowEdge >::edgeCount
int edgeCount() const
ControlFlowGraph::instructionReferenceManager
TTAProgram::InstructionReferenceManager & instructionReferenceManager()
Definition: ControlFlowGraph.cc:2401
BoostGraph< BasicBlockNode, ControlFlowEdge >::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
ControlFlowEdge::isNormalEdge
bool isNormalEdge() const
Definition: ControlFlowEdge.cc:108
TTAProgram::TerminalInstructionReference::equals
virtual bool equals(const Terminal &other) const
Definition: TerminalInstructionReference.cc:122
ControlFlowEdge::isTrueEdge
bool isTrueEdge() const
Definition: ControlFlowEdge.cc:119
ControlFlowGraph::indirectJump
void indirectJump(InstructionAddressMap &leaders, const InstructionAddress &leaderAddr, InstructionAddressMap &dataCodeRellocations, int insIndex, int moveIndex, const TTAProgram::Procedure &procedure)
Definition: ControlFlowGraph.cc:779
TTAProgram::Instruction::hasCall
bool hasCall() const
Definition: Instruction.cc:438
Conversion::toString
static std::string toString(const T &source)
NotAvailable
Definition: Exception.hh:728
TTAMachine::ImmediateUnit::latency
virtual int latency() const
Definition: ImmediateUnit.cc:155
ControlFlowGraph::directJump
void directJump(InstructionAddressMap &leaders, const InstructionAddress &leaderAddr, int insIndex, int moveIndex, const TTAProgram::Instruction &instructionTarget, const TTAProgram::Procedure &procedure)
Definition: ControlFlowGraph.cc:679
ControlFlowGraph::DFSBackEdgeVisitor
DFS visitor which when finding back edge marks such edge as back edge.
Definition: ControlFlowGraph.hh:205
TTAProgram::TerminalProgramOperation::programOperation
ProgramOperationPtr programOperation() const
Definition: TerminalProgramOperation.hh:57
ControlFlowGraph::createJumps
void createJumps(InstructionAddressMap &leaders, const InstructionAddress &leaderAddr, InstructionAddressMap &dataCodeRellocations, const TTAProgram::Procedure &procedure, int insIndex, int moveIndex)
Definition: ControlFlowGraph.cc:1190
BoostGraph< BasicBlockNode, ControlFlowEdge >::edgeDescriptors_
EdgeDescMap edgeDescriptors_
Definition: BoostGraph.hh:340
ControlFlowGraph::bbMap_
std::map< const TTAProgram::BasicBlock *, llvm::MachineBasicBlock * > bbMap_
Definition: ControlFlowGraph.hh:347
ControlFlowEdge
Definition: ControlFlowEdge.hh:50
ProgramOperationPtr
std::shared_ptr< ProgramOperation > ProgramOperationPtr
Definition: MoveNode.hh:52
TerminalRegister.hh
BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree
virtual int outDegree(const Node &node) const
ControlFlowEdge::CFLOW_EDGE_NORMAL
@ CFLOW_EDGE_NORMAL
Definition: ControlFlowEdge.hh:53
BasicBlockNode::statistics
const TTAProgram::BasicBlockStatistics & statistics()
Definition: BasicBlockNode.cc:267
POMDisassembler.hh
BoostGraph< BasicBlockNode, ControlFlowEdge >::moveInEdge
virtual void moveInEdge(const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
BoostGraph< BasicBlockNode, ControlFlowEdge >::disconnectNodes
virtual void disconnectNodes(const Node &nTail, const Node &nHead)
BasicBlockNode::basicBlock
TTAProgram::BasicBlock & basicBlock()
Definition: BasicBlockNode.cc:126
TTAProgram::Program::hasProcedure
bool hasProcedure(const std::string &name) const
Definition: Program.cc:673
TTAProgram::Immediate::destination
const Terminal & destination() const
Definition: Immediate.cc:92
assert
#define assert(condition)
Definition: Application.hh:86
ControlFlowGraph::removeEntryExitEdge
void removeEntryExitEdge()
Definition: ControlFlowGraph.cc:1125
TTAMachine::FunctionUnit
Definition: FunctionUnit.hh:55
ControlFlowGraph::findUnreachableNodes
NodeSet findUnreachableNodes(const NodeSet &reachableNodes)
Definition: ControlFlowGraph.cc:2503
ControlFlowGraph::findJumpAddress
TTAProgram::Terminal * findJumpAddress(BasicBlockNode &src, ControlFlowEdge &e)
Definition: ControlFlowGraph.cc:3006
TTAMachine::HWOperation::port
virtual FUPort * port(int operand) const
Definition: HWOperation.cc:320
UniversalMachine.hh
TTAProgram::Terminal::isImmediateRegister
virtual bool isImmediateRegister() const
Definition: Terminal.cc:97
TTAProgram::BasicBlockStatistics
Definition: BasicBlock.hh:55
TCEString::ciEqual
bool ciEqual(const TCEString &other) const
Definition: TCEString.cc:63
ControlFlowGraph::ReversedGraph
reverse_graph< ControlFlowGraph::Graph > ReversedGraph
Definition: ControlFlowGraph.hh:197
BasicBlockNode::maximumSize
int maximumSize() const
Definition: BasicBlockNode.cc:384
TTAProgram::Program::nextProcedure
Procedure & nextProcedure(const Procedure &proc) const
Definition: Program.cc:250
TTAProgram::Immediate
Definition: Immediate.hh:54
TTAMachine::Machine::controlUnit
virtual ControlUnit * controlUnit() const
Definition: Machine.cc:345
TTAProgram::BasicBlock::skippedFirstInstructions
int skippedFirstInstructions() const
Definition: BasicBlock.cc:88
abortWithError
#define abortWithError(message)
Definition: Application.hh:72
HWOperation.hh
TTAProgram::BasicBlock::setTripCount
void setTripCount(unsigned count)
Definition: BasicBlock.hh:109
TTAProgram::BasicBlock::skipFirstInstructions
void skipFirstInstructions(int count)
Definition: BasicBlock.cc:98
TTAMachine::SpecialRegisterPort
Definition: SpecialRegisterPort.hh:48
TTAProgram::Move::isControlFlowMove
bool isControlFlowMove() const
Definition: Move.cc:233
TTAMachine::HWOperation::name
const std::string & name() const
Definition: HWOperation.cc:141
ControlFlowGraph::InstructionAddressMap
hash_map< InstructionAddress, const TTAProgram::Instruction * > InstructionAddressMap
Definition: ControlFlowGraph.hh:193
TTAProgram::Move::isCall
bool isCall() const
Definition: Move.cc:190
InvalidData
Definition: Exception.hh:149
BoostGraph< BasicBlockNode, ControlFlowEdge >::EdgeSet
std::set< ControlFlowEdge *, typename ControlFlowEdge ::Comparator > EdgeSet
Definition: BoostGraph.hh:87
Instruction.hh
BoostGraph< BasicBlockNode, ControlFlowEdge >::removeNode
virtual void removeNode(Node &node)
TTAProgram::BasicBlock::liveRangeData_
LiveRangeData * liveRangeData_
Definition: BasicBlock.hh:111
TTAProgram::Program::moveProcedure
void moveProcedure(Procedure &proc, int howMuch)
Definition: Program.cc:588
DataMemory.hh
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
ControlFlowGraph.hh
BasicBlockNode::successor
const BasicBlockNode * successor() const
Definition: BasicBlockNode.hh:120
TTAMachine::ControlUnit
Definition: ControlUnit.hh:50
TTAProgram::BasicBlockStatistics::immediateCount
virtual int immediateCount() const
Definition: BasicBlock.cc:185
ControlFlowGraph::addExit
void addExit()
Definition: ControlFlowGraph.cc:922
InterPassDatum.hh
TTAProgram::CodeSnippet::add
virtual void add(Instruction *ins)
Definition: CodeSnippet.cc:432
Conversion.hh
BoostGraph< BasicBlockNode, ControlFlowEdge >::connectingEdge
EdgeDescriptor connectingEdge(const Node &nTail, const Node &nHead) const
TTAProgram::DataDefinition::destinationAddress
virtual Address destinationAddress() const
Definition: DataDefinition.cc:241
ControlFlowGraph::hasInstructionAnotherJump
bool hasInstructionAnotherJump(const TTAProgram::Instruction &ins, int moveIndex)
Definition: ControlFlowGraph.cc:758
TTAMachine::Port
Definition: Port.hh:54
TTAProgram::Instruction::copy
Instruction * copy() const
Definition: Instruction.cc:379
ControlFlowGraph::findRelJumpDistance
int findRelJumpDistance(const BasicBlockNode &src, const TTAProgram::Terminal &jumpAddr, const TTAMachine::Machine &mach) const
Definition: ControlFlowGraph.cc:3137
TTAProgram::Terminal::isProgramOperationReference
virtual bool isProgramOperationReference() const
Definition: Terminal.cc:144
TTAProgram::InstructionReferenceManager::hasReference
bool hasReference(Instruction &ins) const
Definition: InstructionReferenceManager.cc:143
TTAProgram::Program::dataMemory
DataMemory & dataMemory(int index) const
Definition: Program.cc:967
LiveRangeData
Definition: LiveRangeData.hh:47
TTAProgram::InstructionReferenceManager::replace
void replace(Instruction &insA, Instruction &insB)
Definition: InstructionReferenceManager.cc:96
Application.hh
TTAProgram::Move::guard
MoveGuard & guard() const
Definition: Move.cc:345
NullInstruction.hh
DataDependenceGraph::nodeOfMove
MoveNode & nodeOfMove(const TTAProgram::Move &move)
Definition: DataDependenceGraph.cc:3600
IllegalProgram
Definition: Exception.hh:895
BoostGraph< BasicBlockNode, ControlFlowEdge >::moveOutEdges
virtual void moveOutEdges(const Node &source, const Node &destination)
ControlFlowEdge::setPredicate
void setPredicate(CFGEdgePredicate pred)
Definition: ControlFlowEdge.hh:81
__func__
#define __func__
Definition: Application.hh:67
TTAProgram::CodeSnippet::previousInstruction
virtual Instruction & previousInstruction(const Instruction &ins) const
Definition: CodeSnippet.cc:352
LiveRangeData::inlineAsmRegUses_
std::set< TCEString > inlineAsmRegUses_
Definition: LiveRangeData.hh:126
TTAProgram::Instruction::parent
CodeSnippet & parent() const
Definition: Instruction.cc:109
ControlFlowGraph::computeLeadersFromJumpSuccessors
bool computeLeadersFromJumpSuccessors(InstructionAddressMap &leaders, const TTAProgram::Procedure &procedure)
Definition: ControlFlowGraph.cc:444
BasicBlockNode::updateReferencesFromProcToCfg
void updateReferencesFromProcToCfg(TTAProgram::Program &prog)
Definition: BasicBlockNode.cc:331
ControlFlowGraph::fallThroughPredecessor
BasicBlockNode * fallThroughPredecessor(const BasicBlockNode &bbn) const
Definition: ControlFlowGraph.cc:1379
TTAMachine::Machine::functionUnitNavigator
virtual FunctionUnitNavigator functionUnitNavigator() const
Definition: Machine.cc:380
DataDependenceGraph::removeNode
void removeNode(MoveNode &node)
Definition: DataDependenceGraph.cc:2843
BasicBlockNode
Definition: BasicBlockNode.hh:64
TTAProgram::BasicBlock::isEmpty
bool isEmpty()
Definition: BasicBlock.hh:98
ControlFlowEdge::CFLOW_EDGE_FAKE
@ CFLOW_EDGE_FAKE
Definition: ControlFlowEdge.hh:57
BasicBlockNode::isEntryBB
bool isEntryBB() const
Definition: BasicBlockNode.cc:248
TTAProgram::TerminalInstructionReference
Definition: TerminalInstructionReference.hh:48
BasicBlockNode::isNormalBB
bool isNormalBB() const
Definition: BasicBlockNode.cc:239
ControlFlowGraph::blocks_
hash_map< InstructionAddress, BasicBlockNode * > blocks_
Definition: ControlFlowGraph.hh:326
TTAProgram::CodeSnippet::lastInstruction
virtual Instruction & lastInstruction() const
Definition: CodeSnippet.cc:387
TTAProgram::Terminal::isGPR
virtual bool isGPR() const
Definition: Terminal.cc:107
InterPassData
Definition: InterPassData.hh:48
Guard.hh
Operation.hh
ControlFlowGraph::firstNormalNode
BasicBlockNode & firstNormalNode() const
Definition: ControlFlowGraph.cc:1033
TTAProgram::Terminal::value
virtual SimValue value() const
Definition: Terminal.cc:178
TTAProgram::Terminal::immediateUnit
virtual const TTAMachine::ImmediateUnit & immediateUnit() const
Definition: Terminal.cc:240
TerminalFUPort.hh
TTAProgram::Procedure::clear
void clear()
Definition: Procedure.cc:345
TTAProgram::Address::location
InstructionAddress location() const
ControlFlowGraph::jumpSuccessor
BasicBlockNode * jumpSuccessor(BasicBlockNode &bbn)
Definition: ControlFlowGraph.cc:2411
ControlFlowEdge::CFGEdgeType
CFGEdgeType
Definition: ControlFlowEdge.hh:59
TTAProgram::Move
Definition: Move.hh:55
TTAMachine::ControlUnit::delaySlots
int delaySlots() const
Machine.hh
ControlFlowGraph::isSingleBBLoop
bool isSingleBBLoop(const BasicBlockNode &node) const
Definition: ControlFlowGraph.cc:2919
ModuleRunTimeError
Definition: Exception.hh:1043
TTAProgram::ProgramAnnotation::ANN_LOOP_TRIP_COUNT
@ ANN_LOOP_TRIP_COUNT
An instruction annotated with this annotation is the first instruction of a basic block in a loop wit...
Definition: ProgramAnnotation.hh:165
CFGStatistics::setMaxInstructionCount
virtual void setMaxInstructionCount(int)
Definition: CFGStatistics.cc:119
ControlFlowGraph::allScheduledInBetween
bool allScheduledInBetween(const BasicBlockNode &src, const BasicBlockNode &dst) const
Definition: ControlFlowGraph.cc:3178
BoostGraph< BasicBlockNode, ControlFlowEdge >::inDegree
virtual int inDegree(const Node &node) const
CFGStatistics::setMaxImmediateCount
virtual void setMaxImmediateCount(int)
Definition: CFGStatistics.cc:109
ControlFlowGraph::convertBBRefsToInstRefs
void convertBBRefsToInstRefs()
Definition: ControlFlowGraph.cc:2436
Operation
Definition: Operation.hh:59
TTAProgram::Instruction::immediate
Immediate & immediate(int i) const
Definition: Instruction.cc:285
TTAProgram::Immediate::setValue
void setValue(TerminalImmediate *value)
Definition: Immediate.cc:114
TTAProgram::AnnotatedInstructionElement::hasAnnotations
bool hasAnnotations(ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID) const
Definition: AnnotatedInstructionElement.cc:165
BoostGraph< BasicBlockNode, ControlFlowEdge >::inEdges
virtual EdgeSet inEdges(const Node &node) const
BoostGraph< BasicBlockNode, ControlFlowEdge >::connectingEdges
EdgeSet connectingEdges(const Node &nTail, const Node &nHead) const
GraphBase< BasicBlockNode, ControlFlowEdge >::writeToDotFile
virtual void writeToDotFile(const TCEString &fileName) const
TTAProgram::Program::dataMemoryCount
int dataMemoryCount() const
Definition: Program.cc:942
ControlFlowGraph::exitNode
BasicBlockNode & exitNode() const
Definition: ControlFlowGraph.cc:1058
TTAProgram::CodeSnippet
Definition: CodeSnippet.hh:59
TTAProgram::TerminalFUPort
Definition: TerminalFUPort.hh:56
CFGStatistics::maxImmediateCount
virtual int maxImmediateCount() const
Definition: CFGStatistics.cc:66
ControlFlowGraph::computeLeadersFromRelocations
void computeLeadersFromRelocations(InstructionAddressMap &leaderSet, InstructionAddressMap &dataCodeRellocations, const TTAProgram::Procedure &procedure)
Definition: ControlFlowGraph.cc:397
ControlFlowGraph::findLLVMTargetInstrDesc
const llvm::MCInstrDesc & findLLVMTargetInstrDesc(TCEString name, const llvm::MCInstrInfo &tii) const
Definition: ControlFlowGraph.cc:1881
TTAProgram::Terminal::functionUnit
virtual const TTAMachine::FunctionUnit & functionUnit() const
Definition: Terminal.cc:251
TTAProgram::TerminalProgramOperation::label
TCEString label() const
Definition: TerminalProgramOperation.hh:77
ControlFlowEdge::edgePredicate
CFGEdgePredicate edgePredicate() const
Definition: ControlFlowEdge.hh:83
ControlFlowGraph::sanitize
void sanitize()
Definition: ControlFlowGraph.cc:2938
ControlFlowGraph::procedureName_
TCEString procedureName_
Definition: ControlFlowGraph.hh:317
TTAProgram::BasicBlockStatistics::setMoveCount
virtual void setMoveCount(int)
Definition: BasicBlock.cc:210
BoostGraph< BasicBlockNode, ControlFlowEdge >::edge
virtual Edge & edge(const int index) const
BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdges
virtual EdgeSet outEdges(const Node &node) const
TTAProgram::ProgramAnnotation::ANN_LOOP_INNER
@ ANN_LOOP_INNER
An instruction annotated with this annotation is the first instruction of a basic block in an inner l...
Definition: ProgramAnnotation.hh:168
ControlFlowGraph::getMBB
llvm::MachineBasicBlock & getMBB(llvm::MachineFunction &mf, const TTAProgram::BasicBlock &bb) const
Definition: ControlFlowGraph.cc:2829
TTAProgram::TerminalFUPort::programOperation
ProgramOperationPtr programOperation() const
Definition: TerminalFUPort.hh:97
TTAProgram::AnnotatedInstructionElement::annotation
ProgramAnnotation annotation(int index, ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID) const
Definition: AnnotatedInstructionElement.cc:100
BasicBlockNode::setScheduled
void setScheduled(bool state=true)
Definition: BasicBlockNode.hh:94
TTAProgram::BasicBlock
Definition: BasicBlock.hh:85
ControlFlowGraph::findReachableNodes
NodeSet findReachableNodes()
Definition: ControlFlowGraph.cc:1415
TerminalProgramOperation.hh
MapTools::containsKey
static bool containsKey(const MapType &aMap, const KeyType &aKey)
POMDisassembler::disassemble
static std::string disassemble(const TTAProgram::Move &move)
Definition: POMDisassembler.cc:629
TTAProgram::TerminalRegister::equals
virtual bool equals(const Terminal &other) const
Definition: TerminalRegister.cc:158
LiveRangeData.hh
CodeGenerator.hh
TTAProgram::InstructionReferenceManager
Definition: InstructionReferenceManager.hh:82
TTAProgram::Program::instructionReferenceManager
InstructionReferenceManager & instructionReferenceManager() const
Definition: Program.cc:688
ControlFlowGraph::detectBackEdges
void detectBackEdges()
Definition: ControlFlowGraph.cc:2426
BasicBlockNode::predecessor
const BasicBlockNode * predecessor() const
Definition: BasicBlockNode.hh:121
ControlFlowEdge::isCallPassEdge
bool isCallPassEdge() const
Definition: ControlFlowEdge.cc:138
Program.hh
TTAProgram::Terminal::toString
virtual TCEString toString() const =0
TerminalImmediate.hh
Immediate.hh
ControlFlowGraph::hasIncomingExternalJumps
bool hasIncomingExternalJumps(const BasicBlockNode &bbn) const
Definition: ControlFlowGraph.cc:2253
AssocTools::append
static void append(const ContainerType &src, ContainerType &dest)
InterPassData.hh
TTAMachine::Component::machine
virtual Machine * machine() const
Address.hh
ControlFlowGraph::copyToLLVMMachineFunction
void copyToLLVMMachineFunction(llvm::MachineFunction &mf, TTAProgram::InstructionReferenceManager *irm=NULL)
Definition: ControlFlowGraph.cc:1679
ControlFlowGraph::tpos_
std::set< std::pair< ProgramOperationPtr, llvm::MCSymbol * > > tpos_
For LLVM conversion: the dummy label instructions for SPU should be created for with the given MCSymb...
Definition: ControlFlowGraph.hh:351
InstructionReference.hh
TTAProgram::CodeSnippet::parent
virtual Program & parent() const
Definition: CodeSnippet.cc:118
ControlFlowGraph::InsMap
hash_map< TTAProgram::Instruction *, TTAProgram::Instruction * > InsMap
Definition: ControlFlowGraph.hh:330
TCEString
Definition: TCEString.hh:53
FUPort.hh
TTAMachine::HWOperation::parentUnit
FunctionUnit * parentUnit() const
Definition: HWOperation.cc:190
BasicBlock.hh
TTAProgram::Instruction::immediateCount
int immediateCount() const
Definition: Instruction.cc:267
ControlUnit.hh
ControlFlowGraph::statistics
const CFGStatistics & statistics()
Definition: ControlFlowGraph.cc:1308
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
TTAProgram::TerminalFUPort::hwOperation
virtual const TTAMachine::HWOperation * hwOperation() const
Definition: TerminalFUPort.cc:379
ControlFlowGraph::fallThruSuccessor
BasicBlockNode * fallThruSuccessor(const BasicBlockNode &bbn) const
Definition: ControlFlowGraph.cc:1358
R
static RegisterPass< MachineDCE > R("machinedce","Symbol string based machine DCE for removing not used emulation functions", false, true)
SpecialRegisterPort.hh
ControlFlowEdge::CFLOW_EDGE_FALSE
@ CFLOW_EDGE_FALSE
Definition: ControlFlowEdge.hh:55
TTAProgram::DataMemory::dataDefinition
DataDefinition & dataDefinition(Address address) const
Definition: DataMemory.cc:79
ControlFlowGraph::entryNode
BasicBlockNode & entryNode() const
Definition: ControlFlowGraph.cc:1003
TTAProgram::CodeGenerator
Definition: CodeGenerator.hh:53
TTAProgram::Terminal::basicBlock
virtual const BasicBlock & basicBlock() const
Definition: Terminal.cc:261
InstructionReferenceManager.hh
TTAProgram::Procedure::name
TCEString name() const
Definition: Procedure.hh:66
ControlFlowGraph::optimizeBBOrdering
void optimizeBBOrdering(bool removeDeadCode, TTAProgram::InstructionReferenceManager &irm, DataDependenceGraph *ddg)
Definition: ControlFlowGraph.cc:2522
ControlFlowGraph::procedureName
TCEString procedureName() const
Definition: ControlFlowGraph.cc:1150
TTAProgram::Terminal
Definition: Terminal.hh:60
TTAProgram::CodeSnippet::endAddress
virtual Address endAddress() const
Definition: CodeSnippet.cc:788
TTAProgram::CodeSnippet::instructionAtIndex
virtual Instruction & instructionAtIndex(int index) const
Definition: CodeSnippet.cc:285
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
TTAProgram::BasicBlockStatistics::bypassedCount
virtual int bypassedCount() const
Definition: BasicBlock.cc:201
TTAProgram::BasicBlockStatistics::instructionCount
virtual int instructionCount() const
Definition: BasicBlock.cc:193
BoostGraph< BasicBlockNode, ControlFlowEdge >::graph_
Graph graph_
The internal graph structure.
Definition: BoostGraph.hh:331
TTAProgram::Instruction::hasControlFlowMove
bool hasControlFlowMove() const
Definition: Instruction.cc:471
BoostGraph
Definition: BoostGraph.hh:83
TTAProgram::CodeSnippet::toString
virtual std::string toString() const
Definition: CodeSnippet.hh:117
TTAProgram::Terminal::port
virtual const TTAMachine::Port & port() const
Definition: Terminal.cc:378
TTAMachine::Machine::Navigator::item
ComponentType * item(int index) const
ControlFlowGraph::LAST_ELEMENT_REMOVED
@ LAST_ELEMENT_REMOVED
jump removed, other things remain in BB
Definition: ControlFlowGraph.hh:299
program
find Finds info of the inner loops in the program
Definition: InnerLoopFinder.cc:80
TTAProgram::Terminal::isCodeSymbolReference
virtual bool isCodeSymbolReference() const
Definition: Terminal.cc:154
TTAMachine::HWOperation::latency
int latency() const
Definition: HWOperation.cc:216
Conversion::toInt
static int toInt(const T &source)
ControlFlowGraph::addEntryExitEdge
void addEntryExitEdge()
Definition: ControlFlowGraph.cc:1097
ControlFlowGraph::createControlFlowEdge
ControlFlowEdge & createControlFlowEdge(const TTAProgram::Instruction &iTail, const TTAProgram::Instruction &iHead, ControlFlowEdge::CFGEdgePredicate edgePredicate=ControlFlowEdge::CFLOW_EDGE_NORMAL, ControlFlowEdge::CFGEdgeType edgeType=ControlFlowEdge::CFLOW_EDGE_JUMP)
Definition: ControlFlowGraph.cc:618
TTAProgram::Program::lastProcedure
Procedure & lastProcedure() const
Definition: Program.cc:230
TTAProgram::ProgramAnnotation
Definition: ProgramAnnotation.hh:49
TTAProgram::Move::isJump
bool isJump() const
Definition: Move.cc:164
ControlFlowGraph::mergeNodes
void mergeNodes(BasicBlockNode &node1, BasicBlockNode &node2, DataDependenceGraph *ddg, const ControlFlowEdge &connectingEdge)
Definition: ControlFlowGraph.cc:2762
TTAProgram::CodeSnippet::instructionAt
virtual Instruction & instructionAt(UIntWord address) const
Definition: CodeSnippet.cc:241
OperationPool
Definition: OperationPool.hh:52
TTAProgram::DataMemory
Definition: DataMemory.hh:56
Move.hh
ControlFlowGraph::addExitFromSinkNodes
void addExitFromSinkNodes(BasicBlockNode *exitNode)
Definition: ControlFlowGraph.cc:966
TTAProgram::InstructionReferenceManager::begin
Iterator begin()
TTAProgram::BasicBlock::setInInnerLoop
void setInInnerLoop(bool inner=true)
Definition: BasicBlock.hh:104
TTAProgram::Terminal::isImmediate
virtual bool isImmediate() const
Definition: Terminal.cc:63
TTAProgram::Terminal::isRA
virtual bool isRA() const
Definition: Terminal.cc:129
BoostGraph< BasicBlockNode, ControlFlowEdge >::name
virtual const TCEString & name() const
CFGStatistics::setMaxBypassedCount
virtual void setMaxBypassedCount(int)
Definition: CFGStatistics.cc:128
TTAProgram::MoveGuard
Definition: MoveGuard.hh:47
ControlFlowGraph::splitBB
BasicBlockNode * splitBB(BasicBlockNode &n, int remainingSize)
Definition: ControlFlowGraph.cc:3075
ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH
@ CFLOW_EDGE_FALLTHROUGH
Definition: ControlFlowEdge.hh:62
BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount
int nodeCount() const
ControlFlowEdge::CFLOW_EDGE_TRUE
@ CFLOW_EDGE_TRUE
Definition: ControlFlowEdge.hh:54
CFGStatistics.hh
BoostGraph< BasicBlockNode, ControlFlowEdge >::descriptor
EdgeDescriptor descriptor(const Edge &e) const
TTAProgram::TerminalProgramOperation
Definition: TerminalProgramOperation.hh:51
TTAProgram::InstructionReference
Definition: InstructionReference.hh:49
TTAProgram::Program::procedure
Procedure & procedure(int index) const
Definition: Program.cc:622
ControlFlowEdge::CFLOW_EDGE_CALL
@ CFLOW_EDGE_CALL
Definition: ControlFlowEdge.hh:61
TTAProgram::Procedure
Definition: Procedure.hh:55
ControlFlowGraph::procedure_
const TTAProgram::Procedure * procedure_
Definition: ControlFlowGraph.hh:319
BoostGraph< BasicBlockNode, ControlFlowEdge >::successors
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
Operation::numberOfOutputs
virtual int numberOfOutputs() const
Definition: Operation.cc:202
TTAProgram::DataDefinition::isInstructionAddress
virtual bool isInstructionAddress() const
Definition: DataDefinition.cc:231
DataDefinition.hh
ControlFlowGraph::JUMP_NOT_REMOVED
@ JUMP_NOT_REMOVED
Definition: ControlFlowGraph.hh:297
ControlFlowEdge::isFalseEdge
bool isFalseEdge() const
Definition: ControlFlowEdge.cc:129
ControlFlowGraph::deleteNodeAndRefs
void deleteNodeAndRefs(BasicBlockNode &node)
Definition: ControlFlowGraph.cc:2395
ControlFlowEdge::CFLOW_EDGE_JUMP
@ CFLOW_EDGE_JUMP
Definition: ControlFlowEdge.hh:60
ControlFlowGraph::program_
TTAProgram::Program * program_
Definition: ControlFlowGraph.hh:318
DataDependenceGraph::hasAllRegisterAntidependencies
bool hasAllRegisterAntidependencies()
Definition: DataDependenceGraph.hh:379
BasicBlockNode::originalStartAddress
InstructionAddress originalStartAddress() const
Definition: BasicBlockNode.cc:162
TTAProgram::Instruction::moveCount
int moveCount() const
Definition: Instruction.cc:176
CompilerWarnings.hh
TTAProgram::TerminalRegister
Definition: TerminalRegister.hh:53
TTAProgram::Instruction::address
Address address() const
Definition: Instruction.cc:327
BasicBlockNode::toString
std::string toString() const
Definition: BasicBlockNode.cc:185
TTAProgram::Procedure::alignment
int alignment() const
Definition: Procedure.cc:89
TTAProgram::Move::setSource
void setSource(Terminal *src)
Definition: Move.cc:312
ControlFlowGraph::incomingJumpEdges
EdgeSet incomingJumpEdges(const BasicBlockNode &bbn) const
Definition: ControlFlowGraph.cc:2265
TTAProgram::CodeSnippet::isInProgram
virtual bool isInProgram() const
Definition: CodeSnippet.cc:151
TTAMachine::Machine
Definition: Machine.hh:73
ControlFlowGraph::createBBEdges
void createBBEdges(const TTAProgram::Procedure &procedure, InstructionAddressMap &leaders, InstructionAddressMap &dataCodeRellocations)
Definition: ControlFlowGraph.cc:240
FunctionUnit.hh
ControlFlowGraph::removeUnreachableNodes
void removeUnreachableNodes(const NodeSet &unreachableNodes, DataDependenceGraph *ddg)
Definition: ControlFlowGraph.cc:2740
CFGStatistics::setMaxMoveCount
virtual void setMaxMoveCount(int)
Definition: CFGStatistics.cc:99
DataDependenceGraph::hasIntraBBRegisterAntidependencies
bool hasIntraBBRegisterAntidependencies()
Definition: DataDependenceGraph.hh:387
ControlFlowGraph::hasFallThruPredecessor
bool hasFallThruPredecessor(const BasicBlockNode &bbn)
Definition: ControlFlowGraph.cc:1401
MoveGuard.hh
TTAMachine::ImmediateUnit
Definition: ImmediateUnit.hh:50