#include <ControlFlowGraph.hh>

Inheritance diagram for ControlFlowGraph:

Collaboration diagram for ControlFlowGraph:

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

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< GraphNode, GraphEdge >
	GraphBase ()

virtual	~GraphBase ()

virtual int	outDegree (const Node &node) const =0

virtual int	inDegree (const Node &node) const =0

virtual Edge &	outEdge (const Node &node, const int index) const =0

virtual Edge &	inEdge (const Node &node, const int index) const =0

virtual EdgeSet	outEdges (const Node &node) const =0

virtual EdgeSet	inEdges (const Node &node) const =0

virtual Node &	tailNode (const Edge &edge) const =0

virtual Node &	headNode (const Edge &edge) const =0

virtual bool	hasEdge (const Node &nTail, const Node &nHead) const =0

virtual EdgeSet	connectingEdges (const Node &nTail, const Node &nHead) const =0

virtual TCEString	dotString () const

virtual void	writeToDotFile (const TCEString &fileName) const

virtual void	addNode (Node &node)=0

virtual void	removeNode (Node &node)=0

virtual void	removeEdge (Edge &e)=0

virtual void	connectNodes (const Node &nTail, const Node &nHead, Edge &e)=0

virtual void	disconnectNodes (const Node &nTail, const Node &nHead)=0

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.

std::map< ProgramOperation , llvm::MachineInstr >	programOperationToMIMap_
	For LLVM conversion: mapping of created MachineInstructions to TCE ProgramOperations.

Friends
class	ControlDependenceGraph

class	ProgramDependenceGraph

Additional Inherited Members
Public Types inherited from BoostGraph< BasicBlockNode, ControlFlowEdge >
typedef std::set< BasicBlockNode *, typename GraphNode::Comparator >	NodeSet

typedef std::set< ControlFlowEdge *, typename GraphEdge::Comparator >	EdgeSet

typedef BasicBlockNode	Node
	The (base) node type managed by this graph.

typedef ControlFlowEdge	Edge
	The (base) edge type managed by this graph.

Public Types inherited from GraphBase< GraphNode, GraphEdge >
typedef std::set< GraphNode *, typename GraphNode::Comparator >	NodeSet

typedef std::set< GraphEdge *, typename GraphEdge::Comparator >	EdgeSet

typedef GraphNode	Node
	Node type of this graph (possibly, a base class).

typedef GraphEdge	Edge
	Edge type of this graph (possibly, a base class).

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.

typedef boost::graph_traits< Graph >	GraphTraits
	Traits characterising the internal graph type.

typedef GraphTraits::out_edge_iterator	OutEdgeIter
	Output edge iterator type.

typedef GraphTraits::in_edge_iterator	InEdgeIter
	Input edge iterator type.

typedef GraphTraits::edge_iterator	EdgeIter
	Iterator type for the list of all edges in the graph.

typedef GraphTraits::vertex_iterator	NodeIter
	Iterator type for the list of all nodes in the graph.

typedef GraphTraits::edge_descriptor	EdgeDescriptor
	Type with which edges of the graph are seen internally.

typedef GraphTraits::vertex_descriptor	NodeDescriptor
	Type with which nodes of the graph are seen internally.

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 Member Functions inherited from GraphBase< GraphNode, GraphEdge >
virtual bool	hasNode (const Node &) const =0

Protected Attributes inherited from BoostGraph< BasicBlockNode, ControlFlowEdge >
std::unordered_map< const BasicBlockNode *, int >	sourceDistances_

std::unordered_map< const BasicBlockNode *, int >	sinkDistances_

std::unordered_map< const BasicBlockNode *, int >	loopingSourceDistances_

std::unordered_map< const BasicBlockNode *, int >	loopingSinkDistances_

int	height_

Graph	graph_
	The internal graph structure.

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.

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

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.

                                :
    BoostGraph<BasicBlockNode, ControlFlowEdge>(name),
    program_(program),
    startAddress_(TTAProgram::NullAddress::instance()),
    endAddress_(TTAProgram::NullAddress::instance()),
    passData_(NULL) {
    procedureName_ = name;
}

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.

                             :
    BoostGraph<BasicBlockNode, ControlFlowEdge>(procedure.name()),
    program_(NULL),
    procedure_(&procedure),
    startAddress_(TTAProgram::NullAddress::instance()),
    endAddress_(TTAProgram::NullAddress::instance()),
    passData_(&passData) {
    buildFrom(procedure);
}

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.

                                          :
    BoostGraph<BasicBlockNode, ControlFlowEdge>(procedure.name()),
    program_(NULL),
    procedure_(&procedure),
    startAddress_(TTAProgram::NullAddress::instance()),
    endAddress_(TTAProgram::NullAddress::instance()),
    passData_(NULL) {
    buildFrom(procedure);
}

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.

                                    {
    while (nodeCount() > 0) {
        BasicBlockNode* b = &node(0);
        removeNode(*b);
        delete b;
    }
}

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.

                                   {
    // edge from Entry to first "real" node of CFG needs to be true
    // artificial edge to Exit node needs to be false
    BasicBlockNode& entry = entryNode();
    std::vector<std::pair<BasicBlockNode*, int> > fromEntry;
    for (int i = 0; i < outDegree(entry); i++) {
        fromEntry.push_back(
            std::pair<BasicBlockNode*, int>(
                &headNode(outEdge(entry,i)), outEdge(entry,i).edgeID()));
    }
    for (unsigned int i = 0; i < fromEntry.size(); i++) {
        disconnectNodes(entry, *(fromEntry[i].first));
        ControlFlowEdge* edge = new ControlFlowEdge(
            ControlFlowEdge::CFLOW_EDGE_TRUE);
        connectNodes(entry, *(fromEntry[i].first), *edge);
    }
    ControlFlowEdge* edge = new ControlFlowEdge(
        ControlFlowEdge::CFLOW_EDGE_FALSE);
    connectNodes(entryNode(), exitNode(), *edge);
}

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.

                          {
    BasicBlockNode* exit = new BasicBlockNode(0, 0, false, true);
    addNode(*exit);
 
    // the actual code which inserts the exit on normal case.
    for (ReturnSourceSet::iterator i = returnSources_.begin();
         i != returnSources_.end(); i++) {
 
        InstructionAddress sourceAddr = i->first;
        if (!MapTools::containsKey(blocks_, sourceAddr)) {
            if (Application::verboseLevel() >= 1) {
                TCEString msg = (
                    boost::format(
                        "Source instr %d:%s\nDestination instr %d:%s\n")
                    % Conversion::toString(sourceAddr)
                    ).str();
                Application::logStream() << msg;
            }
            throw InvalidData(
                __FILE__, __LINE__, __func__,
                "Source basic block of edge to exit is missing!");
        }
        BasicBlockNode& blockSource(*blocks_[sourceAddr]);
        ControlFlowEdge* theEdge = 
            new ControlFlowEdge(i->second, ControlFlowEdge::CFLOW_EDGE_JUMP);
        connectNodes(blockSource, *exit, *theEdge);
    } 
 
    addExitFromSinkNodes(exit);
}

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 ( ControlFlowGraph::NodeSet & retSourceNodes )

Definition at line 953 of file ControlFlowGraph.cc.

                                                                      {
    BasicBlockNode* exitNode = new BasicBlockNode(0, 0, false, true);
    addNode(*exitNode);
 
    for (auto blockSource: retSourceNodes) {
        ControlFlowEdge* theEdge = new ControlFlowEdge;
        connectNodes(*blockSource, *exitNode, *theEdge);
    }
 
    addExitFromSinkNodes(exitNode);
}

References addExitFromSinkNodes(), BoostGraph< BasicBlockNode, ControlFlowEdge >::addNode(), BoostGraph< BasicBlockNode, ControlFlowEdge >::connectNodes(), and exitNode().

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

Here is the call graph for this function:

◆ addExitFromSinkNodes()

void ControlFlowGraph::addExitFromSinkNodes ( BasicBlockNode * exitNode )

