decompiler  1.0.0
Public Member Functions | Protected Member Functions | Static Protected Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
BlockGraph Class Reference

A control-flow block built out of sub-components. More...

#include <block.hh>

Inheritance diagram for BlockGraph:
FlowBlock BlockCondition BlockDoWhile BlockGoto BlockIf BlockInfLoop BlockList BlockMultiGoto BlockSwitch BlockWhileDo

Public Member Functions

void clear (void)
 Clear all component FlowBlock objects.
 
virtual ~BlockGraph (void)
 Destructor.
 
const vector< FlowBlock * > & getList (void) const
 Get the list of component FlowBlock objects.
 
int4 getSize (void) const
 Get the number of components.
 
FlowBlockgetBlock (int4 i) const
 Get the i-th component.
 
virtual block_type getType (void) const
 Get the FlowBlock type of this.
 
virtual FlowBlocksubBlock (int4 i) const
 Get the i-th component block.
 
virtual void markUnstructured (void)
 Mark target blocks of any unstructured edges.
 
virtual void markLabelBumpUp (bool bump)
 Let hierarchical blocks steal labels of their (first) components. More...
 
virtual void scopeBreak (int4 curexit, int4 curloopexit)
 Mark unstructured edges that should be breaks.
 
virtual void printTree (ostream &s, int4 level) const
 Print tree structure of any blocks owned by this. More...
 
virtual void printRaw (ostream &s) const
 Print raw instructions contained in this FlowBlock.
 
virtual void emit (PrintLanguage *lng) const
 Emit the instructions in this FlowBlock as structured code. More...
 
virtual FlowBlocknextFlowAfter (const FlowBlock *bl) const
 Get the leaf FlowBlock that will execute after the given FlowBlock. More...
 
virtual void orderSwitchCases (void) const
 Order case components of any contained BlockSwitch.
 
virtual void saveXmlBody (ostream &s) const
 Save detail about components to an XML stream.
 
virtual void restoreXmlBody (List::const_iterator &iter, List::const_iterator enditer, BlockMap &resolver)
 Restore details about this FlowBlock from an XML stream. More...
 
void restoreXml (const Element *el, const AddrSpaceManager *m)
 Restore this BlockGraph from an XML stream. More...
 
void addEdge (FlowBlock *begin, FlowBlock *end)
 Add a directed edge between component FlowBlocks. More...
 
void addLoopEdge (FlowBlock *begin, int4 outindex)
 Mark a given edge as a loop edge. More...
 
void removeEdge (FlowBlock *begin, FlowBlock *end)
 Remove an edge between component FlowBlocks. More...
 
void switchEdge (FlowBlock *in, FlowBlock *outbefore, FlowBlock *outafter)
 Move an edge from one out FlowBlock to another. More...
 
void moveOutEdge (FlowBlock *blold, int4 slot, FlowBlock *blnew)
 Move indicated out edge to a new FlowBlock. More...
 
void removeBlock (FlowBlock *bl)
 Remove a FlowBlock from this BlockGraph. More...
 
void removeFromFlow (FlowBlock *bl)
 Remove given FlowBlock preserving flow in this. More...
 
void removeFromFlowSplit (FlowBlock *bl, bool flipflow)
 Remove FlowBlock splitting flow between input and output edges. More...
 
void spliceBlock (FlowBlock *bl)
 Splice given FlowBlock together with its output. More...
 
void setStartBlock (FlowBlock *bl)
 Set the entry point FlowBlock for this graph. More...
 
FlowBlockgetStartBlock (void) const
 Get the entry point FlowBlock. More...
 
FlowBlocknewBlock (void)
 Build a new plain FlowBlock. More...
 
BlockBasicnewBlockBasic (Funcdata *fd)
 Build a new BlockBasic. More...
 
BlockCopynewBlockCopy (FlowBlock *bl)
 Build a new BlockCopy. More...
 
BlockGotonewBlockGoto (FlowBlock *bl)
 Build a new BlockGoto. More...
 
BlockMultiGotonewBlockMultiGoto (FlowBlock *bl, int4 outedge)
 Build a new BlockMultiGoto. More...
 
BlockListnewBlockList (const vector< FlowBlock * > &nodes)
 Build a new BlockList. More...
 
BlockConditionnewBlockCondition (FlowBlock *b1, FlowBlock *b2)
 Build a new BlockCondition. More...
 
BlockIfnewBlockIfGoto (FlowBlock *cond)
 Build a new BlockIfGoto. More...
 
BlockIfnewBlockIf (FlowBlock *cond, FlowBlock *tc)
 Build a new BlockIf. More...
 
BlockIfnewBlockIfElse (FlowBlock *cond, FlowBlock *tc, FlowBlock *fc)
 Build a new BlockIfElse. More...
 
BlockWhileDonewBlockWhileDo (FlowBlock *cond, FlowBlock *cl)
 Build a new BlockWhileDo. More...
 
BlockDoWhilenewBlockDoWhile (FlowBlock *condcl)
 Build a new BlockDoWhile. More...
 
BlockInfLoopnewBlockInfLoop (FlowBlock *body)
 Build a new BlockInfLoop. More...
 
BlockSwitchnewBlockSwitch (const vector< FlowBlock * > &cs)
 Build a new BlockSwitch. More...
 
void orderBlocks (void)
 
void buildCopy (const BlockGraph &graph)
 Build a copy of a BlockGraph. More...
 
void clearVisitCount (void)
 Clear the visit count in all node FlowBlocks.
 
void calcForwardDominator (const vector< FlowBlock * > &rootlist)
 Calculate forward dominators. More...
 
void buildDomTree (vector< vector< FlowBlock * > > &child) const
 Build the dominator tree. More...
 
int4 buildDomDepth (vector< int4 > &depth) const
 Calculate dominator depths. More...
 
