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
ghidra::BlockGraph Class Reference

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

#include <block.hh>

Inheritance diagram for ghidra::BlockGraph:
ghidra::FlowBlock ghidra::BlockCondition ghidra::BlockDoWhile ghidra::BlockGoto ghidra::BlockIf ghidra::BlockInfLoop ghidra::BlockList ghidra::BlockMultiGoto ghidra::BlockSwitch ghidra::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 finalTransform (Funcdata &data)
 Do any structure driven final transforms.
 
virtual void finalizePrinting (Funcdata &data) const
 Make any final configurations necessary to print the block.
 
virtual void encodeBody (Encoder &encoder) const
 Encode detail about components to a stream.
 
virtual void decodeBody (Decoder &decoder)
 Restore details about this FlowBlock from an element stream. More...
 
void decode (Decoder &decoder)
 Decode this BlockGraph from a 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, bool hasExit)
 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 ghidra::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 encodeHeader (Encoder &encoder) const
 Encode basic information as attributes. More...
 
virtual void decodeHeader (Decoder &decoder)
 Decode basic information from element attributes. More...
 
void encodeEdges (Encoder &encoder) const
 Encode edge information to a stream. More...
 
void decodeEdges (Decoder &decoder, BlockMap &resolver)
 Restore edges from an encoded stream. More...
 
void encode (Encoder &encoder) const
 Encode this to a stream. More...
 
void decode (Decoder &decoder, BlockMap &resolver)
 Decode this from a 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 pos)
 Mark an edge as the switch default. More...
 
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...
 
bool dominates (const FlowBlock *subBlock) const
 Does this block dominate the given block. More...
 
bool restrictedByConditional (const FlowBlock *cond) const
 Check if the condition from the given block holds for this block. 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 ghidra::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 fl)
 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 ghidra::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 ghidra::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...
 
static FlowBlockfindCommonBlock (const vector< FlowBlock *> &blockSet)
 Find common dominator of multiple 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 ghidra::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 ghidra::FlowBlock::index, and ghidra::FlowBlock::parent.

Referenced by identifyInternal().

◆ addEdge()

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

◆ addLoopEdge()

void ghidra::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 ghidra::FlowBlock::parent, and ghidra::FlowBlock::setOutEdgeFlag().

◆ buildCopy()

void ghidra::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.

Referenced by ghidra::ActionBlockStructure::apply(), ghidra::IfcStructureBlocks::execute(), and ghidra::StructureGraph::rawAction().

◆ buildDomDepth()

int4 ghidra::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 ghidra::FlowBlock::getIndex(), and ghidra::FlowBlock::immed_dom.

◆ buildDomSubTree()

void ghidra::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 ghidra::FlowBlock::getImmedDom(), and ghidra::FlowBlock::getIndex().

◆ buildDomTree()

void ghidra::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 ghidra::FlowBlock::immed_dom, and ghidra::FlowBlock::index.

◆ calcForwardDominator()