Definition at line 966 of file ControlFlowGraph.cc.

                                                               {
    
    // kludge needed for start and exit methods which do nto have ret inst.
    for (int i = 0; i < nodeCount(); i++) {
        BasicBlockNode& block(node(i));
        if (outDegree(block) == 0 && exitNode != &block) {
            ControlFlowEdge* edge = new ControlFlowEdge(
                ControlFlowEdge::CFLOW_EDGE_NORMAL,
                ControlFlowEdge::CFLOW_EDGE_CALL);
            connectNodes(block, *exitNode, *edge);
        }
    }
}

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(), and 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.

                                  {
    return alignment_;
}

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.

                                                                {
    const BasicBlockNode* ftBBN = src.successor();
    while (ftBBN != nullptr && ftBBN->isNormalBB()) {
        if (ftBBN == &dst) {
            return true;
        }
        if (ftBBN->isScheduled()) {
            ftBBN = ftBBN->successor();
        } else {
            return false;
        }
    }
    return false;
}

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.

                                                                {
    procedure_ = &procedure;
    procedureName_ = procedure.name();
    if (procedure.isInProgram()) {
        program_ = &procedure.parent();
    }
    startAddress_ = procedure.startAddress();
    endAddress_ = procedure.endAddress();
    alignment_ = procedure.alignment();
 
    // Set of instructions that start a new basic block
    InstructionAddressMap leaders;
    InstructionAddressMap dataCodeRellocations;
 
    computeLeadersFromRefManager(leaders, 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.
    if (computeLeadersFromJumpSuccessors(leaders, procedure)) {
        computeLeadersFromRelocations(
            leaders, dataCodeRellocations, procedure);
    }
 
    createAllBlocks(leaders, procedure);
 
    // Creates edges between basic blocks
    createBBEdges(procedure, leaders, dataCodeRellocations);
    detectBackEdges();
    addExit();
}

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(), and 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.

                                          {
 
#ifdef DEBUG_POM_TO_MI
    Application::logStream()
        << "TTA instructions:" << std::endl 
        << bb.toString() << std::endl << std::endl
        << "OTA instructions:" << std::endl;
#endif
 
    /* Find the target machine from an instruction link. Ugly,
       should probably pass it as a parameter instead. */
    const TTAMachine::Machine* mach = NULL;
    for (int i = bb.skippedFirstInstructions(); i < bb.instructionCount(); 
         ++i) {
        const TTAProgram::Instruction& instr = 
            bb.instructionAtIndex(i);
        if (!instr.isNOP()) {
            mach = instr.move(0).bus().machine();
            break;
        }
    }
    if (mach == NULL)
        return; // The BB has only NOPs. Empty MBB is correct already.
 
    // the order of function unit operations in the instruction bundle
    typedef std::vector<const TTAMachine::FunctionUnit*> BundleOrderIndex;
    BundleOrderIndex bundleOrder;
 
    // Currently the bundle order is hard coded to the order of appearance
    // in the ADF file.
    for (int fuc = 0; fuc < mach->functionUnitNavigator().count(); ++fuc) {
        TTAMachine::FunctionUnit* fu = mach->functionUnitNavigator().item(fuc);
        bundleOrder.push_back(fu);
    }
 
    for (int i =  bb.skippedFirstInstructions(); i < bb.instructionCount(); 
         ++i) {
        const TTAProgram::Instruction& instr = 
            bb.instructionAtIndex(i);
        // First collect all started operations at this cycle
        // on each FU. 
        typedef std::map<const TTAMachine::FunctionUnit*, 
                         const TTAMachine::HWOperation*> OpsMap;
        OpsMap startedOps;
        typedef std::map<const TTAMachine::FunctionUnit*, 
                         ProgramOperationPtr> POMap;
        POMap startedPOs;
        for (int m = 0; m < instr.moveCount(); ++m) {
            const TTAProgram::Move& move = instr.move(m);
            if (move.isTriggering()) {
                TTAProgram::TerminalFUPort& tfup =
                    dynamic_cast<TTAProgram::TerminalFUPort&>(
                        move.destination());
                startedOps[&move.destination().functionUnit()] =
                    tfup.hwOperation();
                startedPOs[&move.destination().functionUnit()] =
                    tfup.programOperation();
            }
        }
 
        // in OTAs with data hazard detection, we do not need to emit
        // completely empty instruction bundles at all
        if (startedOps.size() == 0)
            continue; 
        
        typedef std::map<const TTAMachine::HWOperation*,
                         std::vector<TTAProgram::Terminal*> > OperandMap;
        OperandMap operands;
        // On a second pass through the moves we now should know the operand 
        // numbers of all the moves. The result moves should be at an 
        // instruction at the operation latency.
        OperationPool operations;
 
        for (OpsMap::const_iterator opsi = startedOps.begin(); 
            opsi != startedOps.end(); ++opsi) {
            const TTAMachine::HWOperation* hwOp = (*opsi).second;
            const Operation& operation = 
                operations.operation(hwOp->name().c_str());
            // first find the outputs
            for (int out = 0; out < operation.numberOfOutputs(); ++out) {
                const TTAProgram::Instruction& resultInstr = 
                    bb.instructionAtIndex(i + hwOp->latency());
                for (int m = 0; m < resultInstr.moveCount(); ++m) {
                    const TTAProgram::Move& move = resultInstr.move(m);
                    // assume it's a register write, the potential (implicit) 
                    // bypass move is ignored
                    if (move.source().isFUPort() && 
                        &move.source().functionUnit() ==
                        hwOp->parentUnit() &&
                        (move.destination().isGPR() ||
                         move.destination().isRA())) {
                        operands[hwOp].push_back(&move.destination());
                    }
                }
            }
            if ((std::size_t)operation.numberOfOutputs() != 
                operands[hwOp].size()) {
                PRINT_VAR(operation.name());
                PRINT_VAR(operands[hwOp].size());
                PRINT_VAR(operation.numberOfOutputs());
                assert((std::size_t)operation.numberOfOutputs() == 
                       operands[hwOp].size());
                abort();
            }
 
            // then the inputs
            for (int input = 0; input < operation.numberOfInputs();
                 ++input) {
                for (int m = 0; m < instr.moveCount(); ++m) {
                    const TTAProgram::Move& move = instr.move(m);
                    if (move.destination().isFUPort() &&
                        &move.destination().functionUnit() ==
                        hwOp->parentUnit() &&
                        dynamic_cast<const TTAMachine::Port*>(
                            hwOp->port(input + 1)) == 
                        &move.destination().port()) {
                        // if the result is forwarded (bypass), find the
                        // result move 
                        if (move.source().isFUPort()) {
                            for (int mm = 0; mm < instr.moveCount(); ++mm) {
                                const TTAProgram::Move& move2 = 
                                    instr.move(mm);
                                if (move2.destination().isGPR() &&
                                    move2.source().isFUPort() && 
                                    &move2.source().port() ==
                                    &move.source().port()) {
                                    operands[hwOp].push_back(&move2.destination());
                                }
                            }
                        } else {
                            // otherwise assume it's not bypassed but
                            // read from the RF
                            operands[hwOp].push_back(&move.source());
                        }
                    }
                }
            }
 
            if ((std::size_t)operation.numberOfInputs() + 
                operation.numberOfOutputs() !=
                operands[hwOp].size()) {
                PRINT_VAR(operation.name());
                PRINT_VAR(operands[hwOp].size());
                PRINT_VAR(operation.numberOfInputs());
                PRINT_VAR(operation.numberOfOutputs());
                assert(
                    operation.numberOfInputs() + operation.numberOfOutputs() ==
                    (int)operands[hwOp].size());
            }
        }
 
        for (BundleOrderIndex::const_iterator boi = bundleOrder.begin();
             boi != bundleOrder.end(); ++boi) {
            llvm::MachineInstr* mi = NULL;
            const llvm::TargetInstrInfo& tii =
                *mbb.getParent()->getTarget().getSubtargetImpl(
                    mbb.getParent()->getFunction())->getInstrInfo();
            if (startedOps.find(*boi) == startedOps.end()) {
#if 0
                // TODO: figure out a generic way to find the NOP opcode for 
                // the current "lane", it's SPU::ENOP and SPU::LNOP for SPU.                
                // Could call the TargetInstrInfo::insertNoop() if it was 
                // implemented for SPU.
                // Just omit NOP instructions for now and assume the NOP inserter
                // pass takes care of it.
                mi = mbb.getParent()->CreateMachineInstr(
                    findLLVMTargetInstrDesc("nop", tii),
                    llvm::DebugLoc());
#endif
 
#ifdef DEBUG_POM_TO_MI
                Application::logStream() << "nop";
#endif
            } else {
                const TTAMachine::HWOperation* hwop = 
                    (*startedOps.find(*boi)).second;
                assert(hwop->name() != "");
#ifdef DEBUG_POM_TO_MI
                Application::logStream() << "hwop: '" << hwop->name() << "' " << std::endl;
#endif
 
                const llvm::MCInstrDesc& tid =
                    findLLVMTargetInstrDesc(hwop->name(), tii);
                mi = mbb.getParent()->CreateMachineInstr(
                    tid, llvm::DebugLoc());
 
#ifdef DEBUG_POM_TO_MI
                Application::logStream() << "MI: "; 
                //mi->dump();
#endif
 
                
                std::vector<TTAProgram::Terminal*>& opr = operands[hwop];
 
                unsigned counter = 0;
                // add the MachineOperands to the instruction via
                // POM Terminal --> MachineOperand conversion
                for (std::vector<TTAProgram::Terminal*>::const_iterator opri =
                         opr.begin(); opri != opr.end() && 
                         (counter < tid.getNumOperands() || mi->getDesc().isReturn()); 
                     ++opri, ++counter) {
                    TTAProgram::Terminal* terminal = *opri;
                    if (terminal->isCodeSymbolReference()) {
                        // has to be a global variable at this point?
                        // Constant pool indeces are converted to
                        // dummy references when LLVM->POM conversion
                        // in the form of ".CP_INDEX_OFFSET"
                        if (terminal->toString().startsWith(".CP_")) {
                            std::vector<TCEString> refs = 
                                terminal->toString().split("_");
                            unsigned index = Conversion::toInt(refs.at(1));
                            unsigned offset = Conversion::toInt(refs.at(2));
                            mi->addOperand(
                                llvm::MachineOperand::CreateCPI(index, offset));     
                        } else if (terminal->toString().startsWith(".JTI_")) {
                            TCEString ref = terminal->toString().substr(5);
                            unsigned index = Conversion::toInt(ref);
                            mi->addOperand(    
                                llvm::MachineOperand::CreateJTI(index, 0));     
                        } else {       
                            mi->addOperand(
                                llvm::MachineOperand::CreateES(
                                    terminal->toString().c_str()));
                        }
                    } else if (terminal->isBasicBlockReference()) {
                        llvm::MachineBasicBlock& mbb2 =
                            getMBB(*mbb.getParent(), terminal->basicBlock());                          
                        mi->addOperand(
                            llvm::MachineOperand::CreateMBB(&mbb2)); 
                        mbb.addSuccessor(&mbb2);
                    } else if (terminal->isProgramOperationReference()) {
                        const TTAProgram::TerminalProgramOperation& tpo =
                            dynamic_cast<
                            const TTAProgram::TerminalProgramOperation&>(
                                *terminal);
                        llvm::MCSymbol* symbol = 
                            mbb.getParent()->getContext().getOrCreateSymbol(
                                llvm::StringRef(tpo.label()));
                        mi->addOperand(llvm::MachineOperand::CreateMCSymbol(symbol));
                        // need to keep book of the TPOs in order to recreate the
                        // label instructions
                        tpos_.insert(std::make_pair(tpo.programOperation(), symbol));
                    } else if (terminal->isImmediate()) {
                        if (!mi->getDesc().isReturn()) {
                            mi->addOperand(
                                 llvm::MachineOperand::CreateImm(
                                 terminal->value().intValue()));
                        } 
                    } else if (terminal->isGPR()) {
                        // in case it's an output, it's a def, the outputs are always the
                        // first operands in the LLVM instruction
                        bool isDef = counter < tid.getNumDefs();
                        bool isImp = false;
                        // RET on spu seems to have implicit operand
                        // TODO: implement real implicit property to OSAL
                        // operands.
                        if (mi->getDesc().isReturn()) {
                            isImp = true;
                        }
 
                        // LLVM register index starts from 1, 
                        // we count register from 0
                        // thus add 1 to get correct data to the LLVM
                        if (!mi->getDesc().isReturn()) {
                            mi->addOperand(
                                llvm::MachineOperand::CreateReg(
                                    terminal->index() + 1, isDef, isImp));                            
                        }
 
                    } else {
                        abortWithError(
                            "Unsupported Terminal -> MachineOperand conversion attempted.");
                    }
#ifdef DEBUG_POM_TO_MI
                    if (counter > 0)
                        Application::logStream() << ", ";
                    Application::logStream() << terminal->toString();
#endif
                }
            }
            if (mi != NULL) {
                mbb.push_back(mi);
                assert(startedPOs.find(*boi) != startedPOs.end());
                ProgramOperationPtr po = (*startedPOs.find(*boi)).second;
                assert(po.get() != NULL);
                if (po.get() != NULL) {
                    programOperationToMIMap_[po.get()] = mi;
                } else {                    
                    //assert(po.get() != NULL);
                }
            }
#ifdef DEBUG_POM_TO_MI
            Application::logStream() << "\t# " << (*boi)->name() << std::endl;
#endif
        }
#ifdef DEBUG_POM_TO_MI
        Application::logStream() << std::endl;
#endif
    }
 
#ifdef DEBUG_POM_TO_MI
    Application::logStream() << std::endl << std::endl;
#endif
}

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

leaders	Set of leader instructions to update.
procedure	The procedure to analyse.

Returns: true indicates there is indirect jump in procedure

Definition at line 444 of file ControlFlowGraph.cc.

                                {
    
    bool indirectJump = false;
    // record target instructions of jumps, because they are
    // leaders of basic block too
    InstructionAddressMap targets;
    // The procedure start point is always a block leader.
 
    const unsigned int iCount = procedure.instructionCount();
    for (unsigned int insIndex = 0;insIndex < iCount;) {
        Instruction* instruction = &procedure.instructionAtIndex(insIndex);
        // Only one control flow operation per cycle
        bool increase = true;
        for (int i = 0; i < instruction->moveCount(); i++) {
            Move& m(instruction->move(i));
            if (m.isControlFlowMove()) {
                // if it is direct jump we store target address
                if (m.source().isInstructionAddress() && m.isJump()) {
                    Instruction& iTarget =
                        m.source().instructionReference().instruction();
                    InstructionAddress targetAddr =
                        iTarget.address().location();
                    // If an instruction that is target of a jump has not
                    // been yet identified as a leader, do it here.
                    leaders[targetAddr] = &iTarget;
                }
                if (m.isJump() && 
                     (m.source().isGPR() || 
                      m.source().isImmediateRegister())) {
                    indirectJump = true;
                }
                increase = false;
                unsigned int nextIndex = findNextIndex(procedure, insIndex, i);
                if (iCount > nextIndex) {
                    insIndex = nextIndex;
                    instruction = &procedure.instructionAtIndex(insIndex);
                    leaders[instruction->address().location()] = instruction;
                } else {
                    return indirectJump; // end of procedure.
                }
                break;
            }
        }
        if (increase) {
            insIndex++;
        }
    }
    return indirectJump;
}

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

leaders	Set of leader instructions to update.
procedure	The procedure to analyse, uses it's parent() program to find referenceManager.

Definition at line 351 of file ControlFlowGraph.cc.

                                {
 
    if (!procedure.isInProgram()) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "For access to reference manager procedure \
            must be registered in Program!");
    }
    InstructionReferenceManager& refManager =
        procedure.parent().instructionReferenceManager();
    // Add first instruction of procedure by default,
    // testing starts from second
    leaders[startAddress_.location()] = &procedure.firstInstruction();
 
    // this can get slow if there are zillion instructionreferences?
    for (InstructionReferenceManager::Iterator i = refManager.begin();
         i != refManager.end(); ++i) {
        Instruction& instruction = i->instruction();
        InstructionAddress insAddr = instruction.address().location();
        if (insAddr > startAddress_.location() &&
            insAddr < endAddress_.location()) {
            assert(&instruction.parent() == &procedure);
            leaders[insAddr] = &instruction;
        }
    }
}

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

leaders	Set of leader instructions to update.
dataCodeRellocations	Set of dataCodeRellocations that applies for given procedure
procedure	The procedure to analyse, uses it's parent() program to access data memory

