decompiler  1.0.0
Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | Friends | List of all members
ghidra::BlockBasic Class Reference

A basic block for p-code operations. More...

#include <block.hh>

Inheritance diagram for ghidra::BlockBasic:
ghidra::FlowBlock

Public Member Functions

 BlockBasic (Funcdata *fd)
 Construct given the underlying function.
 
FuncdatagetFuncdata (void)
 Return the underlying Funcdata object.
 
const FuncdatagetFuncdata (void) const
 Return the underlying Funcdata object.
 
bool contains (const Address &addr) const
 Determine if the given address is contained in the original range.
 
Address getEntryAddr (void) const
 Get the address of the (original) first operation to execute. More...
 
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 block_type getType (void) const
 Get the FlowBlock type of this.
 
virtual FlowBlocksubBlock (int4 i) const
 Get the i-th component 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...
 
virtual void printHeader (ostream &s) const
 Print a simple description of this to stream. 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 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 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)
 
bool unblockedMulti (int4 outslot) const
 Check if this block can be removed without introducing inconsistencies. More...
 
bool hasOnlyMarkers (void) const
 Does this block contain only MULTIEQUAL and INDIRECT ops. More...
 
bool isDoNothing (void) const
 Should this block should be removed. More...
 
list< PcodeOp * >::iterator beginOp (void)
 Return an iterator to the beginning of the PcodeOps.
 
list< PcodeOp * >::iterator endOp (void)
 Return an iterator to the end of the PcodeOps.
 
list< PcodeOp * >::const_iterator beginOp (void) const
 Return an iterator to the beginning of the PcodeOps.
 
list< PcodeOp * >::const_iterator endOp (void) const
 Return an iterator to the end of the PcodeOps.
 
bool emptyOp (void) const
 Return true if block contains no operations.
 
PcodeOpfindMultiequal (const vector< Varnode *> &varArray)
 Find MULTIEQUAL with given inputs. 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 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 bool preferComplement (Funcdata &data)
 Rearrange this hierarchy to simplify boolean expressions. 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 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...
 

Static Public Member Functions

static bool noInterveningStatement (PcodeOp *first, int4 path, PcodeOp *last)
 Check if there is meaningful activity between two branch instructions. More...
 
static bool liftVerifyUnroll (vector< Varnode *> &varArray, int4 slot)
 Verify given Varnodes are defined with same PcodeOp. 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...
 

Private Member Functions

void insert (list< PcodeOp *>::iterator iter, PcodeOp *inst)
 Insert p-code operation at a given position. More...
 
void setInitialRange (const Address &beg, const Address &end)
 Set the initial address range of the block. More...
 
void copyRange (const BlockBasic *bb)
 Copy address ranges from another basic block.
 
void mergeRange (const BlockBasic *bb)
 Merge address ranges from another basic block.
 
void setOrder (void)
 Reset the SeqNum::order field for all PcodeOp objects in this block. More...
 
void removeOp (PcodeOp *inst)
 Remove PcodeOp from this basic block. More...
 

Private Attributes

list< PcodeOp * > op
 The sequence of p-code operations.
 
Funcdatadata
 The function of which this block is a part.
 
RangeList cover
 Original range of addresses covered by this basic block.
 

Friends

class Funcdata
 

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...
 
- Protected Member Functions inherited from ghidra::FlowBlock
void setFlag (uint4 fl)
 Set a boolean property.
 
void clearFlag (uint4 fl)
 Clear a boolean property.
 

Detailed Description

A basic block for p-code operations.

A basic block is a maximal sequence of p-code operations (PcodeOp) that, within the context of a function, always execute starting with the first operation in sequence through in order to the last operation. Any decision points in the control flow of a function manifest as branching operations (BRANCH, CBRANCH, BRANCHIND) that necessarily occur as the last operation in a basic block.

Every Funcdata object implements the control-flow graph of the underlying function using BlockBasic objects as the underlying nodes of the graph. The decompiler structures code by making a copy of this graph and then overlaying a hierarchy of structured nodes on top of it.

The block also keeps track of the original range of addresses of instructions constituting the block. As decompiler transformations progress, the set of addresses associated with the current set of PcodeOps my migrate away from this original range.

Member Function Documentation

◆ decodeBody()

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

Restore details about this FlowBlock from an element stream.

Parameters
decoderis the stream decoder

Reimplemented from ghidra::FlowBlock.

◆ emit()

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

