OpenASIP  2.0
Classes | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Friends | List of all members
ControlFlowGraph Class Reference

#include <ControlFlowGraph.hh>

Inheritance diagram for ControlFlowGraph:
Inheritance graph
Collaboration diagram for ControlFlowGraph:
Collaboration graph

Classes

class  DFSBackEdgeVisitor
 DFS visitor which when finding back edge marks such edge as back edge. More...
 

Public Member Functions

 ControlFlowGraph (const TCEString name, TTAProgram::Program *program=NULL)
 
 ControlFlowGraph (const TTAProgram::Procedure &procedure, InterPassData &passData)
 
 ControlFlowGraph (const TTAProgram::Procedure &procedure)
 
virtual ~ControlFlowGraph ()
 
TCEString procedureName () const
 
int alignment () const
 
TTAProgram::Program * program () const
 
BasicBlockNode & entryNode () const
 
BasicBlockNode & exitNode () const
 
BasicBlockNode & firstNormalNode () const
 
TCEString printStatistics ()
 
const CFGStatistics & statistics ()
 
void copyToProcedure (TTAProgram::Procedure &proc, TTAProgram::InstructionReferenceManager *irm=NULL)
 
void copyToLLVMMachineFunction (llvm::MachineFunction &mf, TTAProgram::InstructionReferenceManager *irm=NULL)
 
void updateReferencesFromProcToCfg ()
 
void convertBBRefsToInstRefs ()
 
ControlFlowEdge * incomingFTEdge (const BasicBlockNode &bbn) const
 
EdgeSet incomingJumpEdges (const BasicBlockNode &bbn) const
 
bool hasIncomingExternalJumps (const BasicBlockNode &bbn) const
 
void deleteNodeAndRefs (BasicBlockNode &node)
 
TTAProgram::InstructionReferenceManager & instructionReferenceManager ()
 
void setInstructionReferenceManager (TTAProgram::InstructionReferenceManager &irm)
 
BasicBlockNode * jumpSuccessor (BasicBlockNode &bbn)
 
BasicBlockNode * fallThruSuccessor (const BasicBlockNode &bbn) const
 
BasicBlockNode * fallThroughPredecessor (const BasicBlockNode &bbn) const
 
void addExitFromSinkNodes (BasicBlockNode *exitNode)
 
void detectBackEdges ()
 
void reverseGuardOnOutEdges (const BasicBlockNode &bbn)
 
void optimizeBBOrdering (bool removeDeadCode, TTAProgram::InstructionReferenceManager &irm, DataDependenceGraph *ddg)
 
llvm::MachineBasicBlock & getMBB (llvm::MachineFunction &mf, const TTAProgram::BasicBlock &bb) const
 
void splitBasicBlocksWithCallsAndRefs ()
 
bool isSingleBBLoop (const BasicBlockNode &node) const
 
bool hasMultipleUnconditionalSuccessors (const BasicBlockNode &node) const
 
void addExit (NodeSet &retSourceNodes)
 
void sanitize ()
 
TTAProgram::Immediate * findLimmWrite (TTAProgram::Move &move, BasicBlockNode &bb, int moveIndex)
 
TTAProgram::Terminal * findJumpAddress (BasicBlockNode &src, ControlFlowEdge &e)
 
BasicBlockNode * splitBB (BasicBlockNode &n, int remainingSize)
 
bool hasFallThruPredecessor (const BasicBlockNode &bbn)
 
int findRelJumpDistance (const BasicBlockNode &src, const TTAProgram::Terminal &jumpAddr, const TTAMachine::Machine &mach) const
 
bool allScheduledInBetween (const BasicBlockNode &src, const BasicBlockNode &dst) const
 
- Public Member Functions inherited from BoostGraph< BasicBlockNode, ControlFlowEdge >
 BoostGraph (bool allowLoopEdges=true)
 
 BoostGraph (const TCEString &name, bool allowLoopEdges=true)
 
 BoostGraph (const BoostGraph &other, bool allowLoopEdges=true)
 
 ~BoostGraph ()
 
int nodeCount () const
 
int edgeCount () const
 
Node & node (const int index) const
 
Node & node (const int index, bool cacheResult) const
 
virtual Edge & edge (const int index) const
 
virtual void addNode (Node &node)
 
virtual Edge & outEdge (const Node &node, const int index) const
 
virtual Edge & inEdge (const Node &node, const int index) const
 
virtual EdgeSet outEdges (const Node &node) const
 
virtual EdgeSet inEdges (const Node &node) const
 
virtual EdgeSet rootGraphOutEdges (const Node &node) const
 
virtual EdgeSet rootGraphInEdges (const Node &node) const
 
virtual Edge & rootGraphInEdge (const Node &node, const int index) const
 
virtual Edge & rootGraphOutEdge (const Node &node, const int index) const
 
virtual int rootGraphInDegree (const Node &node) const
 
virtual int rootGraphOutDegree (const Node &node) const
 
virtual int outDegree (const Node &node) const
 
virtual int inDegree (const Node &node) const
 
virtual Node & tailNode (const Edge &edge) const
 
virtual Node & headNode (const Edge &edge) const
 
virtual void connectNodes (const Node &nTail, const Node &nHead, Edge &e)
 
virtual void disconnectNodes (const Node &nTail, const Node &nHead)
 
virtual void moveInEdges (const Node &source, const Node &destination)
 
virtual void moveOutEdges (const Node &source, const Node &destination)
 
virtual void moveInEdge (const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
 
virtual void moveOutEdge (const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false)
 
virtual void copyInEdge (const Node &destination, Edge &edge, const Node *tail=NULL)
 
virtual void copyOutEdge (const Node &destination, Edge &edge, const Node *head=NULL)
 
virtual void removeNode (Node &node)
 
virtual void removeEdge (Edge &e)
 
virtual void dropNode (Node &node)
 
virtual void dropEdge (Edge &edge)
 
virtual bool hasEdge (const Node &nTail, const Node &nHead) const
 
virtual NodeSet rootNodes () const
 useful utility functions More...
 
virtual NodeSet sinkNodes () const
 
virtual NodeSet successors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
 
virtual NodeSet predecessors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
 
int maxPathLength (const BasicBlockNode &node) const
 
int maxSinkDistance (const BasicBlockNode &node) const
 
int maxSourceDistance (const BasicBlockNode &node) const
 
bool isInCriticalPath (const BasicBlockNode &node) const
 
int height () const
 
void findAllPaths () const
 
void detachSubgraph (BoostGraph &subGraph)
 
BoostGraph * parentGraph ()
 
BoostGraph * rootGraph ()
 
const BoostGraph * rootGraph () const
 
bool hasNode (const Node &) const
 
virtual const TCEString & name () const
 
void setName (const TCEString &newName)
 
bool hasPath (BasicBlockNode &src, const BasicBlockNode &dest) const
 
void restoreNodeFromParent (BasicBlockNode &node)
 
bool detectIllegalCycles () const
 
EdgeSet connectingEdges (const Node &nTail, const Node &nHead) const
 
- Public Member Functions inherited from GraphBase< BasicBlockNode, ControlFlowEdge >
 GraphBase ()
 
virtual ~GraphBase ()
 
virtual TCEString dotString () const
 
virtual void writeToDotFile (const TCEString &fileName) const
 

Private Types

enum  RemovedJumpData { JUMP_NOT_REMOVED = 0, JUMP_REMOVED, LAST_ELEMENT_REMOVED }
 
typedef hash_map< InstructionAddress, const TTAProgram::Instruction * > InstructionAddressMap
 
typedef std::vector< InstructionAddress > InstructionAddressVector
 
typedef reverse_graph< ControlFlowGraph::Graph > ReversedGraph
 
typedef BoostGraph< BasicBlockNode, ControlFlowEdge >::NodeDescriptor NodeDescriptor
 
typedef std::pair< InstructionAddress, ControlFlowEdge::CFGEdgePredicate > ReturnSource
 
typedef std::set< ReturnSource > ReturnSourceSet
 
typedef hash_map< TTAProgram::Instruction *, TTAProgram::Instruction * > InsMap
 

Private Member Functions

void buildFrom (const TTAProgram::Procedure &procedure)
 
void createBBEdges (const TTAProgram::Procedure &procedure, InstructionAddressMap &leaders, InstructionAddressMap &dataCodeRellocations)
 
ReversedGraph & reversedGraph () const
 
bool hasInstructionAnotherJump (const TTAProgram::Instruction &ins, int moveIndex)
 
void computeLeadersFromRefManager (InstructionAddressMap &leaders, const TTAProgram::Procedure &procedure)
 
bool computeLeadersFromJumpSuccessors (InstructionAddressMap &leaders, const TTAProgram::Procedure &procedure)
 
void computeLeadersFromRelocations (InstructionAddressMap &leaderSet, InstructionAddressMap &dataCodeRellocations, const TTAProgram::Procedure &procedure)
 
void createAllBlocks (InstructionAddressMap &leaders, const TTAProgram::Procedure &procedure)
 
BasicBlockNode & createBlock (TTAProgram::Instruction &leader, const TTAProgram::Instruction &endBlock)
 
ControlFlowEdge & createControlFlowEdge (const TTAProgram::Instruction &iTail, const TTAProgram::Instruction &iHead, ControlFlowEdge::CFGEdgePredicate edgePredicate=ControlFlowEdge::CFLOW_EDGE_NORMAL, ControlFlowEdge::CFGEdgeType edgeType=ControlFlowEdge::CFLOW_EDGE_JUMP)
 
void directJump (InstructionAddressMap &leaders, const InstructionAddress &leaderAddr, int insIndex, int moveIndex, const TTAProgram::Instruction &instructionTarget, const TTAProgram::Procedure &procedure)
 
void indirectJump (InstructionAddressMap &leaders, const InstructionAddress &leaderAddr, InstructionAddressMap &dataCodeRellocations, int insIndex, int moveIndex, const TTAProgram::Procedure &procedure)
 
void createJumps (InstructionAddressMap &leaders, const InstructionAddress &leaderAddr, InstructionAddressMap &dataCodeRellocations, const TTAProgram::Procedure &procedure, int insIndex, int moveIndex)
 
unsigned int findNextIndex (const TTAProgram::Procedure &proc, int jumpInsIndex, int jumpMoveIndex)
 
void addExit ()
 
void addEntryExitEdge ()
 
void removeEntryExitEdge ()
 
NodeSet findReachableNodes ()
 
NodeSet findUnreachableNodes (const NodeSet &reachableNodes)
 
BasicBlockNode * splitBasicBlockAtIndex (BasicBlockNode &bbn, int index)
 
void removeUnreachableNodes (const NodeSet &unreachableNodes, DataDependenceGraph *ddg)
 
void mergeNodes (BasicBlockNode &node1, BasicBlockNode &node2, DataDependenceGraph *ddg, const ControlFlowEdge &connectingEdge)
 
bool jumpToBBN (const TTAProgram::Terminal &jumpAddr, const BasicBlockNode &bbn) const
 
RemovedJumpData removeJumpToTarget (TTAProgram::CodeSnippet &cs, const TTAProgram::Instruction &target, int idx, DataDependenceGraph *ddg=NULL)
 
const llvm::MCInstrDesc & findLLVMTargetInstrDesc (TCEString name, const llvm::MCInstrInfo &tii) const
 
void buildMBBFromBB (llvm::MachineBasicBlock &mbb, const TTAProgram::BasicBlock &bb) const
 

Private Attributes

TCEString procedureName_
 
TTAProgram::Program * program_
 
const TTAProgram::Procedure * procedure_
 
TTAProgram::Address startAddress_
 
TTAProgram::Address endAddress_
 
int alignment_
 
hash_map< InstructionAddress, BasicBlockNode * > blocks_
 
InsMap originalToCfgInstructions_
 
InsMap cfgToOriginalInstructions_
 
ReturnSourceSet returnSources_
 
InterPassData * passData_
 
TTAProgram::InstructionReferenceManager * irm_
 
std::map< const TTAProgram::BasicBlock *, llvm::MachineBasicBlock * > bbMap_
 
std::set< std::pair< ProgramOperationPtr, llvm::MCSymbol * > > tpos_
 For LLVM conversion: the dummy label instructions for SPU should be created for with the given MCSymbol as argument after building. More...
 
std::map< ProgramOperation *, llvm::MachineInstr * > programOperationToMIMap_
 For LLVM conversion: mapping of created MachineInstructions to TCE ProgramOperations. More...
 

Friends

class ControlDependenceGraph
 
class ProgramDependenceGraph
 

Additional Inherited Members

- Public Types inherited from BoostGraph< BasicBlockNode, ControlFlowEdge >
typedef std::set< BasicBlockNode *, typename BasicBlockNode ::Comparator > NodeSet
 
typedef std::set< ControlFlowEdge *, typename ControlFlowEdge ::Comparator > EdgeSet
 
typedef BasicBlockNode Node
 The (base) node type managed by this graph. More...
 
typedef ControlFlowEdge Edge
 The (base) edge type managed by this graph. More...
 
- Public Types inherited from GraphBase< BasicBlockNode, ControlFlowEdge >
typedef std::set< BasicBlockNode *, typename BasicBlockNode ::Comparator > NodeSet
 
typedef std::set< ControlFlowEdge *, typename ControlFlowEdge ::Comparator > EdgeSet
 
typedef BasicBlockNode Node
 Node type of this graph (possibly, a base class). More...
 
typedef ControlFlowEdge Edge
 Edge type of this graph (possibly, a base class). More...
 
- Protected Types inherited from BoostGraph< BasicBlockNode, ControlFlowEdge >
typedef std::set< RemovedEdgeDatum > RemovedEdgeMap
 
typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, Node *, Edge * > Graph
 Internal graph type, providing actual graph-like operations. This type definition relies on bundled properties of boost library, which need the host compiler to support partial template specialisation. More...
 
typedef boost::graph_traits< Graph > GraphTraits
 Traits characterising the internal graph type. More...
 
typedef GraphTraits::out_edge_iterator OutEdgeIter
 Output edge iterator type. More...
 
typedef GraphTraits::in_edge_iterator InEdgeIter
 Input edge iterator type. More...
 
typedef GraphTraits::edge_iterator EdgeIter
 Iterator type for the list of all edges in the graph. More...
 
typedef GraphTraits::vertex_iterator NodeIter
 Iterator type for the list of all nodes in the graph. More...
 
typedef GraphTraits::edge_descriptor EdgeDescriptor
 Type with which edges of the graph are seen internally. More...
 
typedef GraphTraits::vertex_descriptor NodeDescriptor
 Type with which nodes of the graph are seen internally. More...
 
typedef hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions > EdgeDescMap
 
typedef hash_map< const Node *, NodeDescriptor, GraphHashFunctions > NodeDescMap
 
typedef std::vector< std::vector< int > > PathCache
 
- Protected Member Functions inherited from BoostGraph< BasicBlockNode, ControlFlowEdge >
Node & tailNode (const Edge &edge, const NodeDescriptor &headNode) const
 
Node & headNode (const Edge &edge, const NodeDescriptor &tailNode) const
 
virtual void connectNodes (const Node &nTail, const Node &nHead, Edge &e, GraphBase< BasicBlockNode, ControlFlowEdge > *modifier, bool creatingSG=false)
 
void moveInEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)
 