Definition at line 397 of file ControlFlowGraph.cc.

                                {
 
    if (!procedure.isInProgram()) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "For access to Relocations procedure \
            must be registered in Program!");
    }
    Program& program = procedure.parent();
    for (int j = 0; j < program.dataMemoryCount(); j++) {
        const DataMemory& d(program.dataMemory(j));
        for (int i = 0, count = d.dataDefinitionCount();
            i < count;
            i++) {
            const DataDefinition& dataDef(d.dataDefinition(i));
            if (!dataDef.isInstructionAddress()) {
                continue;
            }
            const Address& targetAddress(
                dataDef.destinationAddress());
            if (targetAddress.location() >= startAddress_.location() &&
                targetAddress.location() < endAddress_.location()) {
                Instruction& iTarget(
                    procedure.instructionAt(targetAddress.location())) ;
                leaders[targetAddress.location()] = &iTarget;
                dataCodeRellocations[targetAddress.location()] = &iTarget;
            }
        }
    }
}

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.

                                               {
 
    for (int i = 0; i < nodeCount(); i++) {
        BasicBlockNode& bbn = node(i);
 
        if (bbn.isNormalBB()) {
            TTAProgram::BasicBlock& bb = bbn.basicBlock();
 
            for (int j = 0; j < bb.instructionCount(); j++) {
                TTAProgram::Instruction& ins = bb.instructionAtIndex(j);
 
                for (int k = 0; k < ins.moveCount(); k++) {
                    TTAProgram::Move& move = ins.move(k);
                    TTAProgram::Terminal& src = move.source();
 
                    if (src.isBasicBlockReference()) {
                        const TTAProgram::BasicBlock& target = 
                            src.basicBlock();
                        assert(target.instructionCount() > 0);
                        move.setSource(
                            new TTAProgram::TerminalInstructionReference(
                                instructionReferenceManager().createReference(
                                    target.firstInstruction())));
                    }
                }
 
                for (int k = 0; k < ins.immediateCount(); k++) {
                    TTAProgram::Immediate& imm = ins.immediate(k);
                    TTAProgram::Terminal& immVal = imm.value();
 
                    if (immVal.isBasicBlockReference()) {
                        const TTAProgram::BasicBlock& target = 
                            immVal.basicBlock();
                        assert(target.instructionCount() > 0);
                        imm.setValue(
                            new TTAProgram::TerminalInstructionReference(
                                instructionReferenceManager().createReference(
                                    target.firstInstruction())));
                    }
                }
            }
        }
    }
}

References assert, BasicBlockNode::basicBlock(), TTAProgram::Terminal::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

mf	The MachineFunction where to copy the cfg.
irm	InstructionReferenceManager 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.

                                                {
 
    // todo: make sure not indeterministic.
    // two-way maps between copied and in cfg instructions.
    typedef std::map<TTAProgram::Instruction*,TTAProgram::Instruction*>
        InsMap;
    InsMap copiedInsFromCFG;
 
    std::vector<Instruction*> oldInstructions;
 
    ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
    assert(firstBBs.size() == 1);
    BasicBlockNode* firstBBN = *firstBBs.begin();
    BasicBlockNode* currentBBN = firstBBN;
 
    // fix refs to old first to point to first in cfg - later fixed to
    // first in program
    if (irm == NULL) {
        irm = &program_->instructionReferenceManager();
        assert(irm != NULL);
    }
    assert(firstBBN->isNormalBB());
 
#if 0
    // procedure should not have any references.
    for (int i = 0; i < proc.instructionCount(); i++) {
        assert(!irm->hasReference(proc.instructionAtIndex(i)));
    }
#endif
        
    while (!mf.empty())
        mf.erase(mf.begin());
 
    // find and queue reachable nodes
    NodeSet queuedNodes = findReachableNodes();
    NodeSet unreachableNodes;
 
    // find dead nodes
    for (int i = 0; i < nodeCount(); i++) {
        BasicBlockNode& n = node(i);
        if (!AssocTools::containsKey(queuedNodes,&n) &&
            n.isNormalBB()) {
            unreachableNodes.insert(&n);
        }
    }
 
    /// 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.
    while (currentBBN != NULL) {
        BasicBlockNode* nextNode = NULL;
        TTAProgram::BasicBlock& bb = currentBBN->basicBlock();
 
        /// This will create MachineBasicblock corresponding to BB if it does
        /// not exists already.
        getMBB(mf, bb);
 
        queuedNodes.erase(currentBBN);
 
        // then start searching for the next node.
 
        // if has fall-thru-successor, select it so no need to add
        // extra jump
        BasicBlockNode* ftNode = fallThruSuccessor(*currentBBN);
        if (ftNode != NULL && ftNode->isNormalBB()) {
 
            if (queuedNodes.find(ftNode) == queuedNodes.end()) {
                std::cerr << "not-queued fall-thru: " << ftNode->toString()
                          << " current: " << currentBBN->toString() << 
                    std::endl;
                writeToDotFile("copyToProcedureFallThruBBNotQueued.dot");
            }
            // must not be already processed.
            assert(queuedNodes.find(ftNode) != queuedNodes.end());
            currentBBN = ftNode;
            continue;
        }
 
        // Select some node, preferably successors without ft-preds
        // The jump can then be removed.
        EdgeSet oEdges = outEdges(*currentBBN);
 
        // need to select SOME node as successor.
        // first without ft-predecessor usually is a good candidate.
        // smarter heuristic does not seem to help at all.
        // try to select
        if (nextNode == NULL) {
            bool ftPred = false;
            for (NodeSet::iterator i = queuedNodes.begin();
                 i != queuedNodes.end(); i++) {
                if (!hasFallThruPredecessor(**i)) {
                    nextNode = *i;
                    break;
                } else {
                    ftPred = true;
                }
            }
            
            // unreachable node having ft may have prevented us from
            // managing some node whose fall-thru succs prevent
            // futher nodes. try to select some unreached node.
            if (nextNode == NULL && ftPred) {
                for (NodeSet::iterator i = unreachableNodes.begin();
                     i != unreachableNodes.end(); i++) {
                    if (fallThruSuccessor(**i) != NULL) {
                        nextNode = *i;
                        unreachableNodes.erase(*i);
                        break;
                    }
                }
            }
 
            // did not help. we cannot select node which has
            // fall-thru predecessor.
            if (nextNode == NULL && ftPred) {
                writeToDotFile(
                    "CopyToProcedure_multiple_fall_thorough_nodes.dot");
                assert(0 && "CFG may have multiple fall-thorough nodes!");
            }
        }
        currentBBN = nextNode;
    }
 
    // now all instructions are copied.
 
    // this can happen in indeterministic order.
    // but it should not cause any indeterministicity
    // effects on the schedule.
 
    // Update refs from cfg into final program
    // only works for refs
    // TODO: Is this really necessary or usefull here?
    for (InsMap::iterator i = copiedInsFromCFG.begin();
         i != copiedInsFromCFG.end(); i++) {
        std::pair<Instruction*,Instruction*> insPair = *i;
        if (irm->hasReference(*insPair.first)) {
            irm->replace(*insPair.first, *insPair.second);
        }
    }
 
    /// Fill in created machine basic blocks with machine instructions
    /// based on corresponding basic blocks.
    unsigned int nCount = nodeCount();
    for (unsigned int j = 0; j < nCount; j++) {
        TTAProgram::BasicBlock& bb = node(j).basicBlock();
        llvm::MachineBasicBlock* mbb = &getMBB(mf, bb);
        buildMBBFromBB(*mbb, bb);  
    }
 
    /// 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.
    for (std::set<std::pair<ProgramOperationPtr, llvm::MCSymbol*> >::const_iterator i = 
             tpos_.begin(); i != tpos_.end(); ++i) {
        ProgramOperationPtr po = (*i).first;
        llvm::MCSymbol* symbol = (*i).second;
        assert(programOperationToMIMap_.find(po.get()) != programOperationToMIMap_.end());
        llvm::MachineInstr* mi = programOperationToMIMap_[po.get()];
        assert(mi != NULL);
        const llvm::TargetInstrInfo& tii =
            *mf.getTarget().getSubtargetImpl(mf.getFunction())->getInstrInfo();
        const llvm::MCInstrDesc& tid =
            findLLVMTargetInstrDesc("HBR_LABEL", tii);
        llvm::MachineInstr* labelInstruction = 
            mf.CreateMachineInstr(tid, llvm::DebugLoc());
        labelInstruction->addOperand(
            llvm::MachineOperand::CreateMCSymbol(symbol));
        mi->getParent()->insert(
            llvm::MachineBasicBlock::instr_iterator (mi), labelInstruction);        
    }
    tpos_.clear();
    programOperationToMIMap_.clear();
    /// Based on CFG edges, add successor information to the generated
    /// machine function.
    unsigned int eCount = edgeCount();
    for (unsigned int i = 0; i < eCount; i++) {
        ControlFlowEdge& testEdge = edge(i);
        if (!headNode(testEdge).isNormalBB() ||
            !tailNode(testEdge).isNormalBB())
            continue;
        
        llvm::MachineBasicBlock& hNode =
            getMBB(mf, headNode(testEdge).basicBlock());
        llvm::MachineBasicBlock& tNode =
            getMBB(mf, tailNode(testEdge).basicBlock());
        if (hNode.isSuccessor(&tNode))
            continue;
        tNode.addSuccessor(&hNode);
    }
 
}

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

proc	procedure where the copy the cfg.

Definition at line 1448 of file ControlFlowGraph.cc.

                                                                 {
 
    // todo: make sure not indeterministic.
    // two-way maps between copied and in cfg instructions.
    typedef std::map<TTAProgram::Instruction*,TTAProgram::Instruction*>
        InsMap;
    InsMap copiedInsFromCFG;
 
    std::vector<Instruction*> oldInstructions;
 
    int jumpsRemoved = 0;
    ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
    assert(firstBBs.size() == 1);
    BasicBlockNode* firstBBN = *firstBBs.begin();
    BasicBlockNode* currentBBN = firstBBN;
 
    // fix refs to old first to point to first in cfg - later fixed to
    // first in program
    if (irm == NULL) {
        irm = &program_->instructionReferenceManager();
        assert(irm != NULL);
    }
    if (!firstBBN->isNormalBB()) {
        std::cerr << "First Basic block is not normal basic block. "
                  << "This is propably due function that is completely empty,"
                  <<  " not containg even return jump. The cause of this "
                  << "might be LLVM optimizing away code it considers dead."
                  << std::endl
                  << "Control flow graph written to empty_fn.dot" 
                  << std::endl;
        writeToDotFile("empty_fn.dot");
    }        
    assert(firstBBN->isNormalBB());
 
    // procedure should not have any references.
    for (int i = 0; i < proc.instructionCount(); i++) {
        assert(!irm->hasReference(proc.instructionAtIndex(i)));
    }
 
    proc.clear();
 
    // find and queue reachable nodes
    NodeSet queuedNodes = findReachableNodes();
    NodeSet unreachableNodes = findUnreachableNodes(queuedNodes);
 
    // then loop as long as we have BBs which have not been written to
    // the procedure.
    while (currentBBN != NULL) {
        BasicBlockNode* nextNode = NULL;
        TTAProgram::BasicBlock& bb = currentBBN->basicBlock();
        // todo: if refs to skipped instructions, breaks?
 
        for (int i = 0; i < bb.skippedFirstInstructions(); i++) {
            Instruction& ins = bb.instructionAtIndex(i);
            if (irm->hasReference(ins)) {
                std::cerr << "\tSkipped inst has refs, proc: " << proc.name()
                          << " index: " << i << std::endl;
                writeToDotFile("skipped_has_ref.dot");
                PRINT_VAR(bb.toString());
            }
            assert(!irm->hasReference(ins));
        }
 
        // copy instructions of a BB to procedure.
        for (int i = bb.skippedFirstInstructions();
             i < bb.instructionCount(); i++) {
            Instruction* ins = &bb.instructionAtIndex(i);
            Instruction* copiedIns = ins->copy();
            copiedInsFromCFG[ins] = copiedIns;
 
            // CodeSnippet:: is a speed optimization here.
            // only later fix the addresses of followind functions.
            proc.CodeSnippet::add(copiedIns);
        }
 
        queuedNodes.erase(currentBBN);
 
        // then start searching for the next node.
 
        // if has fall-turu-successor, select it so no need to add
        // extra jump
        BasicBlockNode* ftNode = fallThruSuccessor(*currentBBN);
        if (ftNode != NULL && ftNode->isNormalBB()) {
 
            if (queuedNodes.find(ftNode) == queuedNodes.end()) {
                std::cerr << "not-queued fall-thru: " << ftNode->toString()
                          << " current: " << currentBBN->toString() << 
                    std::endl;
                writeToDotFile("copyToProcedureFallThruBBNotQueued.dot");
            }
            // must not be already processed.
            assert(queuedNodes.find(ftNode) != queuedNodes.end());
            currentBBN = ftNode;
            continue;
        }
 
        // Select some node, preferably successors without ft-preds
        // The jump can then be removed.
        EdgeSet oEdges = outEdges(*currentBBN);
        for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
            ControlFlowEdge& e = **i;
            BasicBlockNode& head = headNode(e);
            if (!hasFallThruPredecessor(head) && head.isNormalBB() &&
                queuedNodes.find(&head) != queuedNodes.end()) {
                // try to remove the jump as it's jump to the next BB.
                RemovedJumpData rjd = removeJumpToTarget(
                    proc, head.basicBlock().firstInstruction(),
                    proc.instructionCount() - 
                    (bb.instructionCount() - bb.skippedFirstInstructions()));
                if (rjd != JUMP_NOT_REMOVED) {
                    jumpsRemoved++;
                    // if BB got empty,
                    // move refs to beginning of the next BB.
                    if (rjd == LAST_ELEMENT_REMOVED) {
                        Instruction& ins = bb.instructionAtIndex(0);
                        if (irm->hasReference(ins)) {
                            irm->replace(
                                ins, head.basicBlock().instructionAtIndex(
                                    head.basicBlock().
                                    skippedFirstInstructions()));
                        }
                    }
                    // we removed a jump so convert the jump edge into
                    // fall-through edge.
                    ControlFlowEdge* ftEdge = new ControlFlowEdge(
                        e.edgePredicate(), 
                        ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
                    removeEdge(e);
                    connectNodes(*currentBBN, head, *ftEdge);
                    nextNode = &head;
                    break;
                }
            }
        }
 
        // need to select SOME node as successor.
        // first without ft-predecessor usually is a good candidate.
        // smarter heuristic does not seem to help at all.
        // try to select
        if (nextNode == NULL) {
            bool ftPred = false;
            for (NodeSet::iterator i = queuedNodes.begin();
                 i != queuedNodes.end(); i++) {
                if (!hasFallThruPredecessor(**i)) {
                    nextNode = *i;
                    break;
                } else {
                    ftPred = true;
                }
            }
            
            // unreachable node having ft may have prevented us from
            // managing some node whose fall-thru succs prevent
            // futher nodes. try to select some unreached node.
            if (nextNode == NULL && ftPred) {
                for (NodeSet::iterator i = unreachableNodes.begin();
                     i != unreachableNodes.end(); i++) {
                    if (fallThruSuccessor(**i) != NULL) {
                        nextNode = *i;
                        unreachableNodes.erase(*i);
                        break;
                    }
                }
            }
 
            // did not help. we cannot select node which has
            // fall-thru predecessor.
            if (nextNode == NULL && ftPred) {
                writeToDotFile(
                    "CopyToProcedure_multiple_fall_thorough_nodes.dot");
                assert(0 && "CFG may have multiple fall-thorough nodes!");
            }
        }
        currentBBN = nextNode;
    }
 
    // now all instructions are copied.
 
    // this can happen in indeterministic order.
    // but it should not cause any indeterministicity
    // effects on the schedule.
 
    // Update refs from cfg into final program
    // only works for refs
    for (InsMap::iterator i = copiedInsFromCFG.begin();
         i != copiedInsFromCFG.end(); i++) {
        std::pair<Instruction*,Instruction*> insPair = *i;
        if (irm->hasReference(*insPair.first)) {
            irm->replace(*insPair.first, *insPair.second);
        }
    }
 
    // move the following procedures to correct place
    if (proc.instructionCount() != 0 && proc.isInProgram()) {
        if (!(&proc == &proc.parent().lastProcedure())) {
            proc.parent().moveProcedure(
                proc.parent().nextProcedure(proc),
                proc.instructionCount());
        }
    }
 
    // make sure no refs to dead code?
/*
    for (NodeSet::iterator i = unreachableNodes.begin();
         i != unreachableNodes.end(); i++) {
        BasicBlockNode& bbn = **i;
        if (bbn.isNormalBB()) {
            BasicBlock& bb = bbn.basicBlock();
            for (int i = 0; i < bb.instructionCount();i++) {
                Instruction& ins = bb.instructionAtIndex(i);
                assert(!irm.hasReference(ins));
            }
        }
    }
*/
}

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< GraphNode, GraphEdge >::writeToDotFile().