void buildDomSubTree (vector< FlowBlock * > &res, FlowBlock *root) const
 Collect nodes from a dominator sub-tree. More...
 
void calcLoop (void)
 Calculate loop edges. More...
 
void collectReachable (vector< FlowBlock * > &res, FlowBlock *bl, bool un) const
 Collect reachable/unreachable FlowBlocks from a given start FlowBlock. More...
 
void structureLoops (vector< FlowBlock * > &rootlist)
 Label loop edges. More...
 
- Public Member Functions inherited from FlowBlock
 FlowBlock (void)
 Construct a block with no edges.
 
virtual ~FlowBlock (void)
 Destructor.
 
int4 getIndex (void) const
 Get the index assigned to this block.
 
FlowBlockgetParent (void)
 Get the parent FlowBlock of this.
 
FlowBlockgetImmedDom (void) const
 Get the immediate dominator FlowBlock.
 
FlowBlockgetCopyMap (void) const
 Get the mapped FlowBlock.
 
const FlowBlockgetParent (void) const
 Get the parent FlowBlock of this.
 
uint4 getFlags (void) const
 Get the block_flags properties.
 
virtual Address getStart (void) const
 Get the starting address of code in this FlowBlock.
 
virtual Address getStop (void) const
 Get the ending address of code in this FlowBlock.
 
virtual void printHeader (ostream &s) const
 Print a simple description of this to stream. More...
 
virtual const FlowBlockgetExitLeaf (void) const
 Get the FlowBlock to which this block exits.
 
virtual PcodeOplastOp (void) const
 Get the last PcodeOp executed by this FlowBlock.
 
virtual bool negateCondition (bool toporbottom)
 Flip the condition computed by this. More...
 
virtual bool preferComplement (Funcdata &data)
 Rearrange this hierarchy to simplify boolean expressions. More...
 
virtual FlowBlockgetSplitPoint (void)
 Get the leaf splitting block. More...
 
virtual int4 flipInPlaceTest (vector< PcodeOp * > &fliplist) const
 Test normalizing the conditional branch in this. More...
 
virtual void flipInPlaceExecute (void)
 Perform the flip to normalize conditional branch executed by this block. More...
 
virtual bool isComplex (void) const
 Is this too complex to be a condition (BlockCondition)
 
virtual void saveXmlHeader (ostream &s) const
 Save basic information as XML attributes. More...
 
virtual void restoreXmlHeader (const Element *el)
 Restore basic information for XML attributes. More...
 
void saveXmlEdges (ostream &s) const
 Save edge information to an XML stream. More...
 
void restoreXmlEdges (List::const_iterator &iter, List::const_iterator enditer, BlockMap &resolver)
 Restore edges from an XML stream. More...
 
void saveXml (ostream &s) const
 Write out this to an XML stream. More...
 
void restoreXml (const Element *el, BlockMap &resolver)
 Restore this from an XML stream. More...
 
const FlowBlocknextInFlow (void) const
 Return next block to be executed in flow. More...
 
void setVisitCount (int4 i)
 Set the number of times this block has been visited.
 
int4 getVisitCount (void) const
 Get the count of visits.
 
void setGotoBranch (int4 i)
 Mark a goto branch. More...
 
void setDefaultSwitch (int4 i)
 Mark an edge as the switch default.
 
bool isMark (void) const
 Return true if this block has been marked.
 
void setMark (void)
 Mark this block.
 
void clearMark (void)
 Clear any mark on this block.
 
void setDonothingLoop (void)
 Label this as a do nothing loop.
 
void setDead (void)
 Label this as dead.
 
bool hasSpecialLabel (void) const
 Return true if this uses a different label.
 
bool isJoined (void) const
 Return true if this is a joined basic block.
 
bool isDuplicated (void) const
 Return true if this is a duplicated block.
 
void setLoopExit (int4 i)
 Label the edge exiting this as a loop.
 
void clearLoopExit (int4 i)
 Clear the loop exit edge.
 
void setBackEdge (int4 i)
 Label the back edge of a loop.
 
bool getFlipPath (void) const
 Have out edges been flipped.
 
bool isJumpTarget (void) const
 Return true if non-fallthru jump flows into this. More...
 
FlowBlockgetFalseOut (void) const
 Get the false output FlowBlock.
 
FlowBlockgetTrueOut (void) const
 Get the true output FlowBlock.
 
FlowBlockgetOut (int4 i)
 Get the i-th output FlowBlock.
 
const FlowBlockgetOut (int4 i) const
 Get i-th output FlowBlock.
 
int4 getOutRevIndex (int4 i) const
 Get the input index of the i-th output FlowBlock.
 
FlowBlockgetIn (int4 i)
 Get the i-th input FlowBlock.
 
const FlowBlockgetIn (int4 i) const
 Get the i-th input FlowBlock.
 
int4 getInRevIndex (int4 i) const
 Get the output index of the i-th input FlowBlock.
 
const FlowBlockgetFrontLeaf (void) const
 Get the first leaf FlowBlock. More...
 
FlowBlockgetFrontLeaf (void)
 Get the first leaf FlowBlock. More...
 
int4 calcDepth (const FlowBlock *leaf) const
 Get the depth of the given component FlowBlock. More...
 
int4 sizeOut (void) const
 Get the number of out edges.
 
int4 sizeIn (void) const
 Get the number of in edges.
 
bool hasLoopIn (void) const
 Is there a looping edge coming into this block. More...
 
bool hasLoopOut (void) const
 Is there a looping edge going out of this block. More...
 
bool isLoopIn (int4 i) const
 Is the i-th incoming edge a loop edge.
 
bool isLoopOut (int4 i) const
 Is the i-th outgoing edge a loop edge.
 
int4 getInIndex (const FlowBlock *bl) const
 Get the incoming edge index for the given FlowBlock. More...
 
int4 getOutIndex (const FlowBlock *bl) const
 Get the outgoing edge index for the given FlowBlock. More...
 