References ghidra::PrintLanguage::emitBlockBasic().

◆ findMultiequal()

PcodeOp * ghidra::BlockBasic::findMultiequal ( const vector< Varnode *> &  varArray)

Find MULTIEQUAL with given inputs.

If there exists a CPUI_MULTIEQUAL PcodeOp in this basic block that takes the given exact list of Varnodes as its inputs, return that PcodeOp. Otherwise return null.

Parameters
varArrayis the exact list of Varnodes
Returns
the MULTIEQUAL or null

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::endDescend(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), and ghidra::PcodeOp::numInput().

Referenced by ghidra::JumpBasic::checkUnrolledGuard().

◆ flipInPlaceExecute()

void ghidra::BlockBasic::flipInPlaceExecute ( void  )
virtual

Perform the flip to normalize conditional branch executed by this block.

This reverses the outgoing edge order in the right basic blocks, but does not modify the instructions directly.

Reimplemented from ghidra::FlowBlock.

References ghidra::PcodeOp::fallthru_true, ghidra::PcodeOp::flipFlag(), and ghidra::FlowBlock::negateCondition().

Referenced by ghidra::ActionNormalizeBranches::apply().

◆ flipInPlaceTest()

int4 ghidra::BlockBasic::flipInPlaceTest ( vector< PcodeOp *> &  fliplist) const
virtual

Test normalizing the conditional branch in this.

Find the set of PcodeOp objects that need to be adjusted to flip the condition this FlowBlock calculates.

Return:

  • 0 if the flip would normalize the condition
  • 1 if the flip doesn't affect normalization of the condition
  • 2 if the flip produces an unnormalized condition
    Parameters
    fliplistwill contain the PcodeOps that need to be adjusted
    Returns
    0 if the condition will be normalized, 1 or 2 otherwise

Reimplemented from ghidra::FlowBlock.

References ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, and ghidra::opFlipInPlaceTest().

◆ getEntryAddr()

Address ghidra::BlockBasic::getEntryAddr ( void  ) const

Get the address of the (original) first operation to execute.

This relies slightly on normal semantics: when instructions fall-thru during execution, the associated address increases.

Returns
the address of the original entry point instruction for this block

References ghidra::Range::getFirstAddr().

Referenced by ghidra::PrintC::emitLabel().

◆ getSplitPoint()

FlowBlock * ghidra::BlockBasic::getSplitPoint ( void  )
virtual

Get the leaf splitting block.

If this block ends with a conditional branch, return the deepest component block that performs the split. This component needs to be able to perform flipInPlaceTest() and flipInPlaceExecute()

Returns
the component FlowBlock or NULL if this doesn't end in a conditional branch

Reimplemented from ghidra::FlowBlock.

◆ hasOnlyMarkers()

bool ghidra::BlockBasic::hasOnlyMarkers ( void  ) const

Does this block contain only MULTIEQUAL and INDIRECT ops.

This is a crucial test for whether this block is doing anything substantial or is a candidate for removal. Even blocks that "do nothing" have some kind of branch and placeholder operations (MULTIEQUAL and INDIRECT) for data flowing through the block. This tests if there is any other operation going on.

Returns
true if there only MULTIEQUAL, INDIRECT, and branch operations in this

References ghidra::PcodeOp::isBranch(), and ghidra::PcodeOp::isMarker().

Referenced by noInterveningStatement().

◆ insert()

void ghidra::BlockBasic::insert ( list< PcodeOp *>::iterator  iter,
PcodeOp inst 
)
private

Insert p-code operation at a given position.

The operation is inserted before the PcodeOp pointed at by the iterator. This method also assigns the ordering index for the PcodeOp, getSeqNum().getOrder()

Parameters
iterpoints at the PcodeOp to insert before
instis the PcodeOp to insert

References ghidra::PcodeOp::code(), ghidra::CPUI_BRANCHIND, ghidra::PcodeOp::isBranch(), ghidra::PcodeOp::setBasicIter(), ghidra::PcodeOp::setOrder(), and ghidra::PcodeOp::setParent().

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

◆ isDoNothing()

bool ghidra::BlockBasic::isDoNothing ( void  ) const

Should this block should be removed.

Check if this block is doing anything useful.

Returns
true if the block does nothing and should be removed

References ghidra::PcodeOp::code(), and ghidra::CPUI_BRANCHIND.

◆ liftVerifyUnroll()

bool ghidra::BlockBasic::liftVerifyUnroll ( vector< Varnode *> &  varArray,
int4  slot 
)
static

Verify given Varnodes are defined with same PcodeOp.

Each Varnode must be defined by a PcodeOp with the same OpCode. The Varnode, within the array, is replaced with the input Varnode in the indicated slot.

Parameters
varArrayis the given array of Varnodes
slotis the indicated slot
Returns
true if all the Varnodes are defined in the same way

References ghidra::PcodeOp::code(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::Varnode::isConstant(), ghidra::Varnode::isWritten(), and ghidra::PcodeOp::numInput().

Referenced by ghidra::JumpBasic::checkUnrolledGuard().

◆ negateCondition()

bool ghidra::BlockBasic::negateCondition ( bool  toporbottom)
virtual

Flip the condition computed by this.

Flip the order of outgoing edges (at least). This should also affect the original op causing the condition. Note: we don't have to flip at all levels of the hierarchy only at the top and at the bottom

Parameters
toporbottomis true if this is the top outermost block of the hierarchy getting negated
Returns
true if a change was made to data-flow

Reimplemented from ghidra::FlowBlock.

References ghidra::PcodeOp::boolean_flip, ghidra::PcodeOp::fallthru_true, ghidra::PcodeOp::flipFlag(), and ghidra::FlowBlock::negateCondition().

◆ noInterveningStatement()

bool ghidra::BlockBasic::noInterveningStatement ( PcodeOp first,
int4  path,
PcodeOp last 
)
static

Check if there is meaningful activity between two branch instructions.

The first branch is assumed to be a CBRANCH one edge of which flows into the other branch. The flow can be through 1 or 2 blocks. If either block performs an operation other than MULTIEQUAL, INDIRECT (or the branch), then return false.

Parameters
firstis the CBRANCH operation
pathis the index of the edge to follow to the other branch
lastis the other branch operation
Returns
true if there is no meaningful activity

References ghidra::FlowBlock::getOut(), ghidra::PcodeOp::getParent(), hasOnlyMarkers(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::JumpBasic::foldInOneGuard().

◆ printHeader()

void ghidra::BlockBasic::printHeader ( ostream &  s) const
virtual

Print a simple description of this to stream.

Only print a header for this single block

Parameters
sis the output stream

Reimplemented from ghidra::FlowBlock.

References ghidra::FlowBlock::printHeader().

◆ removeOp()

void ghidra::BlockBasic::removeOp ( PcodeOp inst)
private

Remove PcodeOp from this basic block.

Parameters
instis the PcodeOp to remove, which must be in the block

References ghidra::PcodeOp::basiciter, and ghidra::PcodeOp::setParent().

Referenced by ghidra::Funcdata::opDestroy(), and ghidra::Funcdata::opUninsert().

◆ setInitialRange()

void ghidra::BlockBasic::setInitialRange ( const Address beg,
const Address end 
)
private

Set the initial address range of the block.

In terms of machine instructions, a basic block always covers a range of addresses, from its first instruction to its last. This method establishes that range.

Parameters
begis the address of the first instruction in the block
endis the address of the last instruction in the block

References ghidra::Address::getOffset(), and ghidra::Address::getSpace().

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

◆ setOrder()

void ghidra::BlockBasic::setOrder ( void  )
private

Reset the SeqNum::order field for all PcodeOp objects in this block.

The SeqNum::order field for each PcodeOp must mirror the ordering of that PcodeOp within this block. Insertions are usually handled by calculating an appropriate SeqNum::order field for the new PcodeOp, but sometime there isn't enough room between existing ops. This method is then called to recalculate the SeqNum::order field for all PcodeOp objects in this block, reestablishing space between the field values.

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

◆ unblockedMulti()

bool ghidra::BlockBasic::unblockedMulti ( int4  outslot) const

Check if this block can be removed without introducing inconsistencies.

Does removing this block leads to redundant MULTIEQUAL entries which are inconsistent. A MULTIEQUAL can hide an implied copy, in which case this block is actually doing something and shouldn't be removed.

Parameters
outslotis the index of the outblock that this is getting collapsed to
Returns
true if there is no implied COPY

References ghidra::PcodeOp::code(), ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getInIndex(), ghidra::FlowBlock::getOut(), ghidra::PcodeOp::getParent(), ghidra::Varnode::isWritten(), op, and ghidra::FlowBlock::sizeOut().


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