Referenced by ProgramDependenceGraph::disassemble(), PreOptimizer::handleProcedure(), SimpleIfConverter::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

leaders	Set of instructions which starts basic block.
procedure	Procedure that is analysed.

Definition at line 503 of file ControlFlowGraph.cc.

                                {
 
    // leaders are not sorted so to create basic blocks we need
    // to sort beginning addresses of blocks
    std::set<InstructionAddress> iAddresses;
    iAddresses = MapTools::keys<InstructionAddress>(leaders);
    InstructionAddressVector
        sortedLeaders(iAddresses.begin(), iAddresses.end());
    sort(sortedLeaders.begin(), sortedLeaders.end());
    int blockSize = sortedLeaders.size();
    if (blockSize > 0) {
        int i;
        for (i = 0; i < blockSize - 1; i++) {
            createBlock(
                procedure.instructionAt(sortedLeaders[i]),
                procedure.instructionAt(sortedLeaders[i+1] - 1));
        }
        createBlock(
            procedure.instructionAt(sortedLeaders[i]),
            procedure.lastInstruction());
    }
}

References createBlock(), TTAProgram::CodeSnippet::instructionAt(), MapTools::keyForValue(), 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

procedure	Procedure that holds the instructions.
leaders	Leader instructions, first instructions in basic blocks.
dataCodeRellocations	Set 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.

                                                 {
 
    InstructionAddress leaderAddr;
    bool hasCFMove = false;
 
    InstructionAddress exitAddr = 0;
    bool hasExit = false;
    if (procedure.isInProgram()) {
        /// 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
 
        if (program_->hasProcedure("__exit")) {
            exitAddr =
                program_->procedure("__exit").firstInstruction().address().
                location();
            hasExit = true; 
        } else {
            /// The __exit procedure was not found, we do not detect calls to
            /// __exit in calls
            hasExit = false;
        }
    }
 
    const int iCount = procedure.instructionCount();
    for (int insIndex = 0; insIndex < iCount; insIndex++) {
        Instruction* instruction = &procedure.instructionAtIndex(insIndex);
        InstructionAddress addr = 
            procedure.startAddress().location() + insIndex;
 
        if (MapTools::containsKey(leaders, addr)) {
            leaderAddr = addr;
            hasCFMove = false;
        }
        // We only deal with one JUMP or CALL per instruction,
        // there is restriction that there can be no control flow
        // operations in delay slots of previous operation
        for (int i = 0, count = instruction->moveCount(); i < count; i++) {
            if (instruction->move(i).isCall()) {
                // There is some CF move in a basic block
                hasCFMove = true;
                int nextIndex = findNextIndex(procedure, insIndex, i);
                if (iCount > nextIndex) {
                    /// Do not create fall through edge after call to __exit
                    if (hasExit &&
                        instruction->move(i).source().isInstructionAddress()) {
                        TTAProgram::TerminalInstructionReference* address =
                        dynamic_cast<TTAProgram::TerminalInstructionReference*>
                            (&instruction->move(i).source());
                        Instruction& destination =
                            address->instructionReference().instruction();
                        if (destination.address().location() == exitAddr) {
                           break;
                        }
                    }
                    Instruction& iNext = 
                        procedure.instructionAtIndex(nextIndex);
                    createControlFlowEdge(
                        *leaders[leaderAddr], iNext,
                        ControlFlowEdge::CFLOW_EDGE_NORMAL,
                        ControlFlowEdge::CFLOW_EDGE_CALL);
 
                }
                break;
            }
            if (instruction->move(i).isJump()) {
                // There is some CF move in basic block
                hasCFMove = true;
                createJumps(
                    leaders, leaderAddr, dataCodeRellocations,
                    procedure, insIndex, i);
                continue;
            }
        }
        if (iCount > insIndex+1) {
            Instruction& nextInstruction =
                procedure.instructionAtIndex(insIndex+1);
            // Look if next instruction is beginning of basic block
            // and if there was no CF move in current basic block
            // add fall true edge in such case
            int nextInsAddr = procedure.startAddress().location() + insIndex+1;
            if (hasCFMove == false &&
                MapTools::containsKey(leaders, nextInsAddr)) {
                BasicBlockNode& blockSource(*blocks_[leaderAddr]);
                BasicBlockNode& blockTarget(
                    *blocks_[nextInsAddr]);
                if (!hasEdge(blockSource, blockTarget)) {
                    createControlFlowEdge(
                        *leaders[leaderAddr],nextInstruction,
                        ControlFlowEdge::CFLOW_EDGE_NORMAL,
                        ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
                }
            }
        } else {
            break;
        }
    }
}

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

leader	The first instruction of the basic block to create.
endBlock	The last instruction of the basic block to create.

Returns: The created basic block node.

Definition at line 540 of file ControlFlowGraph.cc.

                                 {
 
    InstructionAddress blockStart = leader.address().location();
    InstructionAddress blockEnd = endBlock.address().location();
 
    CodeSnippet& proc = leader.parent();
 
    unsigned int blockStartIndex = blockStart - proc.startAddress().location();
    unsigned int blockEndIndex = blockEnd - proc.startAddress().location();
 
    if (MapTools::containsKey(blocks_, blockStart)) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "Basic block with given start address already exists!");
    }
    if (blockStart > blockEnd) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "Basic block start address is higher then it's end address!");
    }
 
    BasicBlockNode* node = new BasicBlockNode(blockStart, blockEnd);
 
    for (unsigned int i = blockStartIndex; i <= blockEndIndex; i++) {
        Instruction *newInstruction = proc.instructionAtIndex(i).copy();
        node->basicBlock().add(newInstruction);
    }
 
    addNode(*node);
    // Create entry node and add edge from it into current BB
    // if it's start is also start of procedure
    if (leader.address().location() == startAddress_.location()){
        BasicBlockNode* entry = new BasicBlockNode(0, 0, true);
        addNode(*entry);
        ControlFlowEdge* edge = new ControlFlowEdge;//(edgeCount());
        connectNodes(*entry, *node, *edge);
    }
 
    if (leader.hasAnnotations(TTAProgram::ProgramAnnotation::ANN_LOOP_INNER)) {
        node->basicBlock().setInInnerLoop();
        node->basicBlock().setTripCount(0); // 0 indicates unknown trip count
        
        if (leader.hasAnnotations(
                TTAProgram::ProgramAnnotation::ANN_LOOP_TRIP_COUNT)) {
 
            unsigned tripCount =
                static_cast<unsigned>(
                    leader.annotation(
                        0, TTAProgram::ProgramAnnotation::ANN_LOOP_TRIP_COUNT).
                    intValue());
            if (tripCount > 0) {
                node->basicBlock().setTripCount(tripCount);
            }
        }
    }
    blocks_[blockStart] = node;
    return *node;
}

References __func__, BoostGraph< BasicBlockNode, ControlFlowEdge >::addNode(), TTAProgram::Instruction::address(), TTAProgram::ProgramAnnotation::ANN_LOOP_INNER, TTAProgram::ProgramAnnotation::ANN_LOOP_TRIP_COUNT, TTAProgram::AnnotatedInstructionElement::annotation(), 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::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

iTail	The first instruction of the tail basic block (from).
iHead	The first instruction of the head basic block (to).
edgePredicate	The value of an edge (true, false, normal, call)
edgeType	Defines 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.

                                         {
 
    InstructionAddress sourceAddr = iTail.address().location();
    InstructionAddress targetAddr = iHead.address().location();
    if (!MapTools::containsKey(blocks_, sourceAddr)) {
        if (Application::verboseLevel() >= 1) {
            TCEString msg = (boost::format(
                "Source instruction %d:%s\nDestination instruction %d:%s\n")
                % Conversion::toString(sourceAddr)
                % POMDisassembler::disassemble(iTail)
                % Conversion::toString(targetAddr)
                % POMDisassembler::disassemble(iHead)).str();
            Application::logStream() << msg;
        }
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "Source basic block is missing!");
    }
    if (!MapTools::containsKey(blocks_, targetAddr)) {
        if (Application::verboseLevel() >= 1) {
            TCEString msg =(boost::format(
                "Source instruction %d:%s\nDestination instruction %d:%s\n")
                % Conversion::toString(sourceAddr)
                % POMDisassembler::disassemble(iTail)
                % Conversion::toString(targetAddr)
                % POMDisassembler::disassemble(iHead)).str();
            Application::logStream() << msg;
        }
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "Destination basic block is missing!");
    }
 
    BasicBlockNode& blockSource(*blocks_[sourceAddr]);
    BasicBlockNode& blockTarget(*blocks_[targetAddr]);
 
    ControlFlowEdge* theEdge;
    theEdge = new ControlFlowEdge(edgePredicate, edgeType);
 
    if (edgeType == ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH) {
        assert(blockSource.originalEndAddress() +1 ==
               blockTarget.originalStartAddress());
    }
 
    connectNodes(blockSource, blockTarget, *theEdge);
    return *theEdge;
}

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