bool isDefaultBranch (int4 i) const
 Is the i-th out edge the switch default edge.
 
bool isLabelBumpUp (void) const
 Are labels for this printed by the parent.
 
bool isUnstructuredTarget (void) const
 Is this the target of an unstructured goto.
 
bool isInteriorGotoTarget (void) const
 Is there an unstructured goto to this block's interior.
 
bool hasInteriorGoto (void) const
 Is there an unstructured goto out of this block's interior.
 
bool isEntryPoint (void) const
 Is the entry point of the function.
 
bool isSwitchOut (void) const
 Is this a switch block.
 
bool isDonothingLoop (void) const
 Is this a do nothing block.
 
bool isDead (void) const
 Is this block dead.
 
bool isTreeEdgeIn (int4 i) const
 Is the i-th incoming edge part of the spanning tree.
 
bool isBackEdgeIn (int4 i) const
 Is the i-th incoming edge a back edge.
 
bool isBackEdgeOut (int4 i) const
 Is the i-th outgoing edge a back edge.
 
bool isIrreducibleOut (int4 i) const
 Is the i-th outgoing edge an irreducible edge.
 
bool isIrreducibleIn (int4 i) const
 Is the i-th incoming edge an irreducible edge.
 
bool isDecisionOut (int4 i) const
 Can this and the i-th output be merged into a BlockIf or BlockList.
 
bool isDecisionIn (int4 i) const
 Can this and the i-th input be merged into a BlockIf or BlockList.
 
bool isLoopDAGOut (int4 i) const
 Is the i-th outgoing edge part of the DAG sub-graph.
 
bool isLoopDAGIn (int4 i) const
 Is the i-th incoming edge part of the DAG sub-graph.
 
bool isGotoIn (int4 i) const
 Is the i-th incoming edge unstructured.
 
bool isGotoOut (int4 i) const
 Is the i-th outgoing edge unstructured.
 
JumpTablegetJumptable (void) const
 Get the JumpTable associated this block. More...
 

Protected Member Functions

void swapBlocks (int4 i, int4 j)
 Swap the positions two component FlowBlocks. More...
 
- Protected Member Functions inherited from FlowBlock
void setFlag (uint4 fl)
 Set a boolean property.
 
void clearFlag (uint4 fl)
 Clear a boolean property.
 

Static Protected Member Functions

static void markCopyBlock (FlowBlock *bl, uint4 fl)
 Set properties on the first leaf FlowBlock. More...
 

Private Member Functions

void addBlock (FlowBlock *bl)
 Add a component FlowBlock. More...
 
void forceOutputNum (int4 i)
 Force number of outputs. More...
 
void selfIdentify (void)
 Inherit our edges from the edges of our components. More...
 
void identifyInternal (BlockGraph *ident, const vector< FlowBlock * > &nodes)
 Move nodes from this into a new BlockGraph. More...
 
void clearEdgeFlags (uint4 flags)
 Clear a set of properties from all edges in the graph. More...
 
void findSpanningTree (vector< FlowBlock * > &preorder, vector< FlowBlock * > &rootlist)
 Find a spanning tree (skipping irreducible edges). More...
 
bool findIrreducible (const vector< FlowBlock * > &preorder, int4 &irreduciblecount)
 Identify irreducible edges. More...
 
void forceFalseEdge (const FlowBlock *out0)
 Force the false out edge to go to the given FlowBlock. More...
 

Static Private Member Functions

static FlowBlockcreateVirtualRoot (const vector< FlowBlock * > &rootlist)
 Create a single root block. More...
 

Private Attributes

vector< FlowBlock * > list
 List of FlowBlock components within this super-block.
 

Additional Inherited Members

- Public Types inherited from FlowBlock
enum  block_type {
  t_plain, t_basic, t_graph, t_copy,
  t_goto, t_multigoto, t_ls, t_condition,
  t_if, t_whiledo, t_dowhile, t_switch,
  t_infloop
}
 The possible block types.
 
enum  block_flags {
  f_goto_goto = 1, f_break_goto = 2, f_continue_goto = 4, f_switch_out = 0x10,
  f_unstructured_targ = 0x20, f_mark = 0x80, f_mark2 = 0x100, f_entry_point = 0x200,
  f_interior_gotoout = 0x400, f_interior_gotoin = 0x800, f_label_bumpup = 0x1000, f_donothing_loop = 0x2000,
  f_dead = 0x4000, f_whiledo_overflow = 0x8000, f_flip_path = 0x10000, f_joined_block = 0x20000,
  f_duplicate_block = 0x40000
}
 Boolean properties of blocks. More...
 
enum  edge_flags {
  f_goto_edge = 1, f_loop_edge = 2, f_defaultswitch_edge = 4, f_irreducible = 8,
  f_tree_edge = 0x10, f_forward_edge = 0x20, f_cross_edge = 0x40, f_back_edge = 0x80,
  f_loop_exit_edge = 0x100
}
 Boolean properties on edges. More...
 
- Static Public Member Functions inherited from FlowBlock
static block_type nameToType (const string &name)
 Get the block_type associated with a name string. More...
 
static string typeToName (block_type bt)
 Get the name string associated with a block_type. More...
 
static bool compareBlockIndex (const FlowBlock *bl1, const FlowBlock *bl2)
 Compare FlowBlock by index. More...
 
static bool compareFinalOrder (const FlowBlock *bl1, const FlowBlock *bl2)
 Final FlowBlock comparison. More...
 
static FlowBlockfindCommonBlock (FlowBlock *bl1, FlowBlock *bl2)
 Find the common dominator of two FlowBlocks. More...
 

Detailed Description

A control-flow block built out of sub-components.

This is the core class for building a hierarchy of control-flow blocks. A set of control-flow blocks can be grouped together and viewed as a single block, with its own input and output blocks. All the code structuring elements (BlockList, BlockIf, BlockWhileDo, etc.) derive from this.