virtual void moveOutEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)
 
virtual void removeNode (Node &node, BoostGraph *modifierGraph)
 
virtual void removeEdge (Edge &e, const BasicBlockNode *tailNode, const BasicBlockNode *headNode, BoostGraph *modifierGraph=NULL)
 
bool hasEdge (const Node &nTail, const Node &nHead, const Edge &edge) const
 
bool hasEdge (const Edge &edge, const Node *nTail=NULL, const Node *nHead=NULL) const
 
void restoreRemovedEdges (RemovedEdgeMap removedEdges)
 
EdgeDescriptor descriptor (const Edge &e) const
 
NodeDescriptor descriptor (const Node &n) const
 
EdgeDescriptor edgeDescriptor (const NodeDescriptor &tailNode, const Edge &e) const
 
EdgeDescriptor edgeDescriptor (const Edge &e, const NodeDescriptor &headNode) const
 
EdgeDescriptor connectingEdge (const Node &nTail, const Node &nHead) const
 
void replaceNodeWithLastNode (BasicBlockNode &dest)
 
void calculatePathLengths () const
 
void calculatePathLengthsFast () const
 
void calculateSinkDistance (const BasicBlockNode &node, int len, bool looping=false) const
 
void calculateSourceDistances (const BasicBlockNode *startNode=NULL, int startingLength=0, bool looping=false) const
 
void calculatePathLengthsOnConnect (const BasicBlockNode &nTail, const BasicBlockNode &nHead, ControlFlowEdge &e)
 
void sinkDistDecreased (const BasicBlockNode &n) const
 
void sourceDistDecreased (const BasicBlockNode &n) const
 
virtual int edgeWeight (ControlFlowEdge &e, const BasicBlockNode &n) const
 
void clearDescriptorCache (EdgeSet edges)
 
void constructSubGraph (BoostGraph &subGraph, NodeSet &nodes)
 
- Protected Attributes inherited from BoostGraph< BasicBlockNode, ControlFlowEdge >
std::map< const BasicBlockNode *, int, typename BasicBlockNode ::Comparator > sourceDistances_
 
std::map< const BasicBlockNode *, int, typename BasicBlockNode ::Comparator > sinkDistances_
 
std::map< const BasicBlockNode *, int, typename BasicBlockNode ::Comparator > loopingSourceDistances_
 
std::map< const BasicBlockNode *, int, typename BasicBlockNode ::Comparator > loopingSinkDistances_
 
int height_
 
Graph graph_
 The internal graph structure. More...
 
EdgeDescMap edgeDescriptors_
 
NodeDescMap nodeDescriptors_
 
BoostGraph< BasicBlockNode, ControlFlowEdge > * parentGraph_
 
std::vector< BoostGraph< BasicBlockNode, ControlFlowEdge > * > childGraphs_
 
TCEString name_
 
int sgCounter_
 
std::set< Edge * > ownedEdges_
 
bool allowLoopEdges_
 
PathCache * pathCache_
 

Detailed Description

Control Flow Graph.

The basic blocks are initially in the original program order when traversed with nodeCount()/node().

Definition at line 100 of file ControlFlowGraph.hh.

Member Typedef Documentation

◆ InsMap

typedef hash_map<TTAProgram::Instruction*,TTAProgram::Instruction*> ControlFlowGraph::InsMap
private

Definition at line 330 of file ControlFlowGraph.hh.

◆ InstructionAddressMap

typedef hash_map<InstructionAddress, const TTAProgram::Instruction*> ControlFlowGraph::InstructionAddressMap
private

Definition at line 193 of file ControlFlowGraph.hh.

◆ InstructionAddressVector

typedef std::vector<InstructionAddress> ControlFlowGraph::InstructionAddressVector
private

Definition at line 194 of file ControlFlowGraph.hh.

◆ NodeDescriptor

typedef BoostGraph<BasicBlockNode, ControlFlowEdge>::NodeDescriptor ControlFlowGraph::NodeDescriptor
private

Definition at line 199 of file ControlFlowGraph.hh.

◆ ReturnSource

typedef std::pair<InstructionAddress, ControlFlowEdge::CFGEdgePredicate> ControlFlowGraph::ReturnSource
private

Definition at line 201 of file ControlFlowGraph.hh.

◆ ReturnSourceSet

typedef std::set<ReturnSource> ControlFlowGraph::ReturnSourceSet
private

Definition at line 202 of file ControlFlowGraph.hh.

◆ ReversedGraph

typedef reverse_graph<ControlFlowGraph::Graph> ControlFlowGraph::ReversedGraph
private

Definition at line 197 of file ControlFlowGraph.hh.

Member Enumeration Documentation

◆ RemovedJumpData

enum ControlFlowGraph::RemovedJumpData
private
Enumerator
JUMP_NOT_REMOVED 
JUMP_REMOVED 

nothing removed

LAST_ELEMENT_REMOVED 

jump removed, other things remain in BB

last jump removed, no immeds in BB.

Definition at line 296 of file ControlFlowGraph.hh.

296  {
297  JUMP_NOT_REMOVED = 0, /// nothing removed
298  JUMP_REMOVED, /// jump removed, other things remain in BB
299  LAST_ELEMENT_REMOVED /// last jump removed, no immeds in BB.
300  };

Constructor & Destructor Documentation

◆ ControlFlowGraph() [1/3]

ControlFlowGraph::ControlFlowGraph ( const TCEString  name,
TTAProgram::Program *  program = NULL 
)

Create empty CFG with given name

Definition at line 145 of file ControlFlowGraph.cc.

147  :
148  BoostGraph<BasicBlockNode, ControlFlowEdge>(name),
149  program_(program),
150  startAddress_(TTAProgram::NullAddress::instance()),
151  endAddress_(TTAProgram::NullAddress::instance()),
152  passData_(NULL) {
153  procedureName_ = name;
154 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::name(), and procedureName_.

Here is the call graph for this function:

◆ ControlFlowGraph() [2/3]

ControlFlowGraph::ControlFlowGraph ( const TTAProgram::Procedure &  procedure,
InterPassData &  passData 
)

Read a procedure of TTA program and build a control flow graph out of it.

A version that allows adding inter pass data with additional data to add to the CFG (currently inner loop BB trip counts).

Create a control flow graph using the procedure of POM. Procedure must be registered in Program to get access to relocations.

Definition at line 184 of file ControlFlowGraph.cc.

186  :
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 }

References buildFrom().

Here is the call graph for this function:

◆ ControlFlowGraph() [3/3]

ControlFlowGraph::ControlFlowGraph ( const TTAProgram::Procedure &  procedure)

Read a procedure of TTA program and build a control flow graph out of it.

Create a control flow graph using the procedure of POM. Procedure must be registered in Program to get access to relocations.

Definition at line 163 of file ControlFlowGraph.cc.

164  :
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 }

References buildFrom().

Here is the call graph for this function:

◆ ~ControlFlowGraph()

ControlFlowGraph::~ControlFlowGraph ( )
virtual

Removes nodes and edge from the graph.

Removal of nodes automatically frees also the edges.

Todo:
: this routine is O(n�)

Definition at line 133 of file ControlFlowGraph.cc.

133  {
134  while (nodeCount() > 0) {
135  BasicBlockNode* b = &node(0);
136  removeNode(*b);
137  delete b;
138  }
139 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::removeNode().

Here is the call graph for this function:

Member Function Documentation

◆ addEntryExitEdge()

void ControlFlowGraph::addEntryExitEdge ( )
private

Create a "false" edge between Entry and Exit. Replaces edges from Entry to graph with "true" edges. This is not strictly part of Control Flow Graph, it is used during construction of control dependencies.

The entry node is connected to exit node

Definition at line 1097 of file ControlFlowGraph.cc.

1097  {
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));
1109  ControlFlowEdge* edge = new ControlFlowEdge(
1110  ControlFlowEdge::CFLOW_EDGE_TRUE);
1111  connectNodes(entry, *(fromEntry[i].first), *edge);
1112  }
1113  ControlFlowEdge* edge = new ControlFlowEdge(
1114  ControlFlowEdge::CFLOW_EDGE_FALSE);
1115  connectNodes(entryNode(), exitNode(), *edge);
1116 }

References ControlFlowEdge::CFLOW_EDGE_FALSE, ControlFlowEdge::CFLOW_EDGE_TRUE, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::disconnectNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edge(), entryNode(), exitNode(), BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge().

Referenced by ControlDependenceGraph::createPostDominanceTree().

Here is the call graph for this function:

◆ addExit() [1/2]

void ControlFlowGraph::addExit ( )
private

Adds artificial block named 'Exit' to the graph