leaders	Starting instructions of all basic blocks
leaderAddr	Address of a first instruction of present Basic Block
dataCodeRellocations	Read from POM, the possible targets of indirect jumps are in data code rellocation information
instruction	Currect instruction containing jump
procedure	The reference to current procedure
moveIndex	Index 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.

                   {
 
    const Instruction& instruction = procedure.instructionAtIndex(insIndex);
    if (instruction.move(moveIndex).source().isInstructionAddress()) {
        Move* tmp = &instruction.move(moveIndex);
        directJump(
            leaders, leaderAddr, insIndex, moveIndex,
            tmp->source().instructionReference().instruction(),
            procedure);
         return;
    }
    if (instruction.move(moveIndex).source().isImmediateRegister() ||
        instruction.move(moveIndex).source().isGPR()) {
        const Instruction* iPrev = &instruction;
        TTAProgram::TerminalRegister* sourceTerm =
            dynamic_cast<TTAProgram::TerminalRegister*>(
            &instruction.move(moveIndex).source());
        while (iPrev->address().location() > leaderAddr) {
            iPrev = &procedure.previousInstruction(*iPrev);
            const TTAProgram::TerminalRegister* destTerm = NULL;
            if (sourceTerm->isImmediateRegister()) {
                for (int j = 0; j < iPrev->immediateCount(); j++){
                    destTerm =
                        dynamic_cast<const TTAProgram::TerminalRegister*>(
                            &iPrev->immediate(j).destination());
                    TTAProgram::Immediate* tmpImm = &iPrev->immediate(j);
                    if (sourceTerm->equals(*destTerm)) {
                        directJump(
                            leaders, leaderAddr, insIndex, moveIndex,
                            tmpImm->value().instructionReference().
                            instruction(),
                            procedure);
                        return;
                    }
                }
            }
            if (sourceTerm->isGPR()) {
                for (int j = 0; j < iPrev->moveCount(); j++){
                    destTerm =
                        dynamic_cast<const TTAProgram::TerminalRegister*>(
                            &iPrev->move(j).destination());
                    if (destTerm == NULL) {
                        continue;
                    }
                    TTAProgram::Terminal* tmpTerm = &iPrev->move(j).source();
                    if (sourceTerm->equals(*destTerm)) {
                        if (tmpTerm->isInstructionAddress()){
                            directJump(
                                leaders, leaderAddr, insIndex, moveIndex,
                                tmpTerm->instructionReference().instruction(),
                                procedure);
                            return;
                        }
                        if (tmpTerm->isGPR() ||
                            tmpTerm->isImmediateRegister()) {
                            sourceTerm =
                                dynamic_cast<TTAProgram::TerminalRegister*>(
                                tmpTerm);
                            break;
                        }
                        if (tmpTerm->isFUPort()) {
                            indirectJump(
                                leaders, leaderAddr,
                                dataCodeRellocations, insIndex, moveIndex,
                                procedure);
                            return;
                        }
                    }
                }
            }
        }
    } else {
        if (instruction.move(moveIndex).source().isImmediateRegister()) {
            throw InvalidData(
                __FILE__, __LINE__, __func__,
                "Source of immediate write not found!");
        }
        indirectJump(
            leaders, leaderAddr, dataCodeRellocations,
            insIndex, moveIndex, procedure);
            return;
    }
}

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

node	basic block node to be removed and deleted.

Definition at line 2395 of file ControlFlowGraph.cc.

                                                        {
    removeNode(node);
    delete &node;
}

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

Referenced by SimpleIfConverter::updateCfg(), and Peel2BBLoops::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.

                                  {
    DFSBackEdgeVisitor vis;
    /// 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
    boost::depth_first_search(graph_, visitor(vis));
}

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

leaders	Set of beginnings of basic blocks
leaderAddr	Address of beginning of current basic block
instruction	Instruction to analyse (only one move in instruction)
procedure	Procedure we are working with

Definition at line 679 of file ControlFlowGraph.cc.

                                          {
 
    Instruction& instruction = procedure.instructionAtIndex(insIndex);
    // find other jumps from same ins.
    bool hasAnotherJump = hasInstructionAnotherJump(instruction, cfMoveIndex);
    TTAProgram::Move& move = instruction.move(cfMoveIndex);
    InstructionAddress targetAddr = instructionTarget.address().location();
    if (!MapTools::containsKey(leaders, targetAddr)) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "Target basic block of jump is missing!");
    }
 
    if (!move.isUnconditional()) {
        // if jump is conditional we consider guard
        // if we add also fall-through edge to next block,
        // for inverted value of guard
        // no other jump in same BB.
 
        Instruction* iNext = NULL;
        if (!hasAnotherJump) {
            int nextIndex = findNextIndex(procedure, insIndex, cfMoveIndex);
            if (nextIndex >= procedure.instructionCount()) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    (boost::format(
                         "Fall-through of jump missing:"
                         "Address: %d jump: %s\n") 
                     % (procedure.startAddress().location() + insIndex)
                     % POMDisassembler::disassemble(instruction)).str());
            }
            iNext = &procedure.instructionAtIndex(nextIndex);
            InstructionAddress nextAddr = 
                procedure.startAddress().location() + nextIndex;
            if (!MapTools::containsKey(leaders, nextAddr)) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    "Fall through basic block is missing!");
            }
        }
        if (move.guard().isInverted()) {
            // jumps on !bool, fall-through on bool
            createControlFlowEdge(
                *leaders[leaderAddr], instructionTarget,
                ControlFlowEdge::CFLOW_EDGE_FALSE);
            if (iNext != NULL) {
                createControlFlowEdge(
                    *leaders[leaderAddr], *iNext,
                    ControlFlowEdge::CFLOW_EDGE_TRUE,
                    ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
            }
        } else {
            createControlFlowEdge(
                *leaders[leaderAddr], instructionTarget,
                ControlFlowEdge::CFLOW_EDGE_TRUE);
            if (iNext != NULL) {
                createControlFlowEdge(
                    *leaders[leaderAddr], *iNext,
                    ControlFlowEdge::CFLOW_EDGE_FALSE,
                    ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
            }
        }
    } else {
        createControlFlowEdge(*leaders[leaderAddr], instructionTarget);
    }
}

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

InstanceNotFound	if the graph does not have a entry node.
InvalidData	if the graph has multiple nodes that are recognised as entry nodes.

Definition at line 1003 of file ControlFlowGraph.cc.

                                  {
    BasicBlockNode* result = NULL;
    bool found = false;
    for (int i = 0; i < nodeCount(); i++) {
        if (inDegree(node(i)) == 0) {
            // sanity check
            if (!static_cast<BasicBlockNode&>(node(i)).isEntryBB()) {
                // probably the entry node is not present
                // or there are more nodes which are not reachable from
                // entry nodes... likely caused by frontend not doing
                // any of -O{1,2} optimizations (in case of gcc)
                continue;
            }
            if (found == true) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    "Corrupted graph. Found multiple entry nodes.");
            }
            result = &node(i);
            found = true;
        }
    }
    if (found == false || result == NULL) {
        TCEString errorMsg("Graph does not have entry node.");
        throw InvalidData(__FILE__, __LINE__, __func__, errorMsg);
    }
    return *result;
}

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

InstanceNotFound	if the graph does not have a stop node.
InvalidData	if the graph has multiple nodes that are recognised as stop nodes.

Definition at line 1058 of file ControlFlowGraph.cc.

                                 {
 
    BasicBlockNode* result = NULL;
    bool found = false;
    bool unlinkedExitNode = false;
 
    for (int i = 0; i < nodeCount(); i++) {
        if (outDegree(node(i)) == 0) {
            // sanity check
            if (!static_cast<BasicBlockNode&>(node(i)).isExitBB()) {
                // probably the stop node is not present
                unlinkedExitNode = true;
                continue;
            }
            if (found == true) {
                throw InvalidData(
                    __FILE__, __LINE__, __func__,
                    "Corrupted graph. Found multiple exit nodes.");
            }
            result = &node(i);
            found = true;
        }
    }
    if (found == false || result == NULL || unlinkedExitNode == true) {
        TCEString errorMsg("Graph does not have exit node.");
        throw InvalidData(__FILE__, __LINE__, __func__, errorMsg);
    }
    return *result;
}

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

Referenced by addEntryExitEdge(), addExit(), 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

bbn	basic 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.

                                                                        {
    if (bbn.isEntryBB()) {
        return NULL;
    }
 
    EdgeSet iEdges = inEdges(bbn);
    for (auto i: iEdges) {
        if (i->isFallThroughEdge() || i->isCallPassEdge()) {
            return &tailNode(*i);
        }
    }
    return NULL;
}

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

bbn	basic 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.

                                                                   {
    if (bbn.isExitBB()) {
        return NULL;
    }
 
    EdgeSet oEdges = outEdges(bbn);
    for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
        if ((*i)->isFallThroughEdge() || (*i)->isCallPassEdge()) {
            return &headNode(**i);
        }
    }
    return NULL;
}

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

Referenced by copyToLLVMMachineFunction(), copyToProcedure(), CallsToJumps::handleControlFlowGraph(), CopyingDelaySlotFiller::mightFillIncomingTo(), 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

src	basic block node which is the tail of the edge, containing the jump.
edge	edge whose target address is being searched.

Definition at line 3006 of file ControlFlowGraph.cc.

                                                                         {
    auto& bb = src.basicBlock();
    for (int i = bb.instructionCount()-1;
         i >= bb.skippedFirstInstructions(); i--) {
        auto& ins = bb[i];
        for (int j = 0; j < ins.moveCount(); j++) {
            auto& m = ins.move(j);
            if (!m.isJump())
                continue;
            auto ep = ControlFlowEdge::edgePredicateFromMove(m);
            if (e.edgePredicate() == ep) {
                if (m.source().isInstructionAddress()) {
                    return &m.source();
                } else {
                    auto limm = findLimmWrite(m, src, i);
                    assert(limm != nullptr);
                    return &limm->value();
                }
            }
        }
    }
    return nullptr;
}

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

move	move containing the immediate use.
bbn	basic block containing the move
moveIndex	index of the instruction containing the move in the BB.

Definition at line 3037 of file ControlFlowGraph.cc.

                                                              {
    auto& bb = bbn.basicBlock();
    const TTAMachine::ImmediateUnit& immu = move.source().immediateUnit();
    int lat = immu.latency();
    int i = moveIndex - lat;
    while (i >= bb.skippedFirstInstructions()) {
        TTAProgram::Instruction& ins = bb[i];
        for (int j = 0; j < ins.immediateCount(); j++) {
            auto& imm = ins.immediate(j);
            if (&imm.destination().immediateUnit() == &immu &&
                move.source().index() == imm.destination().index()) {
                return &imm;
            }
        }
        i--;
    }
    if (inDegree(bbn) == 1) {
        BasicBlockNode* pred = *predecessors(bbn).begin();
        if (!pred->isNormalBB()) {
            return nullptr;
        }
        // search staring from last ins of prev bb
        return findLimmWrite(
            move, *pred, pred->basicBlock().instructionCount() + lat -1);
    }
    return nullptr;
}

References BasicBlockNode::basicBlock(), findLimmWrite(), 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(), and findLimmWrite().

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.

                                      {
    for (unsigned opc = 0; opc < tii.getNumOpcodes(); ++opc) {
        if (name.ciEqual(tii.getName(opc).str())) {
            return tii.get(opc);
        }
    }
    abortWithError(TCEString("Could not find ") << name << " in the TII.");
}

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

procedure	procedure we are processing
jumpInsIndex	index of the jump inside in the procedure
index	of the jump move in the jump instruction.