void ghidra::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 ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::immed_dom, ghidra::FlowBlock::index, ghidra::FlowBlock::removeOutEdge(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

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

◆ calcLoop()

void ghidra::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 ghidra::FlowBlock::clearFlag(), ghidra::FlowBlock::flags, ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isLoopOut(), ghidra::FlowBlock::setFlag(), and ghidra::FlowBlock::sizeOut().

◆ clearEdgeFlags()

void ghidra::BlockGraph::clearEdgeFlags ( uint4  fl)
private

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

Parameters
flis the set of boolean properties

References ghidra::FlowBlock::intothis, and ghidra::FlowBlock::outofthis.

◆ collectReachable()

void ghidra::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 ghidra::FlowBlock::clearMark(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::setMark(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::removeUnreachableBlocks().

◆ createVirtualRoot()

FlowBlock * ghidra::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

◆ decode()

void ghidra::BlockGraph::decode ( Decoder decoder)

Decode this BlockGraph from a stream.

Parse a <block> element. This is currently just a wrapper around the FlowBlock::decode() that sets of the BlockMap resolver

Parameters
decoderis the stream decoder

References ghidra::FlowBlock::decode().

Referenced by ghidra::IfcStructureBlocks::execute().

◆ decodeBody()

void ghidra::BlockGraph::decodeBody ( Decoder decoder)
virtual

◆ emit()

virtual void ghidra::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 ghidra::FlowBlock.

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

References ghidra::BlockEdge::decode(), and ghidra::PrintLanguage::emitBlockGraph().

◆ findIrreducible()

bool ghidra::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 ghidra::FlowBlock::clearMark(), ghidra::FlowBlock::clearOutEdgeFlag(), ghidra::FlowBlock::copymap, ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::FlowBlock::isBackEdgeIn(), ghidra::FlowBlock::isIrreducibleIn(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::isTreeEdgeIn(), ghidra::FlowBlock::numdesc, ghidra::FlowBlock::setMark(), ghidra::FlowBlock::setOutEdgeFlag(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::visitcount.

◆ findSpanningTree()

void ghidra::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 ghidra::FlowBlock::copymap, ghidra::FlowBlock::getOut(), ghidra::FlowBlock::index, ghidra::FlowBlock::isIrreducibleOut(), ghidra::FlowBlock::numdesc, ghidra::FlowBlock::setOutEdgeFlag(), ghidra::FlowBlock::sizeIn(), ghidra::FlowBlock::sizeOut(), and ghidra::FlowBlock::visitcount.

◆ forceFalseEdge()

void ghidra::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 ghidra::FlowBlock::getParent(), and ghidra::BlockEdge::point.

◆ forceOutputNum()

void ghidra::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

◆ getStartBlock()

FlowBlock * ghidra::BlockGraph::getStartBlock ( void  ) const

Get the entry point FlowBlock.

Throw an exception if no entry point is registered

Returns
the entry point FlowBlock

◆ identifyInternal()

void ghidra::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(), and selfIdentify().

◆ markCopyBlock()

void ghidra::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 ghidra::FlowBlock::flags, and ghidra::FlowBlock::getFrontLeaf().

◆ markLabelBumpUp()

void ghidra::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 ghidra::FlowBlock.

Reimplemented in ghidra::BlockInfLoop, ghidra::BlockDoWhile, and ghidra::BlockWhileDo.

References ghidra::FlowBlock::markLabelBumpUp().

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

◆ moveOutEdge()

void ghidra::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 ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getOutRevIndex(), ghidra::FlowBlock::parent, and ghidra::FlowBlock::replaceInEdge().

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

◆ newBlock()

FlowBlock * ghidra::BlockGraph::newBlock ( void  )

Build a new plain FlowBlock.

Add the new FlowBlock to this

Returns
the new FlowBlock

◆ newBlockBasic()

BlockBasic * ghidra::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

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

◆ newBlockCondition()

BlockCondition * ghidra::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 ghidra::CPUI_INT_AND, ghidra::CPUI_INT_OR, ghidra::FlowBlock::getFalseOut(), and ghidra::FlowBlock::getOut().

◆ newBlockCopy()

BlockCopy * ghidra::BlockGraph::newBlockCopy ( FlowBlock bl)

◆ newBlockDoWhile()

BlockDoWhile * ghidra::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

◆ newBlockGoto()

BlockGoto * ghidra::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 ghidra::FlowBlock::getOut().

◆ newBlockIf()

BlockIf * ghidra::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

◆ newBlockIfElse()

BlockIf * ghidra::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

◆ newBlockIfGoto()

BlockIf * ghidra::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 ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getTrueOut(), ghidra::FlowBlock::isGotoOut(), and ghidra::BlockIf::setGotoTarget().

◆ newBlockInfLoop()

BlockInfLoop * ghidra::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

◆ newBlockList()

BlockList * ghidra::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 ghidra::FlowBlock::sizeOut().

◆ newBlockMultiGoto()

BlockMultiGoto * ghidra::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 ghidra::BlockMultiGoto::addEdge(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getType(), ghidra::FlowBlock::isDefaultBranch(), and ghidra::BlockMultiGoto::setDefaultGoto().

◆ newBlockSwitch()

BlockSwitch * ghidra::BlockGraph::newBlockSwitch ( const vector< FlowBlock *> &  cs,
bool  hasExit 
)

Build a new BlockSwitch.

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

Parameters
csis the list of case FlowBlocks
hasExitis true if the switch has a formal exit
Returns
the new BlockSwitch

References ghidra::FlowBlock::clearFlag(), ghidra::FlowBlock::getExitLeaf(), ghidra::FlowBlock::getType(), ghidra::BlockSwitch::grabCaseBasic(), and ghidra::FlowBlock::subBlock().

◆ newBlockWhileDo()

BlockWhileDo * ghidra::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

Referenced by ghidra::CollapseStructure::ruleBlockWhileDo().

◆ nextFlowAfter()

FlowBlock * ghidra::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 ghidra::FlowBlock.

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

References ghidra::FlowBlock::getFrontLeaf().

◆ orderBlocks()

void ghidra::BlockGraph::orderBlocks ( void  )
inline

< Sort blocks using the final ordering

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

◆ printTree()

void ghidra::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 ghidra::FlowBlock.

References ghidra::FlowBlock::printTree().

Referenced by ghidra::Funcdata::printBlockTree().

◆ removeBlock()

void ghidra::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 ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::parent, ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

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

◆ removeEdge()

void ghidra::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 ghidra::FlowBlock::intothis, ghidra::FlowBlock::parent, and ghidra::FlowBlock::removeInEdge().

Referenced by ghidra::Funcdata::branchRemoveInternal(), and ghidra::Funcdata::nodeJoinCreateBlock().

◆ removeFromFlow()

void ghidra::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 ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::intothis, ghidra::FlowBlock::parent, ghidra::FlowBlock::removeOutEdge(), ghidra::FlowBlock::replaceOutEdge(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::blockRemoveInternal().

◆ removeFromFlowSplit()

void ghidra::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 ghidra::FlowBlock::parent, ghidra::FlowBlock::replaceEdgesThru(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::removeFromFlowSplit().

◆ selfIdentify()

void ghidra::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 ghidra::FlowBlock::intothis, ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::outofthis, ghidra::FlowBlock::parent, ghidra::FlowBlock::replaceInEdge(), and ghidra::FlowBlock::replaceOutEdge().

Referenced by identifyInternal().

◆ setStartBlock()

void ghidra::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 ghidra::FlowBlock::flags, and ghidra::FlowBlock::parent.

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

◆ spliceBlock()

void ghidra::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 ghidra::FlowBlock::flags, ghidra::FlowBlock::getOut(), ghidra::FlowBlock::removeOutEdge(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::spliceBlockBasic().

◆ structureLoops()

void ghidra::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 ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

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

◆ swapBlocks()

void ghidra::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

◆ switchEdge()

void ghidra::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 ghidra::FlowBlock::outofthis, and ghidra::FlowBlock::replaceOutEdge().

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


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