Definition at line 922 of file ControlFlowGraph.cc.

922  {
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 =
946  new ControlFlowEdge(i->second, ControlFlowEdge::CFLOW_EDGE_JUMP);
947  connectNodes(blockSource, *exit, *theEdge);
948  }
949 
950  addExitFromSinkNodes(exit);
951 }

References __func__, addExitFromSinkNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::addNode(), blocks_, ControlFlowEdge::CFLOW_EDGE_JUMP, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), MapTools::containsKey(), Application::logStream(), returnSources_, Conversion::toString(), and Application::verboseLevel().

Referenced by buildFrom().

Here is the call graph for this function:

◆ addExit() [2/2]

void ControlFlowGraph::addExit ( NodeSet &  retSourceNodes)

Referenced by llvm::LLVMTCEIRBuilder::buildTCECFG(), and ProgramDependenceGraph::processEntry().

◆ addExitFromSinkNodes()

void ControlFlowGraph::addExitFromSinkNodes ( BasicBlockNode *  exitNode)

Definition at line 966 of file ControlFlowGraph.cc.

966  {
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) {
972  ControlFlowEdge* edge = new ControlFlowEdge(
973  ControlFlowEdge::CFLOW_EDGE_NORMAL,
974  ControlFlowEdge::CFLOW_EDGE_CALL);
975  connectNodes(block, *exitNode, *edge);
976  }
977  }
978 }