Definition at line 877 of file ControlFlowGraph.cc.

                                                                          {
    Instruction& instruction = proc.instructionAtIndex(jumpInsIndex);
    
    // POM allows mixed scheduled an unscheduled code, so each jump
    // must check from machine how many delay slots it needs
    FunctionUnit& unit = const_cast<FunctionUnit&>(
            instruction.move(jumpMoveIndex).destination().functionUnit());
    ControlUnit* control = dynamic_cast<ControlUnit*>(&unit);
    if (control == NULL) {
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__, (boost::format(
            "Control flow move '%s' has destination unit %s, "
            "not global control unit!")
            % POMDisassembler::disassemble(instruction.move(jumpMoveIndex))
            % unit.name()).str());
    }
    int delaySlots = control->delaySlots();
    int nextIndex = jumpInsIndex + delaySlots + 1;
    if (nextIndex > proc.instructionCount()) {
        throw InvalidData(
            __FILE__, __LINE__, __func__,
            "Procedure ends before all delay slot instructions");
    }
    // Then check for control flow instructions inside delay slots.
    for (int i = jumpInsIndex + 1; i < nextIndex; i++) {
        Instruction &dsIns = proc.instructionAtIndex(i);
        if (dsIns.hasControlFlowMove()) {
            throw InvalidData(
                __FILE__, __LINE__, __func__,
                (boost::format(
                     "Control flow operation in delay slot"
                     " in %d! Instruction:\n%s")
                 % dsIns.address().location()
                 % POMDisassembler::disassemble(dsIns)
                    ).str());
        }
    }
    return nextIndex;
}

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.

                                     {
    NodeSet queuedBBs;
    NodeSet processedBBs;
 
    ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
    AssocTools::append(firstBBs,queuedBBs);
 
    while (queuedBBs.size() != 0) {
        BasicBlockNode& current = **queuedBBs.begin();
        if (current.isNormalBB()) {
            processedBBs.insert(&current);
            NodeSet succs = successors(current);
            for (NodeSet::iterator i = succs.begin(); i != succs.end(); i++) {
                if (!AssocTools::containsKey(processedBBs,*i)) {
                    queuedBBs.insert(*i);
                }
            }
            processedBBs.insert(&current);
        }
        queuedBBs.erase(&current);
    }
    return processedBBs;
}

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.

                                         {
 
    int diff = mach.controlUnit()->delaySlots() +1;
 
    // search forwards.
    const BasicBlockNode* ftBBN = src.successor();
    while (ftBBN != nullptr && ftBBN->isNormalBB()) {
        if (jumpToBBN(jumpAddr, *ftBBN)) {
            return diff;
        }
        int nextSz = ftBBN->maximumSize();
        // max size not known, give up.
        if (nextSz == INT_MAX) {
            break;
        }
        ftBBN = ftBBN->successor();
        diff += nextSz;
    }
 
    // Then search backwards.
    diff = mach.controlUnit()->delaySlots() +1;
    ftBBN = &src;
    while (ftBBN != nullptr) {
        int sz = ftBBN->maximumSize();
 
        // maximum size not known, give up?
        if (sz == INT_MAX) {
            return INT_MAX;
        }
        diff -= sz;
 
        if (jumpToBBN(jumpAddr, *ftBBN)) {
            return diff;
        }
        ftBBN = ftBBN->predecessor();
    }
    return INT_MAX;
}

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.

                                                   {
    NodeSet unreachableNodes;
    // find dead nodes
    for (int i = 0; i < nodeCount(); i++) {
        BasicBlockNode& n = node(i);
        if (!AssocTools::containsKey(reachableNodes,&n) &&
            n.isNormalBB()) {
            unreachableNodes.insert(&n);
        }
    }
    return unreachableNodes;
}

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.

                                        {
    ControlFlowGraph::NodeSet entrySucc = successors(entryNode());
    if (entrySucc.size() != 1) {
    throw InvalidData(__FILE__,__LINE__,__func__,
              "Entry node has not exactly one successor");
    }
    BasicBlockNode* firstNode = *entrySucc.begin();
    if (!firstNode->isNormalBB()) {
    throw InvalidData(__FILE__,__LINE__,__func__,
              "Successor of entry node is not normal bb");
    }
    return *firstNode;
}

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

Referenced by CopyingDelaySlotFiller::updateJumpsAndCfg().

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.

                                          {
  
    if (MapTools::containsKey(bbMap_, &bb)) {
        return *bbMap_[&bb];
    } else {        
        llvm::MachineBasicBlock* mbb = mf.CreateMachineBasicBlock();
        mf.push_back(mbb);    
        bbMap_[&bb] = mbb;
        return *mbb;
    }  
}

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

bbn	bbn to check for fall-thru predecessors

Returns: if control can fall-thru to this BB.

Definition at line 1401 of file ControlFlowGraph.cc.

                                                                       {
    EdgeSet iEdges = inEdges(bbn);
    for (EdgeSet::iterator i = iEdges.begin(); i != iEdges.end(); i++) {
        if ((*i)->isFallThroughEdge() || (*i)->isCallPassEdge()) {
            return true;
        }
    }
    return false;
}

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

bbn the node

Definition at line 2253 of file ControlFlowGraph.cc.

                                                                          {
    ControlFlowGraph::EdgeSet jumpEdges = incomingJumpEdges(bbn);
    
    for (auto e: jumpEdges) {
        if (&tailNode(*e) != &bbn) {
            return true;
        }
    }
    return false;
}

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

ins	instruction to check
moveIndex	index of the move triggering the known jump.

Definition at line 758 of file ControlFlowGraph.cc.

                                           {
    for (int i = 0; i < ins.moveCount(); i++) {
        if (i != moveIndex && ins.move(i).isJump()) {
            return true;
        }
    }
    return false;
}

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.

                                     {
    bool hasUncondSucc = false;
 
    for (int i = 0; i < outDegree(bbn); i++) {
        Edge& e = outEdge(bbn,i);
        if (e.isNormalEdge()) {
            if (hasUncondSucc) {
                return true;
            } else {
                hasUncondSucc = true;
            }
        }
    }
    return false;
}

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

bbn the node

Returns: the edge or null, if none found.

Definition at line 2233 of file ControlFlowGraph.cc.

                                                                {
 
    auto edges = boost::in_edges(descriptor(bbn), graph_);
    for (auto i = edges.first; i != edges.second; ++i) {
        auto edge = graph_[(*i)];
        if (!edge->isJumpEdge()) {
            edgeDescriptors_[edge] = *i;
            return edge;
        }
    }
    return nullptr;
}

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

Referenced by CopyingDelaySlotFiller::mightFillIncomingTo(), and CopyingDelaySlotFiller::updateJumpsAndCfg().

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.

                                                                       {
 
    auto edges = boost::in_edges(descriptor(bbn), graph_);
    EdgeSet result;
    for (auto i = edges.first; i != edges.second; ++i) {
        auto edge = graph_[(*i)];
        if (edge->isJumpEdge()) {
            edgeDescriptors_[edge] = *i;
            result.insert(edge);
        }
    }
    return result;
}

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

Referenced by hasIncomingExternalJumps(), and CopyingDelaySlotFiller::mightFillIncomingTo().

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

leaders	Set of beginnings of basic blocks
leaderAddr	Address of beginning of current basic block
dataCodeRellocations	Rellocation information for targets of jump
instruction	Instruction to analyse (only one move in instruction)
procedure	Procedure we are working with

Definition at line 779 of file ControlFlowGraph.cc.

                                          {
 
    Instruction& instruction = procedure.instructionAtIndex(insIndex);
    InstructionAddressMap::iterator dataCodeIterator =
        dataCodeRellocations.begin();
    bool hasAnotherJump = hasInstructionAnotherJump(instruction, cfMoveIndex);
    TTAProgram::Move& move = instruction.move(cfMoveIndex);
 
    if (move.hasAnnotations(ProgramAnnotation::ANN_JUMP_TO_NEXT)) {
        int nextIndex = findNextIndex(procedure, insIndex, cfMoveIndex);
        if (nextIndex < procedure.instructionCount()) {
            const Instruction& iNext = procedure.instructionAtIndex(nextIndex);
            createControlFlowEdge(
                *leaders[leaderAddr], iNext,
                ControlFlowEdge::CFLOW_EDGE_FAKE);
        }
        else {
            throw IllegalProgram(
                __FILE__,__LINE__,__func__,
                "Jump to next annotation without next instruction");
        }
        return;
    }
 
    ControlFlowEdge::CFGEdgePredicate edgePredicate =
        ControlFlowEdge::CFLOW_EDGE_NORMAL;
    ControlFlowEdge::CFGEdgePredicate fallPredicate =
        ControlFlowEdge::CFLOW_EDGE_NORMAL;
    if (instruction.move(cfMoveIndex).isUnconditional() == false) {
        if (instruction.move(cfMoveIndex).guard().isInverted()) {
            edgePredicate = ControlFlowEdge::CFLOW_EDGE_FALSE;
            fallPredicate = ControlFlowEdge::CFLOW_EDGE_TRUE;
        } else {
            edgePredicate = ControlFlowEdge::CFLOW_EDGE_TRUE;
            fallPredicate = ControlFlowEdge::CFLOW_EDGE_FALSE;
        }
    }
 
    if (!instruction.move(cfMoveIndex).isUnconditional() &&
        !hasAnotherJump) {
        int nextIndex = findNextIndex(procedure, insIndex, cfMoveIndex);
        InstructionAddress nextAddr = 
            procedure.startAddress().location() + nextIndex;
        if (nextIndex >= procedure.instructionCount() ||
            !MapTools::containsKey(leaders, nextAddr)) {
            throw InvalidData(
                __FILE__, __LINE__, __func__,
                "Fall through basic block is missing!");
        }
        Instruction& iNext = procedure.instructionAtIndex(nextIndex);
        createControlFlowEdge(
                    *leaders[leaderAddr], iNext,fallPredicate,
                    ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
    }
 
    // Check if this jump is a return. 
    const Port* port =
        &instruction.move(cfMoveIndex).source().port();
 
    if (dynamic_cast<const SpecialRegisterPort*>(port) != NULL || 
        move.hasAnnotations(
            ProgramAnnotation::ANN_STACKFRAME_PROCEDURE_RETURN)) {
        returnSources_.insert(
            ReturnSource(leaderAddr, edgePredicate));
        return;
    }
    
    while (dataCodeIterator != dataCodeRellocations.end()) {
    // Target of jump is reachable also from it's predecessor
    // block, in case there is no unconditional jump at the end.
    // If the end of previous BB is conditional jump it will be
    // added elsewhere.
    // Target is limited to present procedure, no interprocedural
    // indirect jump for now.
        createControlFlowEdge(
            *leaders[leaderAddr], *(*dataCodeIterator).second,
            edgePredicate);
        dataCodeIterator++;
    }
}

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.

                                              {
    if (program_ == NULL) {
        return *irm_;
        throw NotAvailable(__FILE__,__LINE__,__func__,
            "cfg does not have program");
    }
    return program_->instructionReferenceManager();
}

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

Referenced by LoopPrologAndEpilogBuilder::addPrologFromRM(), LoopPrologAndEpilogBuilder::addPrologIntoCfg(), llvm::LLVMTCEIRBuilder::compileOptimized(), convertBBRefsToInstRefs(), ControlFlowGraphPass::executeBasicBlockPass(), BBSchedulerController::handleBBNode(), CallsToJumps::handleControlFlowGraph(), SimpleIfConverter::handleControlFlowGraph(), Peel2BBLoops::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.

                                                                      {
    for (int i = 0; i < outDegree(node); i++) {
        ControlFlowEdge& e = outEdge(node, i);
        if (e.isJumpEdge() && &headNode(e) == &node) {
            assert(e.isBackEdge());
            return true;
        }
    }
    return false;
}

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.

                                                   {
    for (int i = 0; i < outDegree(bbn); i++) {
        Edge& e = outEdge(bbn,i);
        if (e.isJumpEdge()) {
            return &headNode(e);
        }
    }
    return NULL;
}

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

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

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.

                                                                         {
    if (!bbn.isNormalBB()) {
        return false;
    }
    if (jumpAddr.isBasicBlockReference()) {
        auto& target = jumpAddr.basicBlock();
        return &target  == &bbn.basicBlock();
    }
    if (!jumpAddr.isCodeSymbolReference() && jumpAddr.isInstructionAddress()){
        auto& ir = jumpAddr.instructionReference();
        return &ir.instruction() ==
            &bbn.basicBlock().firstInstruction();
    }
    return false;
}

References BasicBlockNode::basicBlock(), TTAProgram::Terminal::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.

                                                                     {
 
    if (ddg != NULL && 
        (!ddg->hasAllRegisterAntidependencies() &&
         ddg->hasIntraBBRegisterAntidependencies())) {
        ddg->fixInterBBAntiEdges(node1, node2, false);
    }
    assert(node1.isNormalBB());
    assert(node2.isNormalBB());
    TTAProgram::BasicBlock& bb1 = node1.basicBlock();
    TTAProgram::BasicBlock& bb2 = node2.basicBlock();
    for (int i = bb2.instructionCount() -1; i >= 0; i--) {
        Instruction& ins = bb2.instructionAtIndex(i);
        if (ddg != NULL) {
            for (int k = 0; k < ins.moveCount(); k++) {
                Move& move = ins.move(k);
                MoveNode* mn = &ddg->nodeOfMove(move);
                ddg->setBasicBlockNode(*mn, node1);
            }
        }
    }
    
    if (node1.basicBlock().liveRangeData_ != NULL &&
        node2.basicBlock().liveRangeData_ != NULL) {
        node1.basicBlock().liveRangeData_->merge(
            *node2.basicBlock().liveRangeData_);
    }
 
    for (int i = bb2.skippedFirstInstructions(),
             end = bb2.instructionCount();
         i < end; i++) {
        Instruction& ins = bb2[bb2.skippedFirstInstructions()];
        bb2.remove(ins);
        bb1.add(&ins);
    }
 
    EdgeSet n2in = inEdges(node2);
    for (EdgeSet::iterator i = n2in.begin(); i != n2in.end(); i++) {
        ControlFlowEdge* e = *i;
        const BasicBlockNode& tail = tailNode(*e);
        if (&tail != &node1) {
            moveInEdge(node2, node1, *e);
        }
    }
 
    EdgeSet n2out = outEdges(node2);
    for (EdgeSet::iterator i = n2out.begin(); i != n2out.end(); i++) {
        ControlFlowEdge* e = *i;
        if (!connectingEdge.isNormalEdge()) {
            assert(e->isNormalEdge());
            e->setPredicate(connectingEdge.edgePredicate());
        }
        moveOutEdge(node2, node1, *e);
    }
 
    removeNode(node2);
    delete &node2;
    // TODO: CFG edges
}

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.

                              {
 
#ifdef DEBUG_BB_OPTIMIZER
    writeToDotFile(
        (boost::format("%s_before_optimize_cfg.dot") %
         name()).str());
#endif
 
    ControlFlowGraph::NodeSet firstBBs = successors(entryNode());
    assert(firstBBs.size() == 1);
    BasicBlockNode* firstBBN = *firstBBs.begin();
    BasicBlockNode* currentBBN = firstBBN;
    entryNode().link(firstBBN);
 
    // find and queue reachable nodes
    NodeSet queuedNodes = findReachableNodes();
    NodeSet unreachableNodes = findUnreachableNodes(queuedNodes);
 
    if (removeDeadCode) {
        removeUnreachableNodes(unreachableNodes, ddg);
    }
 
    // then loop as long as we have BBs which have not been written to
    // the procedure.
    while (currentBBN != NULL) {
 
#ifdef DEBUG_BB_OPTIMIZER
            std::cerr << "current node: " << currentBBN->toString() << 
                std::endl;
#endif
        BasicBlockNode* nextNode = NULL;
        TTAProgram::BasicBlock& bb = currentBBN->basicBlock();
        queuedNodes.erase(currentBBN);
 
        // if has a fall-through node, it has to be the next node
        BasicBlockNode* ftNode = fallThruSuccessor(*currentBBN);
        bool unhandledFT = false;
        while (ftNode != NULL && ftNode->isNormalBB()) {
            if (queuedNodes.find(ftNode) == queuedNodes.end()) {
                std::cerr << "not-queued fall-thru: " << ftNode->toString()
                          << " current: " << currentBBN->toString() << 
                    std::endl;
                writeToDotFile("optimizeCFGFallThruBBNotQueued.dot");
            }
            // must not be already processed.
            assert(queuedNodes.find(ftNode) != queuedNodes.end());
 
#ifdef DEBUG_BB_OPTIMIZER
            std::cerr << "\tfound FT node: " << ftNode->toString() << std::endl;
#endif
            const ControlFlowEdge& cfe = 
                **connectingEdges(*currentBBN, *ftNode).begin();
 
            // if fall-through node has no other predecessors, merge.
            if (inDegree(*ftNode) == 1 && !cfe.isCallPassEdge()
                && ftNode->isScheduled() == currentBBN->isScheduled() // *1
                && (outDegree(*currentBBN) == 1 || ftNode->basicBlock().isEmpty())) {
 
                // *1: No merging of inline asm block (they are set as
                //     scheduled before others). After all is scheduled this
                //     might be ok.
#ifdef DEBUG_BB_OPTIMIZER
                std::cerr << "Merging: " << currentBBN->toString()
                          << " with: " << ftNode->toString() << std::endl;
                writeToDotFile("before_merge.dot");
                if (cfe.isBackEdge()) {
                    std::cerr << "Warning: merging over back edge." << 
                        std::endl;
                }
#endif
                queuedNodes.erase(ftNode);
                mergeNodes(*currentBBN, *ftNode, ddg, cfe);
#ifdef DEBUG_BB_OPTIMIZER
                writeToDotFile("after_merge.dot");
                std::cerr << "Merged with ft node." << std::endl;
#endif
                ftNode = fallThruSuccessor(*currentBBN);
            } else {
                currentBBN->link(ftNode);
#ifdef DEBUG_BB_OPTIMIZER
                writeToDotFile("linked.dot");
#endif
                currentBBN = ftNode;
                unhandledFT = true;
                break;
            }
        }
 
        if (unhandledFT) continue;
 
        // Select some node, preferably successors without ft-preds
        // The jump can then be removed.
        EdgeSet oEdges = outEdges(*currentBBN);
        for (EdgeSet::iterator i = oEdges.begin(); i != oEdges.end(); i++) {
            ControlFlowEdge& e = **i;
            BasicBlockNode& head = headNode(e);
            if (!hasFallThruPredecessor(head) && head.isNormalBB() &&
                queuedNodes.find(&head) != queuedNodes.end()
                && currentBBN->isScheduled() == head.isScheduled() /* *1 */) {
                // *1: No merging of inline asm block (they are set as
                //     scheduled before others). After all is scheduled this
                //     might be ok.
 
                // try to remove the jump as it's jump to the next BB.
                RemovedJumpData rjd = removeJumpToTarget(
                    bb, head.basicBlock().firstInstruction(), 0, ddg);
                if (rjd != JUMP_NOT_REMOVED) {
                    // if BB got empty,
                    // move refs to beginning of the next BB.
                    if (rjd == LAST_ELEMENT_REMOVED) {
                        Instruction& ins = bb.instructionAtIndex(0);
                        if (irm.hasReference(ins)) {
                            irm.replace(
                                ins, head.basicBlock().instructionAtIndex(
                                    head.basicBlock().
                                    skippedFirstInstructions()));
                        }
                        bb.skipFirstInstructions(bb.instructionCount());
                        queuedNodes.erase(&head);
                        mergeNodes(*currentBBN, head, ddg, e);
#ifdef DEBUG_BB_OPTIMIZER
                        std::cerr << "Merged with after jump removal(1)" <<
                            std::endl;
#endif
                        nextNode = currentBBN;
                        break;
                    }
                    // we removed a jump so convert the jump edge into
                    // fall-through edge, OR merge BBs.
 
                    if (inDegree(head) == 1 && outDegree(*currentBBN) == 1) {
#ifdef DEBUG_BB_OPTIMIZER
                        std::cerr << "Merging after jump removal.." << std::endl;
#endif
                        // should not be allowd to do this if has return
 
                        queuedNodes.erase(&head);
                        mergeNodes(*currentBBN, head, ddg, e);
                        nextNode = currentBBN;
#ifdef DEBUG_BB_OPTIMIZER
                        std::cerr << "Merged with after jump removal(2)" <<
                            std::endl;
#endif
                    } else {
                        ControlFlowEdge* ftEdge = new ControlFlowEdge(
                            e.edgePredicate(), 
                            ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH);
                        removeEdge(e);
                        connectNodes(*currentBBN, head, *ftEdge);
                        nextNode = &head;
                    }
                    // if we did remove a back edge, we need to scan the cfg
                    // again for back edges.
                    // TODO: should we also then mark ddg edges that
                    // do over this cfg edge?
                    if (e.isBackEdge()) {
                        detectBackEdges();
                    }
                    break; // continue outer;
                }
            }
        }
        if (nextNode != NULL) {
            continue;
        }
 
        // need to select SOME node as successor.
        // first without ft-predecessor usually is a good candidate.
        // smarter heuristic does not seem to help at all.
        // try to select
        bool ftPred = false;
        for (NodeSet::iterator i = queuedNodes.begin();
             i != queuedNodes.end(); i++) {
            if (!hasFallThruPredecessor(**i)) {
                nextNode = *i;
                break;
            } else {
                ftPred = true;
            }
        }
 
        if (!removeDeadCode) {
            // unreachable node having ft may have prevented us from
            // managing some node whose fall-thru succs prevent
            // futher nodes. try to select some unreached node.
            if (nextNode == NULL && ftPred) {
                for (NodeSet::iterator i = unreachableNodes.begin();
                     i != unreachableNodes.end(); i++) {
                    if (fallThruSuccessor(**i) != NULL) {
                        nextNode = *i;
                        unreachableNodes.erase(*i);
                        break;
                    }
                }
            }
        }
        if (nextNode == NULL) {
            currentBBN->link(&exitNode());
            break;
        }
        else {
            currentBBN->link(nextNode);
            currentBBN = nextNode;
        }
    }
#ifdef DEBUG_BB_OPTIMIZER
    writeToDotFile(
        (boost::format("%s_after_optimize_cfg.dot") %
         name()).str());
#endif
}

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.

                                  {
    const CFGStatistics& stats = statistics();
 
    TCEString result = "";
    result += (boost::format("Procedure '%s' has %d moves, %d immediate"
        " writes, %d instructions and %d bypassed moves in %d basic blocks.")
        % procedureName() % stats.moveCount() % stats.immediateCount()
        % stats.instructionCount() % stats.bypassedCount()
        % stats.normalBBCount()).str();
    result += (boost::format("\n\tLargest basic block has %d moves, %d"
        " immediate writes, %d instructions and %d bypassed moves.\n")
        % stats.maxMoveCount() % stats.maxImmediateCount()
        % stats.maxInstructionCount() % stats.maxBypassedCount()).str();
    return result;
}

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.

                                      {
    return procedureName_;
}

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.

                                {
    return program_;
}

References program_.

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

◆ 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.

                                      {
    // Edge from Entry to Exit node of CFG needs to be removed
    // it is not really control flow edge
    BasicBlockNode& entry = entryNode();
    std::vector<std::pair<BasicBlockNode*, int> > fromEntry;
    for (int i = 0; i < outDegree(entry); i++) {
        fromEntry.push_back(
            std::pair<BasicBlockNode*, int>(
                &headNode(outEdge(entry,i)), outEdge(entry,i).edgeID()));
    }
    for (unsigned int i = 0; i < fromEntry.size(); i++) {
        disconnectNodes(entry, *(fromEntry[i].first));
        ControlFlowEdge* edge = new ControlFlowEdge; //(fromEntry[i].second);
        connectNodes(entry, *(fromEntry[i].first), *edge);
    }
    disconnectNodes(entryNode(), exitNode());
}

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

cs	CodeSnippet where to remove the jump from.
target	jump target instruction.
idx	index 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.

                              {
    int index = cs.instructionCount() -1; // - delaySlots;
 
    Move* lastJump = NULL;
    for (;index >= idx ; index--) {
        Instruction& ins = cs.instructionAtIndex(index);
        for (int j = 0; j < ins.moveCount(); j++) {
            Move& move = ins.move(j);
            if (!move.isJump()) {
                continue;
            }
 
            TTAProgram::Terminal& term = move.source();
            if (term.isInstructionAddress()) {
                TTAProgram::TerminalInstructionReference& tia =
                    dynamic_cast<TTAProgram::TerminalInstructionReference&>(
                        term);
                TTAProgram::InstructionReference& ir =
                    tia.instructionReference();
 
                // found jump to target? remove this?
                if (&ir.instruction() == &target) {
                    if (lastJump != NULL) {
                        // TODO: should also check that no other moves
                        // as the lastJump after the delay slots of
                        // the move.
                        if (lastJump->isUnconditional()) {
                            // if removing conditional jump,
                            // make the other jump have opposite guard
                            if (!move.isUnconditional()) {
 
                                TTAProgram::MoveGuard* invG = NULL;
                                // if already scheduled,
                                // guard must be in same bus
                                if (!lastJump->bus().machine()->
                                    isUniversalMachine()) {
                                    invG = CodeGenerator::createInverseGuard(
                                        move.guard(), &lastJump->bus());
                                } else {
                                    invG = CodeGenerator::createInverseGuard(
                                        move.guard());
                                }
                                if (invG == NULL) {
                                    return JUMP_NOT_REMOVED;
                                }
                                lastJump->setGuard(invG);
                            }
                            
                            if (ddg != NULL) {
#ifdef DEBUG_BB_OPTIMIZER
                                std::cerr << "removing jump node from ddg."
                                          << std::endl;
#endif
                                MoveNode* mn = &ddg->nodeOfMove(move);
                                ddg->removeNode(*mn);
                                delete mn;
                            }
 
                            ins.removeMove(move);
                            return JUMP_REMOVED;
                        } else {
                            // two conditional jumps? nasty. no can do
                            return JUMP_NOT_REMOVED;
                        }
                    } else {
                        if (ddg != NULL) {
#ifdef DEBUG_BB_OPTIMIZER
                            std::cerr << "removing jump node from ddg(2)."
                                      << std::endl;
#endif
                            MoveNode* mn = &ddg->nodeOfMove(move);
                            ddg->removeNode(*mn);
                            delete mn;
                        }
 
                        ins.removeMove(move);
                        // check if there are moves/immeds left.
                        // if not, update refs.
                        for (; idx < cs.instructionCount(); idx++) {
                            Instruction& ins2 = cs.instructionAtIndex(idx);
                            if (ins2.moveCount() > 0 ||
                                ins2.immediateCount() > 0) {
                                return JUMP_REMOVED;
                            }
                        }
                        return LAST_ELEMENT_REMOVED;
                    }
                }
            }
            lastJump = &move;
        }
    }
    return JUMP_NOT_REMOVED;
}

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.

                                                    {
    for (NodeSet::iterator i = nodes.begin(); i != nodes.end(); i++) {
        BasicBlockNode* bbn = *i;
        removeNode(*bbn);
        if (ddg != NULL) {
            TTAProgram::BasicBlock& bb = bbn->basicBlock();
            for (int j = 0; j < bb.instructionCount(); j++) {
                Instruction& ins = bb.instructionAtIndex(j);
                for (int k = 0; k < ins.moveCount(); k++) {
                    Move& move = ins.move(k);
                    MoveNode* mn = &ddg->nodeOfMove(move);
                    ddg->removeNode(*mn);
                    delete mn;
                }
            }
            delete bbn;
        }
    }
}

References BasicBlockNode::basicBlock(), TTAProgram::CodeSnippet::instructionAtIndex(), TTAProgram::CodeSnippet::instructionCount(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), DataDependenceGraph::nodeOfMove(), DataDependenceGraph::removeNode(), and BoostGraph< BasicBlockNode, ControlFlowEdge >::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.

                                      {
    ReversedGraph* R = new ReversedGraph(graph_);
    return *R;
}

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.

                                                                  {
    for (int i = 0; i < outDegree(bbn); i++) {
        Edge& e = outEdge(bbn,i);
        if (e.isTrueEdge()) {
            e.setPredicate(ControlFlowEdge::CFLOW_EDGE_FALSE);
        } else if (e.isFalseEdge()) {
            e.setPredicate(ControlFlowEdge::CFLOW_EDGE_TRUE);
        } else {
            std::cerr << "node in question: " << bbn.toString() <<
                " edge: " << e.toString() << std::endl;
            writeToDotFile("invalid_predicate.dot");
            assert(false && "Can only reverse predicate true or false");
        }
    }
}

References assert, ControlFlowEdge::CFLOW_EDGE_FALSE, ControlFlowEdge::CFLOW_EDGE_TRUE, ControlFlowEdge::isFalseEdge(), ControlFlowEdge::isTrueEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outDegree(), BoostGraph< BasicBlockNode, ControlFlowEdge >::outEdge(), ControlFlowEdge::setPredicate(), BasicBlockNode::toString(), ControlFlowEdge::toString(), and GraphBase< GraphNode, GraphEdge >::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.

                                {
 
    for (int i = 0; i < nodeCount(); i++) {
        auto& n = node(i);
        auto& bb = n.basicBlock();
        // Remove the skipped first instructions. They are totally dead!
        // they only exist to not mess up BB vs RM bookkeeping,
        // but no need for this anymore!
        for (int j = bb.skippedFirstInstructions(); j > 0; j--) {
            auto& ins = bb[0];
 
            if (instructionReferenceManager().hasReference(ins)) {
                std::cerr << "Skipped ins has ref: " << ins.toString()
                          << std::endl;
                std::cerr << "node: " << n.toString() << std::endl;
                writeToDotFile("skipped_ins_has_ref.dot");
            }
            assert(!instructionReferenceManager().hasReference(ins));
 
            bb.remove(ins);
        }
        bb.skipFirstInstructions(0);
        // now our BB instructions start from index 0.
 
        if (!bb.instructionCount()) continue;
 
        // do we need to split this?
        auto& firstIns = bb[0];
        auto ns = inEdges(n);
 
        for (int j = 1; j < bb.instructionCount(); j++) {
            auto& ins = bb[j];
 
            // need to split before this instruction?
            if (instructionReferenceManager().hasReference(ins)) {
                BasicBlockNode* newBBN = splitBB(n, j);
 
                auto firstInsRef =
                    instructionReferenceManager().createReference(firstIns);
                TTAProgram::TerminalInstructionReference tir(firstInsRef);
 
                // update in edges. jumps that don't point to original start ins
                // should be updated to this.
                for (auto e: ns) {
                    if (!e->isJumpEdge()) {
                        continue;
                    }
                    auto& srcNode = tailNode(*e);
                    auto t = findJumpAddress(srcNode, *e);
                    if (!tir.equals(*t)) {
                        moveInEdge(n, *newBBN, *e, &srcNode);
                    }
                }
                break;
            }
        }
    }
}

References assert, TTAProgram::InstructionReferenceManager::createReference(), TTAProgram::TerminalInstructionReference::equals(), findJumpAddress(), TTAProgram::InstructionReferenceManager::hasReference(), BoostGraph< BasicBlockNode, ControlFlowEdge >::inEdges(), instructionReferenceManager(), BoostGraph< BasicBlockNode, ControlFlowEdge >::moveInEdge(), BoostGraph< BasicBlockNode, ControlFlowEdge >::node(), BoostGraph< BasicBlockNode, ControlFlowEdge >::nodeCount(), splitBB(), BoostGraph< BasicBlockNode, ControlFlowEdge >::tailNode(), and GraphBase< GraphNode, GraphEdge >::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.

                                                    {
        irm_ = &irm;
    }

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.

                                    {
    
    TTAProgram::BasicBlock& bb = bbn.basicBlock();
    TTAProgram::BasicBlock* newbb = new TTAProgram::BasicBlock();
    BasicBlockNode* newbbn = new BasicBlockNode(*newbb);
    // Inline Asm BBs are set scheduled, copy the property.
    newbbn->setScheduled(bbn.isScheduled());
    addNode(*newbbn);
    
    // the BB can contain multiple calls, handle them
    // in the new BB
    moveOutEdges(bbn, *newbbn);                
    
    // move the instructions after the call in the old BB to
    // the new one.
    // no index update because remove puts to same index
    for (int i = index; i < bb.instructionCount(); ) {
        TTAProgram::Instruction& ins = bb.instructionAtIndex(i);
        bb.remove(ins);
        newbb->add(&ins);
    }
 
    ControlFlowEdge* cfe = new ControlFlowEdge(
        ControlFlowEdge::CFLOW_EDGE_NORMAL, 
        ControlFlowEdge::CFLOW_EDGE_CALL);
    connectNodes(bbn, *newbbn, *cfe);
 
    if (bb.liveRangeData_) {
        newbb->liveRangeData_ = new LiveRangeData;
        newbb->liveRangeData_->inlineAsmRegUses_ =
            bb.liveRangeData_->inlineAsmRegUses_;
        newbb->liveRangeData_->inlineAsmRegDefs_ =
            bb.liveRangeData_->inlineAsmRegDefs_;
        newbb->liveRangeData_->inlineAsmClobbers_ =
            bb.liveRangeData_->inlineAsmClobbers_;
    }
 
    return newbbn;
}

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.

                                                   {
    std::set<BasicBlockNode*> bbsToHandle;
    for (int i = 0; i < nodeCount(); ++i) {
        BasicBlockNode& bb = node(i);
        bbsToHandle.insert(&bb);
    }
 
    while (bbsToHandle.size() > 0) {
        BasicBlockNode* bbn = *bbsToHandle.begin();
        TTAProgram::BasicBlock& bb = bbn->basicBlock();
 
        for (int ii = 0; ii < bb.instructionCount(); ++ii) {
            TTAProgram::Instruction& instr = bb.instructionAt(ii);
            if (instr.hasCall() && &instr != &bb.lastInstruction()) {
                bbsToHandle.insert(splitBasicBlockAtIndex(*bbn, ii+1));
                break;
            }
            assert (irm_ != NULL);
            if (ii != 0 && irm_->hasReference(instr)) {
                bbsToHandle.insert(splitBasicBlockAtIndex(*bbn, ii));
                break;
            }
        }
        bbsToHandle.erase(bbn);
    }
}

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

n	basic block node being splitted
remainingSize	remaining 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.

                                          {
    TTAProgram::BasicBlock& bb = n.basicBlock();
    TTAProgram::BasicBlock* nbb = new TTAProgram::BasicBlock();
    BasicBlockNode* nbbn = new BasicBlockNode(*nbb);
 
    // TODO: this is slow O(n^2) loop
    for (int i = remainingSize + bb.skippedFirstInstructions();
         i < bb.instructionCount(); ) {
        TTAProgram::Instruction& ins = bb[i];
        bb.remove(ins); // this changes the indeces and is a very slow op.
        nbb->add(&ins);
    }
 
    if (n.isScheduled()) {
        nbbn->setScheduled();
    }
    // then fix cfg
    addNode(*nbbn);
    moveOutEdges(n, *nbbn);
    connectNodes(n, *nbbn, *(new ControlFlowEdge(
                                 ControlFlowEdge::CFLOW_EDGE_NORMAL,
                                 ControlFlowEdge::CFLOW_EDGE_FALLTHROUGH)));
    n.link(nbbn);
    return nbbn;
}

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.

                             {
 
    CFGStatistics* result = new CFGStatistics;
    int moveCount = 0;
    int immediateCount = 0;
    int instructionCount = 0;
    int bypassCount = 0;
    int normalBBCount = 0;
    int maxMoveCount = 0;
    int immediateCountInMax = 0;
    int instructionCountInMax = 0;
    int bypassCountInMax = 0;
    for (int i = 0; i < nodeCount(); i++) {
        if (node(i).isNormalBB()) {
            const TTAProgram::BasicBlockStatistics& stats = 
                node(i).statistics();
            moveCount += stats.moveCount();
            immediateCount += stats.immediateCount();
            instructionCount += stats.instructionCount();
            bypassCount += stats.bypassedCount();
            normalBBCount++;
            if (stats.moveCount() > maxMoveCount) {
                maxMoveCount = stats.moveCount();
                immediateCountInMax = stats.immediateCount();
                instructionCountInMax = stats.instructionCount();
                bypassCountInMax = stats.bypassedCount();
            }
        }
    }
 
    result->setMoveCount(moveCount);
    result->setImmediateCount(immediateCount);
    result->setInstructionCount(instructionCount);
    result->setBypassedCount(bypassCount);
    result->setNormalBBCount(normalBBCount);
    result->setMaxMoveCount(maxMoveCount);
    result->setMaxInstructionCount(instructionCountInMax);
    result->setMaxImmediateCount(immediateCountInMax);
    result->setMaxBypassedCount(bypassCountInMax);
    return *result;
}

References TTAProgram::BasicBlockStatistics::bypassedCount(), TTAProgram::BasicBlockStatistics::immediateCount(), TTAProgram::BasicBlockStatistics::instructionCount(), 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(), and CFGStatistics::setNormalBBCount().

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.

                                                {
 
    // make all refs point to the new copied instructions.
    for (int i = 0; i < nodeCount(); i++) {
        BasicBlockNode& bbn = node(i);
        bbn.updateReferencesFromProcToCfg(*program_);
    }
 
#if 0 // TODO: why does this irm claim to be unuser variable??
    InstructionReferenceManager& irm = program_->instructionReferenceManager();
    // procedure should not have any references.
    for (int i = 0; i < procedure_->instructionCount(); i++) {
        assert(!irm.hasReference(procedure_->instructionAtIndex(i)));
    }
#endif
}

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 PreOptimizer::handleProcedure(), SimpleIfConverter::handleProcedure(), and BBSchedulerController::handleProcedure().

Here is the call graph for this function:

Friends And Related Symbol 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:

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ InsMap

◆ InstructionAddressMap

◆ InstructionAddressVector

◆ NodeDescriptor

◆ ReturnSource

◆ ReturnSourceSet

◆ ReversedGraph

Member Enumeration Documentation

◆ RemovedJumpData

Constructor & Destructor Documentation

◆ ControlFlowGraph() [1/3]

◆ ControlFlowGraph() [2/3]

◆ ControlFlowGraph() [3/3]

◆ ~ControlFlowGraph()

Member Function Documentation

◆ addEntryExitEdge()

◆ addExit() [1/2]

◆ addExit() [2/2]

◆ addExitFromSinkNodes()

◆ alignment()

◆ allScheduledInBetween()

◆ buildFrom()

◆ buildMBBFromBB()

◆ computeLeadersFromJumpSuccessors()

◆ computeLeadersFromRefManager()

◆ computeLeadersFromRelocations()

◆ convertBBRefsToInstRefs()

◆ copyToLLVMMachineFunction()

◆ copyToProcedure()

◆ createAllBlocks()

◆ createBBEdges()

◆ createBlock()

◆ createControlFlowEdge()

◆ createJumps()

◆ deleteNodeAndRefs()

◆ detectBackEdges()

◆ directJump()

◆ entryNode()

◆ exitNode()

◆ fallThroughPredecessor()

◆ fallThruSuccessor()

◆ findJumpAddress()

◆ findLimmWrite()

◆ findLLVMTargetInstrDesc()

◆ findNextIndex()

◆ findReachableNodes()

◆ findRelJumpDistance()

◆ findUnreachableNodes()

◆ firstNormalNode()

◆ getMBB()

◆ hasFallThruPredecessor()

◆ hasIncomingExternalJumps()

◆ hasInstructionAnotherJump()

◆ hasMultipleUnconditionalSuccessors()

◆ incomingFTEdge()

◆ incomingJumpEdges()

◆ indirectJump()

◆ instructionReferenceManager()

◆ isSingleBBLoop()

◆ jumpSuccessor()

◆ jumpToBBN()

◆ mergeNodes()

◆ optimizeBBOrdering()

◆ printStatistics()

◆ procedureName()

◆ program()

◆ removeEntryExitEdge()

◆ removeJumpToTarget()

◆ removeUnreachableNodes()

◆ reversedGraph()

◆ reverseGuardOnOutEdges()