Member Function Documentation

◆ addBlock()

void BlockGraph::addBlock ( FlowBlock bl)
private

Add a component FlowBlock.

Add the given FlowBlock to the list and make this the parent Update index so that it has the minimum over all components

Parameters
blis the given FlowBlock

References FlowBlock::index, list, and FlowBlock::parent.

Referenced by identifyInternal(), newBlock(), newBlockBasic(), newBlockCondition(), newBlockCopy(), newBlockDoWhile(), newBlockGoto(), newBlockIf(), newBlockIfElse(), newBlockIfGoto(), newBlockInfLoop(), newBlockList(), newBlockMultiGoto(), newBlockSwitch(), newBlockWhileDo(), and restoreXmlBody().

◆ addEdge()

void BlockGraph::addEdge ( FlowBlock begin,
FlowBlock end 
)

Add a directed edge between component FlowBlocks.

Parameters
beginis the start FlowBlock
endis the stop FlowBlock

References FlowBlock::addInEdge(), and FlowBlock::parent.

Referenced by FlowInfo::connectBasic(), FlowInfo::generateBlocks(), Funcdata::nodeJoinCreateBlock(), and Funcdata::nodeSplitBlockEdge().

◆ addLoopEdge()

void BlockGraph::addLoopEdge ( FlowBlock begin,
int4  outindex 
)

Mark a given edge as a loop edge.

Parameters
beginis a given component FlowBlock
outindexis the index of the out edge to mark as a loop

References FlowBlock::f_loop_edge, FlowBlock::parent, and FlowBlock::setOutEdgeFlag().

Referenced by calcLoop().

◆ buildCopy()

void BlockGraph::buildCopy ( const BlockGraph graph)

Build a copy of a BlockGraph.

Construct a copy of the given BlockGraph in this. The nodes of the copy will be official BlockCopy objects which will contain a reference to their corresponding FlowBlock in the given graph. All edges will be duplicated.

Parameters
graphis the given BlockGraph to copy

References list, and newBlockCopy().

Referenced by StructureGraph::rawAction().

◆ buildDomDepth()

int4 BlockGraph::buildDomDepth ( vector< int4 > &  depth) const

Calculate dominator depths.

Associate every FlowBlock node in this graph with its depth in the dominator tree. The dominator root has depth 1, the nodes it immediately dominates have depth 2, etc.

Parameters
depthis array that will be populated with depths
Returns
the maximum depth across all nodes

References FlowBlock::getIndex(), and list.

◆ buildDomSubTree()

void BlockGraph::buildDomSubTree ( vector< FlowBlock * > &  res,
FlowBlock root 
) const

Collect nodes from a dominator sub-tree.

Collect all nodes in the dominator sub-tree starting at a given root FlowBlock. We assume blocks in are reverse post order.

Parameters
reswill hold the list of nodes in the sub-tree
rootis the given root FlowBlock

References FlowBlock::getImmedDom(), FlowBlock::getIndex(), and list.

◆ buildDomTree()

void BlockGraph::buildDomTree ( vector< vector< FlowBlock * > > &  child) const

Build the dominator tree.

Associate dominator children with each node via a list (of lists) indexed by the FlowBlock index.

Parameters
childis the initially empty list of lists

References FlowBlock::immed_dom, FlowBlock::index, and list.

◆ calcForwardDominator()

void BlockGraph::calcForwardDominator ( const vector< FlowBlock * > &  rootlist)

Calculate forward dominators.

Calculate the immediate dominator for each FlowBlock node in this BlockGraph, for forward control-flow. The algorithm must be provided a list of entry points for the graph. We assume the blocks are in reverse post-order and this is reflected in the index field. Using an algorithm by Cooper, Harvey, and Kennedy. Softw. Pract. Exper. 2001; 4: 1-10

Parameters
rootlistis the list of entry point FlowBlocks