References ControlFlowEdge::CFLOW_EDGE_CALL, ControlFlowEdge::CFLOW_EDGE_NORMAL, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edge(), exitNode(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree().

Referenced by addExit().

Here is the call graph for this function:

◆ alignment()

int ControlFlowGraph::alignment ( ) const

Returns alignment value copied from original POM procedure

Returns
The alignment of procedure.

Definition at line 1160 of file ControlFlowGraph.cc.

1160  {
1161  return alignment_;
1162 }

References alignment_.

Referenced by ControlDependenceGraph::ControlDependenceGraph().

◆ allScheduledInBetween()

bool ControlFlowGraph::allScheduledInBetween ( const BasicBlockNode &  src,
const BasicBlockNode &  dst 
) const

Definition at line 3178 of file ControlFlowGraph.cc.

3179  {
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 }

References BasicBlockNode::isNormalBB(), BasicBlockNode::isScheduled(), and BasicBlockNode::successor().

Referenced by BBSchedulerController::handleCFGDDG().

Here is the call graph for this function:

◆ buildFrom()

void ControlFlowGraph::buildFrom ( const TTAProgram::Procedure &  procedure)
private

Constructs the CFG from the given procedure.

While finding jump successors, also test if there is indirect jump in procedure, in such case also rellocations are used to find basic block starts.

Definition at line 200 of file ControlFlowGraph.cc.

200  {
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)) {
219  computeLeadersFromRelocations(
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 }

References addExit(), TTAProgram::Procedure::alignment(), alignment_, computeLeadersFromJumpSuccessors(), computeLeadersFromRefManager(), computeLeadersFromRelocations(), createAllBlocks(), createBBEdges(), detectBackEdges(), TTAProgram::CodeSnippet::endAddress(), endAddress_, TTAProgram::CodeSnippet::isInProgram(), TTAProgram::Procedure::name(), TTAProgram::CodeSnippet::parent(), procedure_, procedureName_, program_, TTAProgram::CodeSnippet::startAddress(), and startAddress_.

Referenced by ControlFlowGraph().

Here is the call graph for this function:

◆ buildMBBFromBB()

void ControlFlowGraph::buildMBBFromBB ( llvm::MachineBasicBlock &  mbb,
const TTAProgram::BasicBlock &  bb 
) const
private

Definition at line 1893 of file ControlFlowGraph.cc.

1895  {
1896 
1897 #ifdef DEBUG_POM_TO_MI
1898  Application::logStream()
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) {
1926  TTAMachine::FunctionUnit* fu = mach->functionUnitNavigator().item(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()) {
1945  TTAProgram::TerminalFUPort& tfup =
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()) {
2126  const TTAProgram::TerminalProgramOperation& tpo =
2127  dynamic_cast<
2128  const TTAProgram::TerminalProgramOperation&>(
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 {
2165  abortWithError(
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 }

References abortWithError, assert, TTAProgram::Terminal::basicBlock(), TTAProgram::Move::bus(), TTAProgram::Move::destination(), findLLVMTargetInstrDesc(), TTAProgram::Terminal::functionUnit(), TTAMachine::Machine::functionUnitNavigator(), getMBB(), TTAProgram::TerminalFUPort::hwOperation(), TTAProgram::Terminal::index(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), SimValue::intValue(), TTAProgram::Terminal::isBasicBlockReference(), TTAProgram::Terminal::isCodeSymbolReference(), TTAProgram::Terminal::isFUPort(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediate(), TTAProgram::Instruction::isNOP(), TTAProgram::Terminal::isProgramOperationReference(), TTAProgram::Terminal::isRA(), TTAProgram::Move::isTriggering(), TTAMachine::Machine::Navigator< ComponentType >::item(), TTAProgram::TerminalProgramOperation::label(), TTAMachine::HWOperation::latency(), Application::logStream(), TTAMachine::Component::machine(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAMachine::HWOperation::name(), Operation::name(), Operation::numberOfInputs(), Operation::numberOfOutputs(), OperationPool::operation(), TTAMachine::HWOperation::parentUnit(), TTAMachine::HWOperation::port(), TTAProgram::Terminal::port(), PRINT_VAR, TTAProgram::TerminalProgramOperation::programOperation(), TTAProgram::TerminalFUPort::programOperation(), programOperationToMIMap_, TTAProgram::BasicBlock::skippedFirstInstructions(), TTAProgram::Move::source(), TCEString::split(), TCEString::startsWith(), Conversion::toInt(), TTAProgram::Terminal::toString(), TTAProgram::CodeSnippet::toString(), tpos_, and TTAProgram::Terminal::value().

Referenced by copyToLLVMMachineFunction().

Here is the call graph for this function:

◆ computeLeadersFromJumpSuccessors()

bool ControlFlowGraph::computeLeadersFromJumpSuccessors ( InstructionAddressMap &  leaders,
const TTAProgram::Procedure &  procedure 
)
private

Computes starts of basic blocks which follows jumps or calls or are targets of jump.

Also detect if any of jumps is indirect, which will require data-code rellocation information for creating jumps as well.

Parameters
leadersSet of leader instructions to update.
procedureThe procedure to analyse.
Returns
true indicates there is indirect jump in procedure

Definition at line 444 of file ControlFlowGraph.cc.

446  {
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 =
465  m.source().instructionReference().instruction();
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 }

References TTAProgram::Instruction::address(), findNextIndex(), indirectJump(), TTAProgram::InstructionReference::instruction(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Terminal::instructionReference(), TTAProgram::Move::isControlFlowMove(), TTAProgram::Terminal::isGPR(), TTAProgram::Terminal::isImmediateRegister(), TTAProgram::Terminal::isInstructionAddress(), TTAProgram::Move::isJump(), TTAProgram::Address::location(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), and TTAProgram::Move::source().

Referenced by buildFrom().

Here is the call graph for this function:

◆ computeLeadersFromRefManager()

void ControlFlowGraph::computeLeadersFromRefManager ( InstructionAddressMap &  leaders,
const TTAProgram::Procedure &  procedure 
)
private

Internal helper. Find the leader instructions from program reference manager. Should also find startAddress of procedure.

Parameters
leadersSet of leader instructions to update.
procedureThe procedure to analyse, uses it's parent() program to find referenceManager.

Definition at line 351 of file ControlFlowGraph.cc.

353  {
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 }

References __func__, TTAProgram::Instruction::address(), assert, TTAProgram::InstructionReferenceManager::begin(), TTAProgram::InstructionReferenceManager::end(), endAddress_, TTAProgram::CodeSnippet::firstInstruction(), TTAProgram::Program::instructionReferenceManager(), TTAProgram::CodeSnippet::isInProgram(), TTAProgram::Address::location(), TTAProgram::CodeSnippet::parent(), TTAProgram::Instruction::parent(), and startAddress_.

Referenced by buildFrom().

Here is the call graph for this function:

◆ computeLeadersFromRelocations()

void ControlFlowGraph::computeLeadersFromRelocations ( InstructionAddressMap &  leaders,
InstructionAddressMap &  dataCodeRellocations,
const TTAProgram::Procedure &  procedure 
)
private

Internal helper. Finds the leader instructions that are referred to via addressed stored in data memory and recorded as data-to-code relocation entries.

Adds to a given instruction set all instructions whose address is stored in data memory (thus are potential targets of an indirect jump) and is recorded in a data-to-code relocation entry.

Parameters
leadersSet of leader instructions to update.
dataCodeRellocationsSet of dataCodeRellocations that applies for given procedure
procedureThe procedure to analyse, uses it's parent() program to access data memory

Definition at line 397 of file ControlFlowGraph.cc.

400  {
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 }

References __func__, TTAProgram::DataMemory::dataDefinition(), TTAProgram::DataMemory::dataDefinitionCount(), TTAProgram::Program::dataMemory(), TTAProgram::Program::dataMemoryCount(), TTAProgram::DataDefinition::destinationAddress(), endAddress_, TTAProgram::CodeSnippet::instructionAt(), TTAProgram::CodeSnippet::isInProgram(), TTAProgram::DataDefinition::isInstructionAddress(), TTAProgram::Address::location(), TTAProgram::CodeSnippet::parent(), program(), and startAddress_.

Referenced by buildFrom().

Here is the call graph for this function:

◆ convertBBRefsToInstRefs()

void ControlFlowGraph::convertBBRefsToInstRefs ( )

Definition at line 2436 of file ControlFlowGraph.cc.

2436  {
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++) {
2445  TTAProgram::Instruction& ins = bb.instructionAtIndex(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(
2456  new TTAProgram::TerminalInstructionReference(
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(
2471  new TTAProgram::TerminalInstructionReference(
2472  instructionReferenceManager().createReference(
2473  target.firstInstruction())));
2474  }
2475  }
2476  }
2477  }
2478  }
2479 }

References assert, TTAProgram::Terminal::basicBlock(), BasicBlockNode::basicBlock(), TTAProgram::CodeSnippet::firstInstruction(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), instructionReferenceManager(), TTAProgram::Terminal::isBasicBlockReference(), BasicBlockNode::isNormalBB(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), TTAProgram::Move::setSource(), TTAProgram::Immediate::setValue(), TTAProgram::Move::source(), and TTAProgram::Immediate::value().

Referenced by llvm::LLVMTCEIRBuilder::compileOptimized(), and llvm::LLVMTCEIRBuilder::writeMachineFunction().

Here is the call graph for this function:

◆ copyToLLVMMachineFunction()

void ControlFlowGraph::copyToLLVMMachineFunction ( llvm::MachineFunction &  mf,
TTAProgram::InstructionReferenceManager *  irm = NULL 
)

Copies the CFG into an LLVM MachineFunction.

Assumes an operation triggered target and that all scheduler restrictions to produce valid code for such an target have been enabled in ADF while producing the schedule.

Parameters
mfThe MachineFunction where to copy the cfg.
irmInstructionReferenceManager for resolving instruction refs.

This loop now only creates empty basic blocks in same order as they were transfered from LLVM to POM previously. Actuall copying of the content is done afterwords.

This will create MachineBasicblock corresponding to BB if it does not exists already.

Fill in created machine basic blocks with machine instructions based on corresponding basic blocks.

Add the dummy instructions denoting labels to instructions that are not basic block starts. This is only for the SPU's branch hint instructions at the moment. It instantiates an LLVM/SPU-backend-specific dummy instruction HBR_LABEL at the moment.

Based on CFG edges, add successor information to the generated machine function.

Definition at line 1679 of file ControlFlowGraph.cc.

1681  {
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 
1691  ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
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) {
1699  irm = &program_->instructionReferenceManager();
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) {
1796  writeToDotFile(
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++) {
1825  TTAProgram::BasicBlock& bb = node(j).basicBlock();
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 }

References assert, BasicBlockNode::basicBlock(), buildMBBFromBB(), AssocTools::containsKey(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edgeCount(), entryNode(), fallThruSuccessor(), findLLVMTargetInstrDesc(), findReachableNodes(), getMBB(), hasFallThruPredecessor(), TTAProgram::InstructionReferenceManager::hasReference(), BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), TTAProgram::Program::instructionReferenceManager(), BasicBlockNode::isNormalBB(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdges(), program_, programOperationToMIMap_, TTAProgram::InstructionReferenceManager::replace(), BoostGraph< BasicBlockNode, ControlFlowEdge >::successors(), BoostGraph< BasicBlockNode, ControlFlowEdge >::tailNode(), BasicBlockNode::toString(), tpos_, and GraphBase< BasicBlockNode, ControlFlowEdge >::writeToDotFile().

Referenced by llvm::LLVMTCEIRBuilder::writeMachineFunction().

Here is the call graph for this function:

◆ copyToProcedure()

void ControlFlowGraph::copyToProcedure ( TTAProgram::Procedure &  proc,
TTAProgram::InstructionReferenceManager *  irm = NULL 
)

Copies the CFG into a procedure.

Clears the procedure and replaces all instructions in it with ones in CFG. Tries to get rid of some unnecessary jumps.

Parameters
procprocedure where the copy the cfg.

Definition at line 1448 of file ControlFlowGraph.cc.

1449  {
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;
1460  ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
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) {
1468  irm = &program_->instructionReferenceManager();
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.
1554  RemovedJumpData rjd = removeJumpToTarget(
1555  proc, head.basicBlock().firstInstruction(),
1556  proc.instructionCount() -
1557  (bb.instructionCount() - bb.skippedFirstInstructions()));
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(),
1575  ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
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) {
1617  writeToDotFile(
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 }

References assert, BasicBlockNode::basicBlock(), ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, TTAProgram::Procedure::clear(), BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), TTAProgram::Instruction::copy(), ControlFlowEdge::edgePredicate(), entryNode(), fallThruSuccessor(), findReachableNodes(), findUnreachableNodes(), TTAProgram::CodeSnippet::firstInstruction(), hasFallThruPredecessor(), TTAProgram::InstructionReferenceManager::hasReference(), BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Program::instructionReferenceManager(), TTAProgram::CodeSnippet::isInProgram(), BasicBlockNode::isNormalBB(), JUMP_NOT_REMOVED, LAST_ELEMENT_REMOVED, TTAProgram::Program::lastProcedure(), TTAProgram::Program::moveProcedure(), TTAProgram::Procedure::name(), TTAProgram::Program::nextProcedure(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdges(), TTAProgram::CodeSnippet::parent(), PRINT_VAR, program_, BoostGraph< BasicBlockNode, ControlFlowEdge >::removeEdge(), removeJumpToTarget(), TTAProgram::InstructionReferenceManager::replace(), TTAProgram::BasicBlock::skippedFirstInstructions(), BoostGraph< BasicBlockNode, ControlFlowEdge >::successors(), BasicBlockNode::toString(), TTAProgram::CodeSnippet::toString(), and GraphBase< BasicBlockNode, ControlFlowEdge >::writeToDotFile().

Referenced by ProgramDependenceGraph::disassemble(), SimpleIfConverter::handleProcedure(), PreOptimizer::handleProcedure(), BBSchedulerController::handleProcedure(), and llvm::LLVMTCEIRBuilder::writeMachineFunction().

Here is the call graph for this function:

◆ createAllBlocks()

void ControlFlowGraph::createAllBlocks ( InstructionAddressMap &  leaders,
const TTAProgram::Procedure &  procedure 
)
private

Split Procedure into the set of basic blocks.

Parameters
leadersSet of instructions which starts basic block.
procedureProcedure that is analysed.

Definition at line 503 of file ControlFlowGraph.cc.

505  {
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);
511  InstructionAddressVector
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 }

References createBlock(), TTAProgram::CodeSnippet::instructionAt(), and TTAProgram::CodeSnippet::lastInstruction().

Referenced by buildFrom().

Here is the call graph for this function:

◆ createBBEdges()

void ControlFlowGraph::createBBEdges ( const TTAProgram::Procedure &  procedure,
InstructionAddressMap &  leaders,
InstructionAddressMap &  dataCodeRellocations 
)
private

Creates edges between basic blocks.

Parameters
procedureProcedure that holds the instructions.
leadersLeader instructions, first instructions in basic blocks.
dataCodeRellocationsSet of dataCodeRellocations that applies to the given procedure.

Look for __exit procedure, if it is found, calls to it will not have fall through edges in CFG to avoid possible endless loops and create possible unreachable basic blocks

The __exit procedure was not found, we do not detect calls to __exit in calls

Do not create fall through edge after call to __exit

Definition at line 240 of file ControlFlowGraph.cc.

243  {
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 =
257  program_->procedure("__exit").firstInstruction().address().
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()) {
289  TTAProgram::TerminalInstructionReference* address =
290  dynamic_cast<TTAProgram::TerminalInstructionReference*>
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);
300  createControlFlowEdge(
301  *leaders[leaderAddr], iNext,
302  ControlFlowEdge::CFLOW_EDGE_NORMAL,
303  ControlFlowEdge::CFLOW_EDGE_CALL);
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)) {
330  createControlFlowEdge(
331  *leaders[leaderAddr],nextInstruction,
332  ControlFlowEdge::CFLOW_EDGE_NORMAL,
333  ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
334  }
335  }
336  } else {
337  break;
338  }
339  }
340 }

References TTAProgram::Instruction::address(), blocks_, ControlFlowEdge::CFLOW_EDGE_CALL, ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, ControlFlowEdge::CFLOW_EDGE_NORMAL, MapTools::containsKey(), createControlFlowEdge(), createJumps(), findNextIndex(), TTAProgram::CodeSnippet::firstInstruction(), BoostGraph< BasicBlockNode, ControlFlowEdge >::hasEdge(), TTAProgram::Program::hasProcedure(), TTAProgram::InstructionReference::instruction(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::TerminalInstructionReference::instructionReference(), TTAProgram::Move::isCall(), TTAProgram::CodeSnippet::isInProgram(), TTAProgram::Terminal::isInstructionAddress(), TTAProgram::Move::isJump(), TTAProgram::Address::location(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAProgram::Program::procedure(), program_, TTAProgram::Move::source(), and TTAProgram::CodeSnippet::startAddress().

Referenced by buildFrom().

Here is the call graph for this function:

◆ createBlock()

BasicBlockNode & ControlFlowGraph::createBlock ( TTAProgram::Instruction &  leader,
const TTAProgram::Instruction &  endBlock 
)
private

Internal helper. Create a basic block.

Given the first and last instructions of a basic block, create a new basic block of graph. It is assumed that the graph does not have a basic block for the given pair of instructions yet. If such a block exists, this method aborts.

Parameters
leaderThe first instruction of the basic block to create.
endBlockThe last instruction of the basic block to create.
Returns
The created basic block node.

Definition at line 540 of file ControlFlowGraph.cc.

542  {
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 
580  if (leader.hasAnnotations(TTAProgram::ProgramAnnotation::ANN_LOOP_INNER)) {
581  node->basicBlock().setInInnerLoop();
582  node->basicBlock().setTripCount(0); // 0 indicates unknown trip count
583 
584  if (leader.hasAnnotations(
585  TTAProgram::ProgramAnnotation::ANN_LOOP_TRIP_COUNT)) {
586 
587  unsigned tripCount =
588  static_cast<unsigned>(
589  leader.annotation(
590  0, TTAProgram::ProgramAnnotation::ANN_LOOP_TRIP_COUNT).
591  intValue());
592  if (tripCount > 0) {
593  node->basicBlock().setTripCount(tripCount);
594  }
595  }
596  }
597  blocks_[blockStart] = node;
598  return *node;
599 }

References __func__, TTAProgram::CodeSnippet::add(), BoostGraph< BasicBlockNode, ControlFlowEdge >::addNode(), TTAProgram::Instruction::address(), TTAProgram::ProgramAnnotation::ANN_LOOP_INNER, TTAProgram::ProgramAnnotation::ANN_LOOP_TRIP_COUNT, TTAProgram::AnnotatedInstructionElement::annotation(), BasicBlockNode::basicBlock(), blocks_, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), MapTools::containsKey(), TTAProgram::Instruction::copy(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edge(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::Address::location(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), TTAProgram::Instruction::parent(), TTAProgram::BasicBlock::setInInnerLoop(), TTAProgram::BasicBlock::setTripCount(), TTAProgram::CodeSnippet::startAddress(), and startAddress_.

Referenced by createAllBlocks().

Here is the call graph for this function:

◆ createControlFlowEdge()

ControlFlowEdge & ControlFlowGraph::createControlFlowEdge ( const TTAProgram::Instruction &  iTail,
const TTAProgram::Instruction &  iHead,
ControlFlowEdge::CFGEdgePredicate  edgePredicate = ControlFlowEdge::CFLOW_EDGE_NORMAL,
ControlFlowEdge::CFGEdgeType  edgeType = ControlFlowEdge::CFLOW_EDGE_JUMP 
)
private

Internal helper. Create a control flow edge between two basic blocks.

Given the leader instructions of two basic blocks, create a new control flow edge connecting the blocks. The basic blocks are assumed to be already existing and added to the graph. If either basic block does not exist, this method aborts. A new edge is created even if the blocks are already connected. Thus, parallel edges are possible.

Parameters
iTailThe first instruction of the tail basic block (from).
iHeadThe first instruction of the head basic block (to).
edgePredicateThe value of an edge (true, false, normal, call)
edgeTypeDefines if edge represents jump or call or fall-through, default jump
Returns
The created control flow edge.

Definition at line 618 of file ControlFlowGraph.cc.

622  {
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)
631  % POMDisassembler::disassemble(iTail)
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)
645  % POMDisassembler::disassemble(iTail)
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 }

References __func__, TTAProgram::Instruction::address(), assert, blocks_, ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), MapTools::containsKey(), POMDisassembler::disassemble(), TTAProgram::Address::location(), Application::logStream(), BasicBlockNode::originalEndAddress(), BasicBlockNode::originalStartAddress(), Conversion::toString(), and Application::verboseLevel().

Referenced by createBBEdges(), directJump(), and indirectJump().

Here is the call graph for this function:

◆ createJumps()

void ControlFlowGraph::createJumps ( InstructionAddressMap &  leaders,
const InstructionAddress &  leaderAddr,
InstructionAddressMap &  dataCodeRellocations,
const TTAProgram::Procedure &  procedure,
int  insIndex,
int  moveIndex 
)
private

Helper function to find target address of a jump in case source of jump is immediate register or general purpose register.

Parameters
leadersStarting instructions of all basic blocks
leaderAddrAddress of a first instruction of present Basic Block
dataCodeRellocationsRead from POM, the possible targets of indirect jumps are in data code rellocation information
instructionCurrect instruction containing jump
procedureThe reference to current procedure
moveIndexIndex of move with jump in current instruction
Note
Abort when the source of jump is immediateregister and no write to such register is found in same basic block.

Definition at line 1190 of file ControlFlowGraph.cc.

1196  {
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,
1203  tmp->source().instructionReference().instruction(),
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 }

References __func__, TTAProgram::Instruction::address(), TTAProgram::Immediate::destination(), TTAProgram::Move::destination(), directJump(), TTAProgram::TerminalRegister::equals(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), indirectJump(), TTAProgram::InstructionReference::instruction(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::Terminal::instructionReference(), TTAProgram::Terminal::isFUPort(), TTAProgram::TerminalRegister::isGPR(), TTAProgram::Terminal::isGPR(), TTAProgram::TerminalRegister::isImmediateRegister(), TTAProgram::Terminal::isImmediateRegister(), TTAProgram::Terminal::isInstructionAddress(), TTAProgram::Address::location(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAProgram::CodeSnippet::previousInstruction(), TTAProgram::Move::source(), and TTAProgram::Immediate::value().

Referenced by createBBEdges().

Here is the call graph for this function:

◆ deleteNodeAndRefs()

void ControlFlowGraph::deleteNodeAndRefs ( BasicBlockNode &  node)

Removes and deletes a basic block node from the grpahs and updates all references that point to it to point elsewhere.

Parameters
nodebasic block node to be removed and deleted.

Definition at line 2395 of file ControlFlowGraph.cc.

2395  {
2396  removeNode(node);
2397  delete &node;
2398 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::removeNode().

Referenced by Peel2BBLoops::updateCFG(), and SimpleIfConverter::updateCfg().

Here is the call graph for this function:

◆ detectBackEdges()

void ControlFlowGraph::detectBackEdges ( )

Tests created control flow graph using depth first search algorithm of boost graph library and mark back edges.

Default starting vertex is vertex(g).first, which is actually first basic block created. Entry is created as second and there is connection added from entry to first BB. Using default parameter for root_vertex is therefore sufficient

Definition at line 2426 of file ControlFlowGraph.cc.

2426  {
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 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::graph_.

Referenced by buildFrom(), llvm::LLVMTCEIRBuilder::buildTCECFG(), and optimizeBBOrdering().

◆ directJump()

void ControlFlowGraph::directJump ( InstructionAddressMap &  leaders,
const InstructionAddress &  leaderAddr,
int  insIndex,
int  cfMoveIndex,
const TTAProgram::Instruction &  instructionTarget,
const TTAProgram::Procedure &  procedure 
)
private

Creates edges for direct jump (source is immediate value).

Parameters
leadersSet of beginnings of basic blocks
leaderAddrAddress of beginning of current basic block
instructionInstruction to analyse (only one move in instruction)
procedureProcedure we are working with

Definition at line 679 of file ControlFlowGraph.cc.

684  {
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
726  createControlFlowEdge(
727  *leaders[leaderAddr], instructionTarget,
728  ControlFlowEdge::CFLOW_EDGE_FALSE);
729  if (iNext != NULL) {
730  createControlFlowEdge(
731  *leaders[leaderAddr], *iNext,
732  ControlFlowEdge::CFLOW_EDGE_TRUE,
733  ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
734  }
735  } else {
736  createControlFlowEdge(
737  *leaders[leaderAddr], instructionTarget,
738  ControlFlowEdge::CFLOW_EDGE_TRUE);
739  if (iNext != NULL) {
740  createControlFlowEdge(
741  *leaders[leaderAddr], *iNext,
742  ControlFlowEdge::CFLOW_EDGE_FALSE,
743  ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
744  }
745  }
746  } else {
747  createControlFlowEdge(*leaders[leaderAddr], instructionTarget);
748  }
749 }

References __func__, TTAProgram::Instruction::address(), ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, ControlFlowEdge::CFLOW_EDGE_FALSE, ControlFlowEdge::CFLOW_EDGE_TRUE, MapTools::containsKey(), createControlFlowEdge(), POMDisassembler::disassemble(), findNextIndex(), TTAProgram::Move::guard(), hasInstructionAnotherJump(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::MoveGuard::isInverted(), TTAProgram::Move::isUnconditional(), TTAProgram::Address::location(), TTAProgram::Instruction::move(), and TTAProgram::CodeSnippet::startAddress().

Referenced by createJumps().

Here is the call graph for this function:

◆ entryNode()

BasicBlockNode & ControlFlowGraph::entryNode ( ) const

Return the entry node of the graph.

Returns
The entry node of the graph.
Exceptions
InstanceNotFoundif the graph does not have a entry node.
InvalidDataif the graph has multiple nodes that are recognised as entry nodes.

Definition at line 1003 of file ControlFlowGraph.cc.

1003  {
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 }

References __func__, BoostGraph< BasicBlockNode, ControlFlowEdge >::inDegree(), BasicBlockNode::isEntryBB(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount().

Referenced by addEntryExitEdge(), copyToLLVMMachineFunction(), copyToProcedure(), DataDependenceGraphBuilder::createRegisterDeps(), findReachableNodes(), firstNormalNode(), optimizeBBOrdering(), DataDependenceGraphBuilder::queueFirstBB(), and removeEntryExitEdge().

Here is the call graph for this function:

◆ exitNode()

BasicBlockNode & ControlFlowGraph::exitNode ( ) const

Return the stop/exit node of the graph.

Returns
The stop node of the graph.
Exceptions
InstanceNotFoundif the graph does not have a stop node.
InvalidDataif the graph has multiple nodes that are recognised as stop nodes.

Definition at line 1058 of file ControlFlowGraph.cc.

1058  {
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 }

References __func__, BasicBlockNode::isExitBB(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree().

Referenced by addEntryExitEdge(), addExitFromSinkNodes(), ControlDependenceGraph::createPostDominanceTree(), optimizeBBOrdering(), and removeEntryExitEdge().

Here is the call graph for this function:

◆ fallThroughPredecessor()

BasicBlockNode * ControlFlowGraph::fallThroughPredecessor ( const BasicBlockNode &  bbn) const

Finds a node where control falls thru to the give node.

Parameters
bbnbasic block node whose successor we are searching
Returns
node where control falls thru from given node or NULL if not exist.

Definition at line 1379 of file ControlFlowGraph.cc.

1379  {
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 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::inEdges(), BasicBlockNode::isEntryBB(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::tailNode().

Here is the call graph for this function:

◆ fallThruSuccessor()

BasicBlockNode * ControlFlowGraph::fallThruSuccessor ( const BasicBlockNode &  bbn) const

Finds a node where control falls thru from the give node.

Parameters
bbnbasic block node whose successor we are searching
Returns
node where control falls thru from given node or NULL if not exist.

Definition at line 1358 of file ControlFlowGraph.cc.

1358  {
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 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), BasicBlockNode::isExitBB(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdges().

Referenced by copyToLLVMMachineFunction(), copyToProcedure(), CallsToJumps::handleControlFlowGraph(), and optimizeBBOrdering().

Here is the call graph for this function:

◆ findJumpAddress()

TTAProgram::Terminal * ControlFlowGraph::findJumpAddress ( BasicBlockNode &  src,
ControlFlowEdge &  e 
)

Finds the terminal containing the target address of the jump corresponding to the edge.

Parameters
srcbasic block node which is the tail of the edge, containing the jump.
edgeedge whose target address is being searched.

Definition at line 3006 of file ControlFlowGraph.cc.

3006  {
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;
3015  auto ep = ControlFlowEdge::edgePredicateFromMove(m);
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 }

References assert, BasicBlockNode::basicBlock(), ControlFlowEdge::edgePredicate(), ControlFlowEdge::edgePredicateFromMove(), and findLimmWrite().

Referenced by sanitize().

Here is the call graph for this function:

◆ findLimmWrite()

TTAProgram::Immediate * ControlFlowGraph::findLimmWrite ( TTAProgram::Move &  move,
BasicBlockNode &  bbn,
int  moveIndex 
)

Finds the immediate write which is read by a move.

Parameters
movemove containing the immediate use.
bbnbasic block containing the move
moveIndexindex of the instruction containing the move in the BB.

Definition at line 3037 of file ControlFlowGraph.cc.

3038  {
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 }

References BasicBlockNode::basicBlock(), TTAProgram::Instruction::immediate(), TTAProgram::Instruction::immediateCount(), TTAProgram::Terminal::immediateUnit(), BoostGraph< BasicBlockNode, ControlFlowEdge >::inDegree(), TTAProgram::Terminal::index(), TTAProgram::CodeSnippet::instructionCount(), BasicBlockNode::isNormalBB(), TTAMachine::ImmediateUnit::latency(), BoostGraph< BasicBlockNode, ControlFlowEdge >::predecessors(), and TTAProgram::Move::source().

Referenced by findJumpAddress().

Here is the call graph for this function:

◆ findLLVMTargetInstrDesc()

const llvm::MCInstrDesc & ControlFlowGraph::findLLVMTargetInstrDesc ( TCEString  name,
const llvm::MCInstrInfo &  tii 
) const
private

Finds the TargetInstrDesc for the given LLVM instruction name.

Definition at line 1881 of file ControlFlowGraph.cc.

1883  {
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 }

References abortWithError, TCEString::ciEqual(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::name().

Referenced by buildMBBFromBB(), and copyToLLVMMachineFunction().

Here is the call graph for this function:

◆ findNextIndex()

unsigned int ControlFlowGraph::findNextIndex ( const TTAProgram::Procedure &  proc,
int  jumpInsIndex,
int  jumpMoveIndex 
)
private

Finds the index of the next instruction after jump and delay slots in the procedure.

Also checks for control flow moves in delay slots, and throws if found, or if the procedure ends before all delays slots.

Parameters
procedureprocedure we are processing
jumpInsIndexindex of the jump inside in the procedure
indexof the jump move in the jump instruction.

Definition at line 877 of file ControlFlowGraph.cc.

878  {
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()
911  % POMDisassembler::disassemble(dsIns)
912  ).str());
913  }
914  }
915  return nextIndex;
916 }

References __func__, TTAProgram::Instruction::address(), TTAMachine::ControlUnit::delaySlots(), TTAProgram::Move::destination(), POMDisassembler::disassemble(), TTAProgram::Terminal::functionUnit(), TTAProgram::Instruction::hasControlFlowMove(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Address::location(), TTAProgram::Instruction::move(), and TTAMachine::Component::name().

Referenced by computeLeadersFromJumpSuccessors(), createBBEdges(), directJump(), and indirectJump().

Here is the call graph for this function:

◆ findReachableNodes()

ControlFlowGraph::NodeSet ControlFlowGraph::findReachableNodes ( )
private

Does a breadth first search to find all reachable nodes.

Definition at line 1415 of file ControlFlowGraph.cc.

1415  {
1416  NodeSet queuedBBs;
1417  NodeSet processedBBs;
1418 
1419  ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
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 }

References AssocTools::append(), AssocTools::containsKey(), entryNode(), BasicBlockNode::isNormalBB(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::successors().

Referenced by copyToLLVMMachineFunction(), copyToProcedure(), and optimizeBBOrdering().

Here is the call graph for this function:

◆ findRelJumpDistance()

int ControlFlowGraph::findRelJumpDistance ( const BasicBlockNode &  src,
const TTAProgram::Terminal &  jumpAddr,
const TTAMachine::Machine &  mach 
) const

Definition at line 3137 of file ControlFlowGraph.cc.

3139  {
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 }

References TTAMachine::Machine::controlUnit(), TTAMachine::ControlUnit::delaySlots(), BasicBlockNode::isNormalBB(), jumpToBBN(), BasicBlockNode::maximumSize(), BasicBlockNode::predecessor(), and BasicBlockNode::successor().

Here is the call graph for this function:

◆ findUnreachableNodes()

ControlFlowGraph::NodeSet ControlFlowGraph::findUnreachableNodes ( const NodeSet &  reachableNodes)
private

Definition at line 2503 of file ControlFlowGraph.cc.

2504  {
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 }

References AssocTools::containsKey(), BasicBlockNode::isNormalBB(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount().

Referenced by copyToProcedure(), and optimizeBBOrdering().

Here is the call graph for this function:

◆ firstNormalNode()

BasicBlockNode & ControlFlowGraph::firstNormalNode ( ) const

Definition at line 1033 of file ControlFlowGraph.cc.

1033  {
1034  ControlFlowGraph::NodeSet entrySucc = successors(entryNode());
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 }

References __func__, entryNode(), BasicBlockNode::isNormalBB(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::successors().

Here is the call graph for this function:

◆ getMBB()

llvm::MachineBasicBlock & ControlFlowGraph::getMBB ( llvm::MachineFunction &  mf,
const TTAProgram::BasicBlock &  bb 
) const

Fetch machine basic block corresponding to the BasicBlock passed, if it does not exist create empty one.

Definition at line 2829 of file ControlFlowGraph.cc.

2831  {
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 }

References bbMap_, and MapTools::containsKey().

Referenced by buildMBBFromBB(), copyToLLVMMachineFunction(), and llvm::LLVMTCEIRBuilder::fixJumpTableDestinations().

Here is the call graph for this function:

◆ hasFallThruPredecessor()

bool ControlFlowGraph::hasFallThruPredecessor ( const BasicBlockNode &  bbn)

Returns true if given basic blocks has a predecessor which falls thru to it.

Parameters
bbnbbn to check for fall-thru predecessors
Returns
if control can fall-thru to this BB.

Definition at line 1401 of file ControlFlowGraph.cc.

1401  {
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 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::inEdges().

Referenced by copyToLLVMMachineFunction(), copyToProcedure(), and optimizeBBOrdering().

Here is the call graph for this function:

◆ hasIncomingExternalJumps()

bool ControlFlowGraph::hasIncomingExternalJumps ( const BasicBlockNode &  bbn) const

Tells whether a node has incoming jumps that are not from a single-basic block loop, ie source is not the same node.

Parameters
bbnthe node

Definition at line 2253 of file ControlFlowGraph.cc.

2253  {
2254  ControlFlowGraph::EdgeSet jumpEdges = incomingJumpEdges(bbn);
2255 
2256  for (auto e: jumpEdges) {
2257  if (&tailNode(*e) != &bbn) {
2258  return true;
2259  }
2260  }
2261  return false;
2262 }

References incomingJumpEdges(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::tailNode().

Here is the call graph for this function:

◆ hasInstructionAnotherJump()

bool ControlFlowGraph::hasInstructionAnotherJump ( const TTAProgram::Instruction &  ins,
int  moveIndex 
)
private

Tells whether an instruction has another jump in addition to the given.

Parameters
insinstruction to check
moveIndexindex of the move triggering the known jump.

Definition at line 758 of file ControlFlowGraph.cc.

759  {
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 }

References TTAProgram::Move::isJump(), TTAProgram::Instruction::move(), and TTAProgram::Instruction::moveCount().

Referenced by directJump(), and indirectJump().

Here is the call graph for this function:

◆ hasMultipleUnconditionalSuccessors()

bool ControlFlowGraph::hasMultipleUnconditionalSuccessors ( const BasicBlockNode &  node) const

Definition at line 3103 of file ControlFlowGraph.cc.

3104  {
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 }

References ControlFlowEdge::isNormalEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge().

Here is the call graph for this function:

◆ incomingFTEdge()

ControlFlowEdge * ControlFlowGraph::incomingFTEdge ( const BasicBlockNode &  bbn) const

Return an incoming fall-thru edge to a node. Jump and entry is also considered fall-thru

Parameters
bbnthe node
Returns
the edge or null, if none found.

Definition at line 2233 of file ControlFlowGraph.cc.

2233  {
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 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::descriptor(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edgeDescriptors_, BoostGraph< BasicBlockNode, ControlFlowEdge >::graph_, and ControlFlowEdge::isJumpEdge().

Here is the call graph for this function:

◆ incomingJumpEdges()

ControlFlowGraph::EdgeSet ControlFlowGraph::incomingJumpEdges ( const BasicBlockNode &  bbn) const

Definition at line 2265 of file ControlFlowGraph.cc.

2265  {
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 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::descriptor(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edgeDescriptors_, BoostGraph< BasicBlockNode, ControlFlowEdge >::graph_, and ControlFlowEdge::isJumpEdge().

Referenced by hasIncomingExternalJumps().

Here is the call graph for this function:

◆ indirectJump()

void ControlFlowGraph::indirectJump ( InstructionAddressMap &  leaders,
const InstructionAddress &  leaderAddr,
InstructionAddressMap &  dataCodeRellocations,
int  insIndex,
int  cfMoveIndex,
const TTAProgram::Procedure &  procedure 
)
private

Creates edges for indirect jump (source is NOT immediate value).

Parameters
leadersSet of beginnings of basic blocks
leaderAddrAddress of beginning of current basic block
dataCodeRellocationsRellocation information for targets of jump
instructionInstruction to analyse (only one move in instruction)
procedureProcedure we are working with

Definition at line 779 of file ControlFlowGraph.cc.

784  {
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);
796  createControlFlowEdge(
797  *leaders[leaderAddr], iNext,
798  ControlFlowEdge::CFLOW_EDGE_FAKE);
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 =
809  ControlFlowEdge::CFLOW_EDGE_NORMAL;
810  ControlFlowEdge::CFGEdgePredicate fallPredicate =
811  ControlFlowEdge::CFLOW_EDGE_NORMAL;
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);
834  createControlFlowEdge(
835  *leaders[leaderAddr], iNext,fallPredicate,
836  ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
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.
858  createControlFlowEdge(
859  *leaders[leaderAddr], *(*dataCodeIterator).second,
860  edgePredicate);
861  dataCodeIterator++;
862  }
863 }

References __func__, ControlFlowEdge::CFLOW_EDGE_FAKE, ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, ControlFlowEdge::CFLOW_EDGE_FALSE, ControlFlowEdge::CFLOW_EDGE_NORMAL, ControlFlowEdge::CFLOW_EDGE_TRUE, MapTools::containsKey(), createControlFlowEdge(), findNextIndex(), TTAProgram::Move::guard(), TTAProgram::AnnotatedInstructionElement::hasAnnotations(), hasInstructionAnotherJump(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::MoveGuard::isInverted(), TTAProgram::Move::isUnconditional(), TTAProgram::Address::location(), TTAProgram::Instruction::move(), TTAProgram::Terminal::port(), returnSources_, TTAProgram::Move::source(), and TTAProgram::CodeSnippet::startAddress().

Referenced by computeLeadersFromJumpSuccessors(), and createJumps().

Here is the call graph for this function:

◆ instructionReferenceManager()

TTAProgram::InstructionReferenceManager & ControlFlowGraph::instructionReferenceManager ( )

Definition at line 2401 of file ControlFlowGraph.cc.

2401  {
2402  if (program_ == NULL) {
2403  return *irm_;
2404  throw NotAvailable(__FILE__,__LINE__,__func__,
2405  "cfg does not have program");
2406  }
2407  return program_->instructionReferenceManager();
2408 }

References __func__, TTAProgram::Program::instructionReferenceManager(), irm_, and program_.

Referenced by LoopPrologAndEpilogBuilder::addPrologFromRM(), LoopPrologAndEpilogBuilder::addPrologIntoCfg(), llvm::LLVMTCEIRBuilder::compileOptimized(), convertBBRefsToInstRefs(), ControlFlowGraphPass::executeBasicBlockPass(), BBSchedulerController::handleBBNode(), Peel2BBLoops::handleControlFlowGraph(), CallsToJumps::handleControlFlowGraph(), SimpleIfConverter::handleControlFlowGraph(), and sanitize().

Here is the call graph for this function:

◆ isSingleBBLoop()

bool ControlFlowGraph::isSingleBBLoop ( const BasicBlockNode &  node) const

Definition at line 2919 of file ControlFlowGraph.cc.

2919  {
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 }

References assert, BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), ControlFlowEdge::isBackEdge(), ControlFlowEdge::isJumpEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge().

Referenced by ControlFlowGraphPass::executeBasicBlockPass(), BBSchedulerController::handleBasicBlock(), and BBSchedulerController::handleCFGDDG().

Here is the call graph for this function:

◆ jumpSuccessor()

BasicBlockNode * ControlFlowGraph::jumpSuccessor ( BasicBlockNode &  bbn)

Definition at line 2411 of file ControlFlowGraph.cc.

2411  {
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 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), ControlFlowEdge::isJumpEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge().

Referenced by SimpleIfConverter::detectTriangleViaFt(), and BBSchedulerController::handleCFGDDG().

Here is the call graph for this function:

◆ jumpToBBN()

bool ControlFlowGraph::jumpToBBN ( const TTAProgram::Terminal &  jumpAddr,
const BasicBlockNode &  bbn 
) const
private

Definition at line 3120 of file ControlFlowGraph.cc.

3121  {
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 }

References TTAProgram::Terminal::basicBlock(), BasicBlockNode::basicBlock(), TTAProgram::CodeSnippet::firstInstruction(), TTAProgram::InstructionReference::instruction(), TTAProgram::Terminal::instructionReference(), TTAProgram::Terminal::isBasicBlockReference(), TTAProgram::Terminal::isCodeSymbolReference(), TTAProgram::Terminal::isInstructionAddress(), and BasicBlockNode::isNormalBB().

Referenced by findRelJumpDistance().

Here is the call graph for this function:

◆ mergeNodes()

void ControlFlowGraph::mergeNodes ( BasicBlockNode &  node1,
BasicBlockNode &  node2,
DataDependenceGraph *  ddg,
const ControlFlowEdge &  connectingEdge 
)
private

Definition at line 2762 of file ControlFlowGraph.cc.

2764  {
2765 
2766  if (ddg != NULL &&
2767  (!ddg->hasAllRegisterAntidependencies() &&
2768  ddg->hasIntraBBRegisterAntidependencies())) {
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 }

References TTAProgram::CodeSnippet::add(), assert, BasicBlockNode::basicBlock(), BoostGraph< BasicBlockNode, ControlFlowEdge >::connectingEdge(), DataDependenceGraph::fixInterBBAntiEdges(), DataDependenceGraph::hasAllRegisterAntidependencies(), DataDependenceGraph::hasIntraBBRegisterAntidependencies(), BoostGraph< BasicBlockNode, ControlFlowEdge >::inEdges(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), BasicBlockNode::isNormalBB(), ControlFlowEdge::isNormalEdge(), TTAProgram::BasicBlock::liveRangeData_, LiveRangeData::merge(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), BoostGraph< BasicBlockNode, ControlFlowEdge >::moveInEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::moveOutEdge(), DataDependenceGraph::nodeOfMove(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdges(), TTAProgram::CodeSnippet::remove(), BoostGraph< BasicBlockNode, ControlFlowEdge >::removeNode(), DataDependenceGraph::setBasicBlockNode(), ControlFlowEdge::setPredicate(), TTAProgram::BasicBlock::skippedFirstInstructions(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::tailNode().

Referenced by optimizeBBOrdering().

Here is the call graph for this function:

◆ optimizeBBOrdering()

void ControlFlowGraph::optimizeBBOrdering ( bool  removeDeadCode,
TTAProgram::InstructionReferenceManager &  irm,
DataDependenceGraph *  ddg 
)

The algorithm is same as in CopyToProcedure, but without the copying. Still removes jump, and also does BB mergeing.

Definition at line 2522 of file ControlFlowGraph.cc.

2524  {
2525 
2526 #ifdef DEBUG_BB_OPTIMIZER
2527  writeToDotFile(
2528  (boost::format("%s_before_optimize_cfg.dot") %
2529  name()).str());
2530 #endif
2531 
2532  ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
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.
2628  RemovedJumpData rjd = removeJumpToTarget(
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  }
2641  bb.skipFirstInstructions(bb.instructionCount());
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(),
2670  ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
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
2730  writeToDotFile(
2731  (boost::format("%s_after_optimize_cfg.dot") %
2732  name()).str());
2733 #endif
2734 }

References assert, BasicBlockNode::basicBlock(), ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectingEdges(), BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), detectBackEdges(), ControlFlowEdge::edgePredicate(), entryNode(), exitNode(), fallThruSuccessor(), findReachableNodes(), findUnreachableNodes(), TTAProgram::CodeSnippet::firstInstruction(), hasFallThruPredecessor(), TTAProgram::InstructionReferenceManager::hasReference(), BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), BoostGraph< BasicBlockNode, ControlFlowEdge >::inDegree(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), ControlFlowEdge::isBackEdge(), ControlFlowEdge::isCallPassEdge(), TTAProgram::BasicBlock::isEmpty(), BasicBlockNode::isNormalBB(), BasicBlockNode::isScheduled(), JUMP_NOT_REMOVED, LAST_ELEMENT_REMOVED, BasicBlockNode::link(), mergeNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::name(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdges(), BoostGraph< BasicBlockNode, ControlFlowEdge >::removeEdge(), removeJumpToTarget(), removeUnreachableNodes(), TTAProgram::InstructionReferenceManager::replace(), TTAProgram::BasicBlock::skipFirstInstructions(), BoostGraph< BasicBlockNode, ControlFlowEdge >::successors(), BasicBlockNode::toString(), and GraphBase< BasicBlockNode, ControlFlowEdge >::writeToDotFile().

Referenced by llvm::LLVMTCEIRBuilder::compileOptimized().

Here is the call graph for this function:

◆ printStatistics()

TCEString ControlFlowGraph::printStatistics ( )

Returns basic statistics about control flow graph as a string.

Returns
String with basic statistics about control flow graph.

Definition at line 1286 of file ControlFlowGraph.cc.

1286  {
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 }

References TTAProgram::BasicBlockStatistics::bypassedCount(), TTAProgram::BasicBlockStatistics::immediateCount(), TTAProgram::BasicBlockStatistics::instructionCount(), CFGStatistics::maxBypassedCount(), CFGStatistics::maxImmediateCount(), CFGStatistics::maxInstructionCount(), CFGStatistics::maxMoveCount(), TTAProgram::BasicBlockStatistics::moveCount(), CFGStatistics::normalBBCount(), procedureName(), and statistics().

Here is the call graph for this function:

◆ procedureName()

TCEString ControlFlowGraph::procedureName ( ) const

Returns a name of procedure the graph represents taken from original POM object.

Returns
The name of procedure as a string

Definition at line 1150 of file ControlFlowGraph.cc.

1150  {
1151  return procedureName_;
1152 }

References procedureName_.

Referenced by BBSchedulerController::handleBBNode(), and printStatistics().

◆ program()

TTAProgram::Program * ControlFlowGraph::program ( ) const

Returns a pointer to the POM Program object procedure was part of in POM.

Returns
The pointer to POM Program

Definition at line 1171 of file ControlFlowGraph.cc.

1171  {
1172  return program_;
1173 }

References program_.

Referenced by computeLeadersFromRelocations(), ControlDependenceGraph::ControlDependenceGraph(), and PreOptimizer::handleCFGDDG().

◆ removeEntryExitEdge()

void ControlFlowGraph::removeEntryExitEdge ( )
private

Remove a "false" edge between Entry and Exit after control dependencies are created.

The entry node is connected to exit

Definition at line 1125 of file ControlFlowGraph.cc.

1125  {
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  }
1140  disconnectNodes(entryNode(), exitNode());
1141 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::disconnectNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::edge(), entryNode(), exitNode(), BoostGraph< BasicBlockNode, ControlFlowEdge >::headNode(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge().

Referenced by ControlDependenceGraph::computeDependence(), and ControlDependenceGraph::detectControlDependencies().

Here is the call graph for this function:

◆ removeJumpToTarget()

ControlFlowGraph::RemovedJumpData ControlFlowGraph::removeJumpToTarget ( TTAProgram::CodeSnippet &  cs,
const TTAProgram::Instruction &  target,
int  idx,
DataDependenceGraph *  ddg = NULL 
)
private

Finds a jump that jumps to target from a codesnippet and removes the jump.

Parameters
csCodeSnippet where to remove the jump from.
targetjump target instruction.
idxindex which after to check for existing moves and immeds
Returns
whther not removed, removed and some moves last after idx, or if removed and no moves/immeds left after idx. @TODO should be able to handle also jumps where address is LIMM

Definition at line 2291 of file ControlFlowGraph.cc.

2293  {
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()) {
2307  TTAProgram::TerminalInstructionReference& tia =
2308  dynamic_cast<TTAProgram::TerminalInstructionReference&>(
2309  term);
2310  TTAProgram::InstructionReference& ir =
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 }

References TTAProgram::Move::bus(), TTAProgram::Move::guard(), TTAProgram::Instruction::immediateCount(), TTAProgram::InstructionReference::instruction(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::TerminalInstructionReference::instructionReference(), TTAProgram::Terminal::isInstructionAddress(), TTAProgram::Move::isJump(), TTAProgram::Move::isUnconditional(), JUMP_NOT_REMOVED, JUMP_REMOVED, LAST_ELEMENT_REMOVED, TTAMachine::Component::machine(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), DataDependenceGraph::nodeOfMove(), TTAProgram::Instruction::removeMove(), DataDependenceGraph::removeNode(), TTAProgram::Move::setGuard(), and TTAProgram::Move::source().

Referenced by copyToProcedure(), and optimizeBBOrdering().

Here is the call graph for this function:

◆ removeUnreachableNodes()

void ControlFlowGraph::removeUnreachableNodes ( const NodeSet &  nodes,
DataDependenceGraph *  ddg 
)
private

TODO: what to do with exit node?

Definition at line 2740 of file ControlFlowGraph.cc.

2741  {
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 }

References BasicBlockNode::basicBlock(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), DataDependenceGraph::nodeOfMove(), BoostGraph< BasicBlockNode, ControlFlowEdge >::removeNode(), and DataDependenceGraph::removeNode().

Referenced by optimizeBBOrdering().

Here is the call graph for this function:

◆ reversedGraph()

ControlFlowGraph::ReversedGraph & ControlFlowGraph::reversedGraph ( ) const
private

Creates reversed underlying graph.

Control Flow Graph has member graph_ which stores actual data. This function returns reversed graph_ (edge directions changed).

Returns
Reversed underlying graph.

Definition at line 989 of file ControlFlowGraph.cc.

989  {
990  ReversedGraph* R = new ReversedGraph(graph_);
991  return *R;
992 }

References BoostGraph< BasicBlockNode, ControlFlowEdge >::graph_, and R().

Referenced by ControlDependenceGraph::createPostDominanceTree().

Here is the call graph for this function:

◆ reverseGuardOnOutEdges()

void ControlFlowGraph::reverseGuardOnOutEdges ( const BasicBlockNode &  bbn)

Reverses predicate of outgoing edges.

Definition at line 2486 of file ControlFlowGraph.cc.

2486  {
2487  for (int i = 0; i < outDegree(bbn); i++) {
2488  Edge& e = outEdge(bbn,i);
2489  if (e.isTrueEdge()) {
2490  e.setPredicate(ControlFlowEdge::CFLOW_EDGE_FALSE);
2491  } else if (e.isFalseEdge()) {
2492  e.setPredicate(ControlFlowEdge::CFLOW_EDGE_TRUE);
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 }

References assert, ControlFlowEdge::CFLOW_EDGE_FALSE, ControlFlowEdge::CFLOW_EDGE_TRUE, ControlFlowEdge::isFalseEdge(), ControlFlowEdge::isTrueEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge(), ControlFlowEdge::setPredicate(), ControlFlowEdge::toString(), BasicBlockNode::toString(), and GraphBase< BasicBlockNode, ControlFlowEdge >::writeToDotFile().

Referenced by PreOptimizer::handleCFGDDG().

Here is the call graph for this function:

◆ sanitize()

void ControlFlowGraph::sanitize ( )

Sanitizes CFG back to a format where there are no jumps to middle of a BB, And where the instruction index 0 of all basic blocks really mean the first instructions. The delay slot filler may generate such "insane" CFGs which breaks these. So this should be run after the delay slot filler to make the CFG sane again.

Definition at line 2938 of file ControlFlowGraph.cc.

2938  {
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 =
2976  instructionReferenceManager().createReference(firstIns);
2977  TTAProgram::TerminalInstructionReference tir(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 }

References assert, TTAProgram::InstructionReferenceManager::createReference(), TTAProgram::TerminalInstructionReference::equals(), findJumpAddress(), BoostGraph< BasicBlockNode, ControlFlowEdge >::inEdges(), instructionReferenceManager(), BoostGraph< BasicBlockNode, ControlFlowEdge >::moveInEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), splitBB(), BoostGraph< BasicBlockNode, ControlFlowEdge >::tailNode(), and GraphBase< BasicBlockNode, ControlFlowEdge >::writeToDotFile().

Here is the call graph for this function:

◆ setInstructionReferenceManager()

void ControlFlowGraph::setInstructionReferenceManager ( TTAProgram::InstructionReferenceManager &  irm)
inline

Definition at line 142 of file ControlFlowGraph.hh.

143  {
144  irm_ = &irm;
145  }

References irm_.

Referenced by llvm::LLVMTCEIRBuilder::buildTCECFG(), and llvm::LLVMTCEIRBuilder::writeMachineFunction().

◆ splitBasicBlockAtIndex()

BasicBlockNode * ControlFlowGraph::splitBasicBlockAtIndex ( BasicBlockNode &  bbn,
int  index 
)
private

Definition at line 2878 of file ControlFlowGraph.cc.

2879  {
2880 
2881  TTAProgram::BasicBlock& bb = bbn.basicBlock();
2882  TTAProgram::BasicBlock* newbb = new TTAProgram::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(); ) {
2896  TTAProgram::Instruction& ins = bb.instructionAtIndex(i);
2897  bb.remove(ins);
2898  newbb->add(&ins);
2899  }
2900 
2901  ControlFlowEdge* cfe = new ControlFlowEdge(
2902  ControlFlowEdge::CFLOW_EDGE_NORMAL,
2903  ControlFlowEdge::CFLOW_EDGE_CALL);
2904  connectNodes(bbn, *newbbn, *cfe);
2905 
2906  if (bb.liveRangeData_) {
2907  newbb->liveRangeData_ = new LiveRangeData;
2908  newbb->liveRangeData_->inlineAsmRegUses_ =
2909  bb.liveRangeData_->inlineAsmRegUses_;
2910  newbb->liveRangeData_->inlineAsmRegDefs_ =
2911  bb.liveRangeData_->inlineAsmRegDefs_;
2912  newbb->liveRangeData_->inlineAsmClobbers_ =
2913  bb.liveRangeData_->inlineAsmClobbers_;
2914  }
2915 
2916  return newbbn;
2917 }

References TTAProgram::CodeSnippet::add(), BoostGraph< BasicBlockNode, ControlFlowEdge >::addNode(), BasicBlockNode::basicBlock(), ControlFlowEdge::CFLOW_EDGE_CALL, ControlFlowEdge::CFLOW_EDGE_NORMAL, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), LiveRangeData::inlineAsmClobbers_, LiveRangeData::inlineAsmRegDefs_, LiveRangeData::inlineAsmRegUses_, TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), BasicBlockNode::isScheduled(), TTAProgram::BasicBlock::liveRangeData_, BoostGraph< BasicBlockNode, ControlFlowEdge >::moveOutEdges(), TTAProgram::CodeSnippet::remove(), and BasicBlockNode::setScheduled().

Referenced by splitBasicBlocksWithCallsAndRefs().

Here is the call graph for this function:

◆ splitBasicBlocksWithCallsAndRefs()

void ControlFlowGraph::splitBasicBlocksWithCallsAndRefs ( )

Checks if the basic blocks have calls in the middle of them and splits them to multiple basic blocks with call edge chains.

TCE scheduler assumes there cannot be calls in the middle of basic block.

Definition at line 2850 of file ControlFlowGraph.cc.

2850  {
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 }

References assert, BasicBlockNode::basicBlock(), TTAProgram::Instruction::hasCall(), TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::CodeSnippet::instructionAt(), TTAProgram::CodeSnippet::instructionCount(), irm_, TTAProgram::CodeSnippet::lastInstruction(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), and splitBasicBlockAtIndex().

Referenced by llvm::LLVMTCEIRBuilder::buildTCECFG().

Here is the call graph for this function:

◆ splitBB()

BasicBlockNode * ControlFlowGraph::splitBB ( BasicBlockNode &  n,
int  remainingSize 
)

Splits a basic block into two parts.

Parameters
nbasic block node being splitted
remainingSizeremaining effective size of the first bb, or index of the instruction starting the new BB.
Returns
the created new basic block node.

Definition at line 3075 of file ControlFlowGraph.cc.

3076  {
3077  TTAProgram::BasicBlock& bb = n.basicBlock();
3078  TTAProgram::BasicBlock* nbb = new TTAProgram::BasicBlock();
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(
3096  ControlFlowEdge::CFLOW_EDGE_NORMAL,
3097  ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH)));
3098  n.link(nbbn);
3099  return nbbn;
3100 }

References TTAProgram::CodeSnippet::add(), BoostGraph< BasicBlockNode, ControlFlowEdge >::addNode(), BasicBlockNode::basicBlock(), ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH, ControlFlowEdge::CFLOW_EDGE_NORMAL, BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), TTAProgram::CodeSnippet::instructionCount(), BasicBlockNode::isScheduled(), BasicBlockNode::link(), BoostGraph< BasicBlockNode, ControlFlowEdge >::moveOutEdges(), TTAProgram::CodeSnippet::remove(), BasicBlockNode::setScheduled(), and TTAProgram::BasicBlock::skippedFirstInstructions().

Referenced by sanitize().

Here is the call graph for this function:

◆ statistics()

const CFGStatistics & ControlFlowGraph::statistics ( )

Returns basic statistics about control flow graph in statistic object.

Returns
Object with basic statistics about control flow graph.

Definition at line 1308 of file ControlFlowGraph.cc.

1308  {
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 }

References TTAProgram::BasicBlockStatistics::bypassedCount(), TTAProgram::BasicBlockStatistics::immediateCount(), TTAProgram::BasicBlockStatistics::instructionCount(), BasicBlockNode::isNormalBB(), TTAProgram::BasicBlockStatistics::moveCount(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), TTAProgram::BasicBlockStatistics::setBypassedCount(), TTAProgram::BasicBlockStatistics::setImmediateCount(), TTAProgram::BasicBlockStatistics::setInstructionCount(), CFGStatistics::setMaxBypassedCount(), CFGStatistics::setMaxImmediateCount(), CFGStatistics::setMaxInstructionCount(), CFGStatistics::setMaxMoveCount(), TTAProgram::BasicBlockStatistics::setMoveCount(), CFGStatistics::setNormalBBCount(), and BasicBlockNode::statistics().

Referenced by printStatistics().

Here is the call graph for this function:

◆ updateReferencesFromProcToCfg()

void ControlFlowGraph::updateReferencesFromProcToCfg ( )

Updates instruction references from procedure to cfg Which is constructed from the procedure.

Definition at line 2207 of file ControlFlowGraph.cc.

2207  {
2208 
2209  // make all refs point to the new copied instructions.
2210  for (int i = 0; i < nodeCount(); i++) {
2211  BasicBlockNode& bbn = node(i);
2212  bbn.updateReferencesFromProcToCfg(*program_);
2213  }
2214 
2215 #if 0 // TODO: why does this irm claim to be unuser variable??
2216  InstructionReferenceManager& irm = program_->instructionReferenceManager();
2217  // procedure should not have any references.
2218  for (int i = 0; i < procedure_->instructionCount(); i++) {
2219  assert(!irm.hasReference(procedure_->instructionAtIndex(i)));
2220  }
2221 #endif
2222 }

References assert, TTAProgram::InstructionReferenceManager::hasReference(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Program::instructionReferenceManager(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), procedure_, program_, and BasicBlockNode::updateReferencesFromProcToCfg().

Referenced by SimpleIfConverter::handleProcedure(), PreOptimizer::handleProcedure(), and BBSchedulerController::handleProcedure().

Here is the call graph for this function:

Friends And Related Function Documentation

◆ ControlDependenceGraph

friend class ControlDependenceGraph
friend

Definition at line 121 of file ControlFlowGraph.hh.

◆ ProgramDependenceGraph

friend class ProgramDependenceGraph
friend

Definition at line 122 of file ControlFlowGraph.hh.

Member Data Documentation

◆ alignment_

int ControlFlowGraph::alignment_
private

Definition at line 322 of file ControlFlowGraph.hh.

Referenced by alignment(), and buildFrom().

◆ bbMap_

std::map<const TTAProgram::BasicBlock*, llvm::MachineBasicBlock*> ControlFlowGraph::bbMap_
mutableprivate

Definition at line 347 of file ControlFlowGraph.hh.

Referenced by getMBB().

◆ blocks_

hash_map<InstructionAddress, BasicBlockNode*> ControlFlowGraph::blocks_
private

Definition at line 326 of file ControlFlowGraph.hh.

Referenced by addExit(), createBBEdges(), createBlock(), and createControlFlowEdge().

◆ cfgToOriginalInstructions_

InsMap ControlFlowGraph::cfgToOriginalInstructions_
private

Definition at line 333 of file ControlFlowGraph.hh.

◆ endAddress_

TTAProgram::Address ControlFlowGraph::endAddress_
private

Definition at line 321 of file ControlFlowGraph.hh.

Referenced by buildFrom(), computeLeadersFromRefManager(), and computeLeadersFromRelocations().

◆ irm_

TTAProgram::InstructionReferenceManager* ControlFlowGraph::irm_
private

Definition at line 343 of file ControlFlowGraph.hh.

Referenced by instructionReferenceManager(), setInstructionReferenceManager(), and splitBasicBlocksWithCallsAndRefs().

◆ originalToCfgInstructions_

InsMap ControlFlowGraph::originalToCfgInstructions_
private

Definition at line 332 of file ControlFlowGraph.hh.

◆ passData_

InterPassData* ControlFlowGraph::passData_
private

Definition at line 339 of file ControlFlowGraph.hh.

◆ procedure_

const TTAProgram::Procedure* ControlFlowGraph::procedure_
private

Definition at line 319 of file ControlFlowGraph.hh.

Referenced by buildFrom(), and updateReferencesFromProcToCfg().

◆ procedureName_

TCEString ControlFlowGraph::procedureName_
private

Definition at line 317 of file ControlFlowGraph.hh.

Referenced by buildFrom(), ControlFlowGraph(), and procedureName().

◆ program_

TTAProgram::Program* ControlFlowGraph::program_
private

Definition at line 318 of file ControlFlowGraph.hh.

Referenced by buildFrom(), copyToLLVMMachineFunction(), copyToProcedure(), createBBEdges(), instructionReferenceManager(), program(), and updateReferencesFromProcToCfg().

◆ programOperationToMIMap_

std::map<ProgramOperation*, llvm::MachineInstr*> ControlFlowGraph::programOperationToMIMap_
mutableprivate

For LLVM conversion: mapping of created MachineInstructions to TCE ProgramOperations.

Definition at line 355 of file ControlFlowGraph.hh.

Referenced by buildMBBFromBB(), and copyToLLVMMachineFunction().

◆ returnSources_

ReturnSourceSet ControlFlowGraph::returnSources_
private

Definition at line 336 of file ControlFlowGraph.hh.

Referenced by addExit(), and indirectJump().

◆ startAddress_

TTAProgram::Address ControlFlowGraph::startAddress_
private

Definition at line 320 of file ControlFlowGraph.hh.

Referenced by buildFrom(), computeLeadersFromRefManager(), computeLeadersFromRelocations(), and createBlock().

◆ tpos_

std::set<std::pair<ProgramOperationPtr, llvm::MCSymbol*> > ControlFlowGraph::tpos_
mutableprivate

For LLVM conversion: the dummy label instructions for SPU should be created for with the given MCSymbol as argument after building.

Definition at line 351 of file ControlFlowGraph.hh.

Referenced by buildMBBFromBB(), and copyToLLVMMachineFunction().

The documentation for this class was generated from the following files:
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
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 >::connectNodes
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge
virtual Edge & outEdge(const Node &node, const int index) const
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
TTAProgram::TerminalRegister::isGPR
virtual bool isGPR() const
InstructionAddress
UInt32 InstructionAddress
Definition: BaseType.hh:175
TTAProgram::Instruction::isNOP
bool isNOP() const
Definition: Instruction.hh:90
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
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
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
TTAMachine::HWOperation
Definition: HWOperation.hh:52
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
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
BoostGraph< BasicBlockNode, ControlFlowEdge >::Edge
ControlFlowEdge Edge
The (base) edge type managed by this graph.
Definition: BoostGraph.hh:92
LiveRangeData::inlineAsmClobbers_
std::set< TCEString > inlineAsmClobbers_
Definition: LiveRangeData.hh:128
LiveRangeData::merge
void merge(LiveRangeData &succ)
Definition: LiveRangeData.cc:47
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
CFGStatistics::maxInstructionCount
virtual int maxInstructionCount() const
Definition: CFGStatistics.cc:74
TTAProgram::CodeSnippet::remove
virtual void remove(Instruction &ins)
Definition: CodeSnippet.cc:558
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
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
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
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
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
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
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
TTAProgram::NullAddress::instance
static NullAddress & instance()
Definition: NullAddress.cc:65
ProgramOperationPtr
std::shared_ptr< ProgramOperation > ProgramOperationPtr
Definition: MoveNode.hh:52
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
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
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
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
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
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
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
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
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
TTAProgram::CodeSnippet::add
virtual void add(Instruction *ins)
Definition: CodeSnippet.cc:432
BoostGraph< BasicBlockNode, ControlFlowEdge >::connectingEdge
EdgeDescriptor connectingEdge(const Node &nTail, const Node &nHead) const
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
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
TTAProgram::Move::guard
MoveGuard & guard() const
Definition: Move.cc:345
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
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
TTAProgram::Terminal::value
virtual SimValue value() const
Definition: Terminal.cc:178
TTAProgram::Terminal::immediateUnit
virtual const TTAMachine::ImmediateUnit & immediateUnit() const
Definition: Terminal.cc:240
TTAProgram::Procedure::clear
void clear()
Definition: Procedure.cc:345
TTAProgram::Address::location
InstructionAddress location() const
TTAProgram::Move
Definition: Move.hh:55
TTAMachine::ControlUnit::delaySlots
int delaySlots() const
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
BoostGraph< BasicBlockNode, ControlFlowEdge >::inDegree
virtual int inDegree(const Node &node) const
CFGStatistics::setMaxImmediateCount
virtual void setMaxImmediateCount(int)
Definition: CFGStatistics.cc:109
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
ControlFlowGraph::passData_
InterPassData * passData_
Definition: ControlFlowGraph.hh:339
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::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
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
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
TTAProgram::Terminal::toString
virtual TCEString toString() const =0
AssocTools::append
static void append(const ContainerType &src, ContainerType &dest)
TTAMachine::Component::machine
virtual Machine * machine() const
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
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
TTAMachine::HWOperation::parentUnit
FunctionUnit * parentUnit() const
Definition: HWOperation.cc:190
TTAProgram::Instruction::immediateCount
int immediateCount() const
Definition: Instruction.cc:267
ControlFlowGraph::statistics
const CFGStatistics & statistics()
Definition: ControlFlowGraph.cc:1308
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)
ControlFlowEdge::CFLOW_EDGE_FALSE
@ CFLOW_EDGE_FALSE
Definition: ControlFlowEdge.hh:55
ControlFlowGraph::entryNode
BasicBlockNode & entryNode() const
Definition: ControlFlowGraph.cc:1003
TTAProgram::Terminal::basicBlock
virtual const BasicBlock & basicBlock() const
Definition: Terminal.cc:261
TTAProgram::Procedure::name
TCEString name() const
Definition: Procedure.hh:66
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< BasicBlockNode, ControlFlowEdge >
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
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::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::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
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
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
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
ControlFlowGraph::JUMP_NOT_REMOVED
@ JUMP_NOT_REMOVED
Definition: ControlFlowGraph.hh:297
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
TTAProgram::Instruction::moveCount
int moveCount() const
Definition: Instruction.cc:176
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
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
TTAMachine::ImmediateUnit
Definition: ImmediateUnit.hh:50
Generated by   doxygen 1.8.17