References createVirtualRoot(), FlowBlock::getIn(), FlowBlock::getOut(), FlowBlock::immed_dom, FlowBlock::index, list, FlowBlock::removeOutEdge(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by StructureGraph::rawAction(), and Funcdata::structureReset().

◆ calcLoop()

void BlockGraph::calcLoop ( void  )

Calculate loop edges.

This algorithm identifies a set of edges such that, if the edges are removed, the remaining graph has NO directed cycles The algorithm works as follows: Starting from the start block, do a depth first search through the "out" edges of the block. If the outblock is already on the current path from root to node, we have found a cycle, we add the last edge to the list and continue pretending that edge didn't exist. If the outblock is not on the current path but has been visited before, we can truncate the search. This is now only applied as a failsafe if the graph has irreducible edges.

References addLoopEdge(), FlowBlock::clearFlag(), FlowBlock::f_mark, FlowBlock::f_mark2, FlowBlock::flags, FlowBlock::getOut(), FlowBlock::isLoopOut(), list, FlowBlock::setFlag(), and FlowBlock::sizeOut().

Referenced by structureLoops().

◆ clearEdgeFlags()

void BlockGraph::clearEdgeFlags ( uint4  flags)
private

Clear a set of properties from all edges in the graph.

Parameters
flagsis the set of boolean properties

References FlowBlock::flags, FlowBlock::intothis, list, and FlowBlock::outofthis.

Referenced by findSpanningTree(), and structureLoops().

◆ collectReachable()

void BlockGraph::collectReachable ( vector< FlowBlock * > &  res,
FlowBlock bl,
bool  un 
) const

Collect reachable/unreachable FlowBlocks from a given start FlowBlock.

If the boolean un is true, collect unreachable blocks. Otherwise collect reachable blocks.

Parameters
reswill hold the reachable or unreachable FlowBlocks
blis the starting FlowBlock
untoggles reachable,unreachable

References FlowBlock::clearMark(), FlowBlock::getOut(), FlowBlock::isMark(), list, FlowBlock::setMark(), and FlowBlock::sizeOut().

Referenced by Funcdata::removeUnreachableBlocks().

◆ createVirtualRoot()

FlowBlock * BlockGraph::createVirtualRoot ( const vector< FlowBlock * > &  rootlist)
staticprivate

Create a single root block.

Some algorithms need a graph with a single entry node. Given multiple entry points, this routine creates an artificial root with no in edges and an out edge to each of the real entry points. The resulting root FlowBlock isn't owned by any BlockGraph, and the caller is responsible for freeing it.

Parameters
rootlistis the given set of entry point FlowBlocks
Returns
the new artificial root FlowBlock

References FlowBlock::addInEdge(), and FlowBlock::FlowBlock().

Referenced by calcForwardDominator().

◆ emit()

virtual void BlockGraph::emit ( PrintLanguage lng) const
inlinevirtual

Emit the instructions in this FlowBlock as structured code.

This is the main entry point, at the control-flow level, for printing structured code.

Parameters
lngis the PrintLanguage that provides details of the high-level language being printed

Reimplemented from FlowBlock.

Reimplemented in BlockSwitch, BlockInfLoop, BlockDoWhile, BlockWhileDo, BlockIf, BlockCondition, BlockList, BlockMultiGoto, and BlockGoto.

References PrintLanguage::emitBlockGraph().

◆ findIrreducible()

bool BlockGraph::findIrreducible ( const vector< FlowBlock * > &  preorder,
int4 &  irreduciblecount 
)
private

Identify irreducible edges.

Assuming the spanning tree has been properly labeled using findSpanningTree(), test for and label and irreducible edges (the test ignores any edges already labeled as irreducible). Return true if the spanning tree needs to be rebuilt, because one of the tree edges is irreducible. Original algorithm due to Tarjan.

Parameters
preorderis the list of FlowBlocks in pre-order
irreduciblecountwill hold the number of irreducible edges
Returns
true if the spanning tree needs to be rebuilt

References FlowBlock::clearMark(), FlowBlock::clearOutEdgeFlag(), FlowBlock::copymap, FlowBlock::f_cross_edge, FlowBlock::f_forward_edge, FlowBlock::f_irreducible, FlowBlock::getIn(), FlowBlock::getInRevIndex(), FlowBlock::isBackEdgeIn(), FlowBlock::isIrreducibleIn(), FlowBlock::isMark(), FlowBlock::isTreeEdgeIn(), FlowBlock::numdesc, FlowBlock::setMark(), FlowBlock::setOutEdgeFlag(), FlowBlock::sizeIn(), and FlowBlock::visitcount.

Referenced by structureLoops().

◆ findSpanningTree()

void BlockGraph::findSpanningTree ( vector< FlowBlock * > &  preorder,
vector< FlowBlock * > &  rootlist 
)
private

Find a spanning tree (skipping irreducible edges).

  • Label pre and reverse-post orderings, tree, forward, cross, and back edges.
  • Calculate number of descendants.
  • Put the blocks of the graph in reverse post order.
  • Return an array of all nodes in pre-order.
  • If the graph does not have a real root, create one and return it, otherwise return null.

Algorithm originally due to Tarjan. The first block is the entry block, and should remain the first block

Parameters
preorderwill hold the list of FlowBlock components in pre-order
rootlistwill hold the list of entry points

References clearEdgeFlags(), FlowBlock::copymap, FlowBlock::f_back_edge, FlowBlock::f_cross_edge, FlowBlock::f_forward_edge, FlowBlock::f_loop_edge, FlowBlock::f_tree_edge, FlowBlock::getOut(), FlowBlock::index, FlowBlock::isIrreducibleOut(), list, FlowBlock::numdesc, FlowBlock::setOutEdgeFlag(), FlowBlock::sizeIn(), FlowBlock::sizeOut(), and FlowBlock::visitcount.

Referenced by structureLoops().

◆ forceFalseEdge()

void BlockGraph::forceFalseEdge ( const FlowBlock out0)
private

Force the false out edge to go to the given FlowBlock.

Make sure this has exactly 2 out edges and the first edge flows to the given FlowBlock. Swap the edges if necessary. Throw an exception if this is not possible.

Parameters
out0is the given FlowBlock

References FlowBlock::getParent(), FlowBlock::outofthis, FlowBlock::sizeOut(), and FlowBlock::swapEdges().

◆ forceOutputNum()

void BlockGraph::forceOutputNum ( int4  i)
private

Force number of outputs.

Force this FlowBlock to have the indicated number of outputs. Create edges back into itself if necessary.

Parameters
iis the number of out edges to force

References FlowBlock::addInEdge(), FlowBlock::f_back_edge, FlowBlock::f_loop_edge, and FlowBlock::sizeOut().

◆ getStartBlock()

FlowBlock * BlockGraph::getStartBlock ( void  ) const

Get the entry point FlowBlock.

Throw an exception if no entry point is registered

Returns
the entry point FlowBlock

References FlowBlock::f_entry_point, and list.

Referenced by Heritage::concatPieces(), and Heritage::splitPieces().

◆ identifyInternal()

void BlockGraph::identifyInternal ( BlockGraph ident,
const vector< FlowBlock * > &  nodes 
)
private

Move nodes from this into a new BlockGraph.

This does most of the work of collapsing a set of components in this into a single node. The components are removed from this, put in the new FlowBlock and adjusts edges. The new FlowBlock must be added back into this.

Parameters
identis the new FlowBlock
nodesis the list component FlowBlocks to move

References addBlock(), FlowBlock::f_interior_gotoin, FlowBlock::f_interior_gotoout, list, and selfIdentify().

Referenced by newBlockCondition(), newBlockDoWhile(), newBlockGoto(), newBlockIf(), newBlockIfElse(), newBlockIfGoto(), newBlockInfLoop(), newBlockList(), newBlockMultiGoto(), newBlockSwitch(), and newBlockWhileDo().

◆ markCopyBlock()

void BlockGraph::markCopyBlock ( FlowBlock bl,
uint4  fl 
)
staticprotected

Set properties on the first leaf FlowBlock.

For the given BlockGraph find the first component leaf FlowBlock and set its properties

Parameters
blis the given BlockGraph
flis the property to set

References FlowBlock::flags, and FlowBlock::getFrontLeaf().

Referenced by BlockGoto::markUnstructured(), BlockIf::markUnstructured(), and BlockSwitch::markUnstructured().

◆ markLabelBumpUp()

void BlockGraph::markLabelBumpUp ( bool  bump)
virtual

Let hierarchical blocks steal labels of their (first) components.

Parameters
bumpif true, mark that labels for this block are printed by somebody higher in hierarchy

Reimplemented from FlowBlock.

Reimplemented in BlockInfLoop, BlockDoWhile, and BlockWhileDo.

References list, and FlowBlock::markLabelBumpUp().

Referenced by BlockWhileDo::markLabelBumpUp(), BlockDoWhile::markLabelBumpUp(), and BlockInfLoop::markLabelBumpUp().

◆ moveOutEdge()

void BlockGraph::moveOutEdge ( FlowBlock blold,
int4  slot,
FlowBlock blnew 
)

Move indicated out edge to a new FlowBlock.

Given an edge specified by its input FlowBlock, replace that input with new FlowBlock.

Parameters
bloldis the original input FlowBlock
slotis the index of the out edge of blold
blnewis the FlowBlock that will become the input to the edge

References FlowBlock::getOut(), FlowBlock::getOutRevIndex(), FlowBlock::parent, and FlowBlock::replaceInEdge().

Referenced by Funcdata::nodeJoinCreateBlock(), Funcdata::pushBranch(), and spliceBlock().

◆ newBlock()

FlowBlock * BlockGraph::newBlock ( void  )

Build a new plain FlowBlock.

Add the new FlowBlock to this

Returns
the new FlowBlock

References addBlock(), and FlowBlock::FlowBlock().

◆ newBlockBasic()

BlockBasic * BlockGraph::newBlockBasic ( Funcdata fd)

Build a new BlockBasic.

Add the new BlockBasic to this

Parameters
fdis the function underlying the basic block
Returns
the new BlockBasic

References addBlock().

Referenced by FlowInfo::generateBlocks(), Funcdata::nodeJoinCreateBlock(), Funcdata::nodeSplitBlockEdge(), and FlowInfo::splitBasic().

◆ newBlockCondition()

BlockCondition * BlockGraph::newBlockCondition ( FlowBlock b1,
FlowBlock b2 
)

Build a new BlockCondition.

Add the new BlockCondition to this, collapsing its pieces into it.

Parameters
b1is the first FlowBlock piece
b2is the second FlowBlock piece
Returns
the new BlockCondition

References addBlock(), CPUI_INT_AND, CPUI_INT_OR, FlowBlock::getFalseOut(), FlowBlock::getOut(), and identifyInternal().

Referenced by CollapseStructure::ruleBlockOr().

◆ newBlockCopy()

BlockCopy * BlockGraph::newBlockCopy ( FlowBlock bl)

Build a new BlockCopy.

Add the new BlockCopy to this

Parameters
blis the FlowBlock underlying the copy
Returns
the new BlockCopy

References addBlock(), FlowBlock::f_switch_out, FlowBlock::flags, FlowBlock::immed_dom, FlowBlock::index, FlowBlock::intothis, FlowBlock::numdesc, and FlowBlock::outofthis.

Referenced by buildCopy().

◆ newBlockDoWhile()

BlockDoWhile * BlockGraph::newBlockDoWhile ( FlowBlock condcl)

Build a new BlockDoWhile.

Add the new BlockDoWhile to this, collapsing the condition clause FlowBlock into it.

Parameters
condclis the condition clause FlowBlock
Returns
the new BlockDoWhile

References addBlock(), and identifyInternal().

Referenced by CollapseStructure::ruleBlockDoWhile().

◆ newBlockGoto()

BlockGoto * BlockGraph::newBlockGoto ( FlowBlock bl)

Build a new BlockGoto.

Add the new BlockGoto to this, incorporating the given FlowBlock

Parameters
blis the given FlowBlock whose outgoing edge is to be marked as a goto
Returns
the new BlockGoto

References addBlock(), FlowBlock::getOut(), identifyInternal(), and removeEdge().

Referenced by CollapseStructure::ruleBlockGoto().

◆ newBlockIf()

BlockIf * BlockGraph::newBlockIf ( FlowBlock cond,
FlowBlock tc 
)

Build a new BlockIf.

Add the new BlockIf to this, collapsing the condition and body FlowBlocks into it.

Parameters
condis the condition FlowBlock
tcis the body FlowBlock
Returns
the new BlockIf

References addBlock(), and identifyInternal().

Referenced by CollapseStructure::ruleBlockIfNoExit(), and CollapseStructure::ruleBlockProperIf().

◆ newBlockIfElse()

BlockIf * BlockGraph::newBlockIfElse ( FlowBlock cond,
FlowBlock tc,
FlowBlock fc 
)

Build a new BlockIfElse.

Add the new BlockIfElse to this, collapsing the condition, true clause, and false clause into it.

Parameters
condis the condition FlowBlock
tcis the true clause FlowBlock
fcis the false clause FlowBlock
Returns
the new BlockIf

References addBlock(), and identifyInternal().

Referenced by CollapseStructure::ruleBlockIfElse().

◆ newBlockIfGoto()

BlockIf * BlockGraph::newBlockIfGoto ( FlowBlock cond)

Build a new BlockIfGoto.

Add the new BlockIfGoto to this, collapsing the given condition FlowBlock into it.

Parameters
condis the given condition FlowBlock
Returns
the new BlockIfGoto

References addBlock(), FlowBlock::getOut(), FlowBlock::getTrueOut(), identifyInternal(), FlowBlock::isGotoOut(), removeEdge(), and BlockIf::setGotoTarget().

Referenced by CollapseStructure::ruleBlockGoto().

◆ newBlockInfLoop()

BlockInfLoop * BlockGraph::newBlockInfLoop ( FlowBlock body)

Build a new BlockInfLoop.

Add the new BlockInfLoop to this, collapsing the body FlowBlock into it.

Parameters
bodyis the body FlowBlock
Returns
the new BlockInfLoop

References addBlock(), and identifyInternal().

Referenced by CollapseStructure::ruleBlockInfLoop().

◆ newBlockList()

BlockList * BlockGraph::newBlockList ( const vector< FlowBlock * > &  nodes)

Build a new BlockList.

Add the new BlockList to this, collapsing the given FlowBlock components into it.

Parameters
nodesis the given set of FlowBlocks components
Returns
the new BlockList

References addBlock(), identifyInternal(), and FlowBlock::sizeOut().

Referenced by CollapseStructure::ruleBlockCat().

◆ newBlockMultiGoto()

BlockMultiGoto * BlockGraph::newBlockMultiGoto ( FlowBlock bl,
int4  outedge 
)

Build a new BlockMultiGoto.

The given FlowBlock may already be a BlockMultiGoto, otherwise we add the new BlockMultiGoto to this.

Parameters
blis the given FlowBlock with the new goto edge
outedgeis the index of the outgoing edge to make into a goto
Returns
the (possibly new) BlockMultiGoto

References addBlock(), BlockMultiGoto::addEdge(), FlowBlock::getOut(), FlowBlock::getType(), identifyInternal(), FlowBlock::isDefaultBranch(), removeEdge(), and BlockMultiGoto::setDefaultGoto().

Referenced by CollapseStructure::ruleBlockGoto().

◆ newBlockSwitch()

BlockSwitch * BlockGraph::newBlockSwitch ( const vector< FlowBlock * > &  cs)

Build a new BlockSwitch.

Add the new BlockSwitch to this, collapsing all the case FlowBlocks into it.

Parameters
csis the list of case FlowBlocks
Returns
the new BlockSwitch

References addBlock(), FlowBlock::clearFlag(), FlowBlock::f_switch_out, FlowBlock::getExitLeaf(), FlowBlock::getType(), BlockSwitch::grabCaseBasic(), identifyInternal(), and FlowBlock::subBlock().

Referenced by CollapseStructure::ruleBlockSwitch().

◆ newBlockWhileDo()

BlockWhileDo * BlockGraph::newBlockWhileDo ( FlowBlock cond,
FlowBlock cl 
)

Build a new BlockWhileDo.

Add the new BlockWhileDo to this, collapsing the condition and clause into it.

Parameters
condis the condition FlowBlock
clis the clause FlowBlock
Returns
the new BlockWhileDo

References addBlock(), and identifyInternal().

Referenced by CollapseStructure::ruleBlockWhileDo().

◆ nextFlowAfter()

FlowBlock * BlockGraph::nextFlowAfter ( const FlowBlock bl) const
virtual

Get the leaf FlowBlock that will execute after the given FlowBlock.

Within the hierarchy of this FlowBlock, assume the given FlowBlock will fall-thru in its execution at some point. Return the first leaf block (BlockBasic or BlockCopy) that will execute after the given FlowBlock completes, assuming this is a unique block.

Parameters
blis the given FlowBlock
Returns
the next FlowBlock to execute or NULL

Reimplemented from FlowBlock.

Reimplemented in BlockSwitch, BlockInfLoop, BlockDoWhile, BlockWhileDo, BlockIf, BlockCondition, BlockMultiGoto, and BlockGoto.

References FlowBlock::getFrontLeaf(), FlowBlock::getParent(), list, and FlowBlock::nextFlowAfter().

◆ orderBlocks()

void BlockGraph::orderBlocks ( void  )
inline

< Sort blocks using the final ordering

References FlowBlock::compareFinalOrder(), and list.

Referenced by ActionFinalStructure::apply(), and StructureGraph::rawAction().

◆ printTree()

void BlockGraph::printTree ( ostream &  s,
int4  level 
) const
virtual

Print tree structure of any blocks owned by this.

Recursively print out the hierarchical structure of this FlowBlock.

Parameters
sis the output stream
levelis the current level of indentation

Reimplemented from FlowBlock.

References list, and FlowBlock::printTree().

Referenced by Funcdata::printBlockTree().

◆ removeBlock()

void BlockGraph::removeBlock ( FlowBlock bl)

Remove a FlowBlock from this BlockGraph.

The indicated block is pulled out of the component list and deleted. Any edges between it and the rest of the BlockGraph are simply removed.

Parameters
blis the indicated block

References FlowBlock::getIn(), FlowBlock::getOut(), list, FlowBlock::parent, removeEdge(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by Funcdata::blockRemoveInternal(), Funcdata::removeFromFlowSplit(), and spliceBlock().

◆ removeEdge()

void BlockGraph::removeEdge ( FlowBlock begin,
FlowBlock end 
)

Remove an edge between component FlowBlocks.

The edge must already exist

Parameters
beginis the incoming FlowBlock of the edge
endis the outgoing FlowBlock

References FlowBlock::intothis, FlowBlock::parent, and FlowBlock::removeInEdge().

Referenced by Funcdata::branchRemoveInternal(), newBlockGoto(), newBlockIfGoto(), newBlockMultiGoto(), Funcdata::nodeJoinCreateBlock(), and removeBlock().

◆ removeFromFlow()

void BlockGraph::removeFromFlow ( FlowBlock bl)

Remove given FlowBlock preserving flow in this.

This should be applied only if the given FlowBlock has 0 or 1 outputs. If there is an output FlowBlock, all incoming edges to the given FlowBlock are moved so they flow into the output FlowBlock, then all remaining edges into or out of the given FlowBlock are removed. The given FlowBlock is not removed from this. This routine doesn't preserve loopedge information

Parameters
blis the given FlowBlock component

References FlowBlock::getIn(), FlowBlock::getOut(), FlowBlock::intothis, FlowBlock::parent, FlowBlock::removeOutEdge(), FlowBlock::replaceOutEdge(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by Funcdata::blockRemoveInternal().

◆ removeFromFlowSplit()

void BlockGraph::removeFromFlowSplit ( FlowBlock bl,
bool  flipflow 
)

Remove FlowBlock splitting flow between input and output edges.

Remove the given FlowBlock from the flow of the graph. It must have 2 inputs, and 2 outputs. The edges will be remapped so that

  • In(0) -> Out(0) and
  • In(1) -> Out(1)

Or if flipflow is true:

  • In(0) -> Out(1)
  • In(1) -> Out(0)
    Parameters
    blis the given FlowBlock
    flipflowindicates how the edges are remapped

References FlowBlock::parent, FlowBlock::replaceEdgesThru(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by Funcdata::removeFromFlowSplit().

◆ restoreXml()

void BlockGraph::restoreXml ( const Element el,
const AddrSpaceManager m 
)

Restore this BlockGraph from an XML stream.

This is currently just a wrapper around the FlowBlock::restoreXml() that sets of the BlockMap resolver

Parameters
elis the root <block> tag
mis the address space manager

References FlowBlock::restoreXml().

Referenced by StructureGraph::loadParameters().

◆ restoreXmlBody()

void BlockGraph::restoreXmlBody ( List::const_iterator &  iter,
List::const_iterator  enditer,
BlockMap resolver 
)
virtual

Restore details about this FlowBlock from an XML stream.

Parameters
iteris an iterator to XML elements containing component tags etc.
enditermarks the end of the XML tags
resolveris used to recover FlowBlock objects based on XML references

Reimplemented from FlowBlock.

References addBlock(), BlockMap::createBlock(), FlowBlock::index, FlowBlock::restoreXml(), FlowBlock::restoreXmlBody(), and BlockMap::sortList().

◆ selfIdentify()

void BlockGraph::selfIdentify ( void  )
private

Inherit our edges from the edges of our components.

Examine the set of components and their incoming and outgoing edges. If both ends of the edge are not within the set, then this block inherits the edge. A formal BlockEdge is added between this and the FlowBlock outside the set. The edges are deduplicated.

References FlowBlock::dedup(), FlowBlock::f_switch_out, FlowBlock::intothis, FlowBlock::isSwitchOut(), list, FlowBlock::outofthis, FlowBlock::parent, FlowBlock::replaceInEdge(), FlowBlock::replaceOutEdge(), and FlowBlock::setFlag().

Referenced by identifyInternal().

◆ setStartBlock()

void BlockGraph::setStartBlock ( FlowBlock bl)

Set the entry point FlowBlock for this graph.

The component list is reordered to make the given FlowBlock first. The f_entry_point property is updated.

Parameters
blis the given FlowBlock to make the entry point

References FlowBlock::f_entry_point, FlowBlock::flags, list, and FlowBlock::parent.

Referenced by FlowInfo::generateBlocks(), and FlowInfo::splitBasic().

◆ spliceBlock()

void BlockGraph::spliceBlock ( FlowBlock bl)

Splice given FlowBlock together with its output.

The given FlowBlock must have exactly one output. That output must have exactly one input. The output FlowBlock is removed and any outgoing edges it has become outgoing edge of the given FlowBlock. The output FlowBlock is permanently removed. It is viewed as being spliced together with the given FlowBlock.

Parameters
blis the given FlowBlock

References FlowBlock::f_entry_point, FlowBlock::f_switch_out, FlowBlock::f_unstructured_targ, FlowBlock::flags, FlowBlock::getOut(), moveOutEdge(), removeBlock(), FlowBlock::removeOutEdge(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by Funcdata::spliceBlockBasic().

◆ structureLoops()

void BlockGraph::structureLoops ( vector< FlowBlock * > &  rootlist)

Label loop edges.

  • Find irreducible edges
  • Find a spanning tree
  • Set FlowBlock indices in reverse-post order
  • Label tree-edges, forward-edges, cross-edges, and back-edges
    Parameters
    rootlistwill contain the entry points for the graph

References calcLoop(), clearEdgeFlags(), FlowBlock::f_back_edge, FlowBlock::f_cross_edge, FlowBlock::f_forward_edge, FlowBlock::f_loop_edge, FlowBlock::f_tree_edge, findIrreducible(), and findSpanningTree().

Referenced by StructureGraph::rawAction(), and Funcdata::structureReset().

◆ swapBlocks()

void BlockGraph::swapBlocks ( int4  i,
int4  j 
)
protected

Swap the positions two component FlowBlocks.

Parameters
iis the position of the first FlowBlock to swap
jis the position of the second

References list.

Referenced by BlockIf::preferComplement().

◆ switchEdge()

void BlockGraph::switchEdge ( FlowBlock in,
FlowBlock outbefore,
FlowBlock outafter 
)

Move an edge from one out FlowBlock to another.

The edge from in to outbefore must already exist. It will get removed and replaced with an edge from in to outafter. The new edge index will be the same as the removed edge, and all other edge ordering will be preserved.

Parameters
inis the input FlowBlock
outbeforeis the initial output FlowBlock
outafteris the new output FlowBlock

References FlowBlock::outofthis, and FlowBlock::replaceOutEdge().

Referenced by Funcdata::nodeSplitBlockEdge(), and Funcdata::switchEdge().


The documentation for this class was generated from the following files: