decompiler
1.0.0
|
A basic block for p-code operations. More...
#include <block.hh>
Public Member Functions | |
BlockBasic (Funcdata *fd) | |
Construct given the underlying function. | |
Funcdata * | getFuncdata (void) |
Return the underlying Funcdata object. | |
const Funcdata * | getFuncdata (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 FlowBlock * | subBlock (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 FlowBlock * | getExitLeaf (void) const |
Get the FlowBlock to which this block exits. | |
virtual PcodeOp * | lastOp (void) const |
Get the last PcodeOp executed by this FlowBlock. | |
virtual bool | negateCondition (bool toporbottom) |
Flip the condition computed by this. More... | |
virtual FlowBlock * | getSplitPoint (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. | |
PcodeOp * | findMultiequal (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. | |
FlowBlock * | getParent (void) |
Get the parent FlowBlock of this. | |
FlowBlock * | getImmedDom (void) const |
Get the immediate dominator FlowBlock. | |
FlowBlock * | getCopyMap (void) const |
Get the mapped FlowBlock. | |
const FlowBlock * | getParent (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 FlowBlock * | nextFlowAfter (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 FlowBlock * | nextInFlow (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... | |
FlowBlock * | getFalseOut (void) const |
Get the false output FlowBlock. | |
FlowBlock * | getTrueOut (void) const |
Get the true output FlowBlock. | |
FlowBlock * | getOut (int4 i) |
Get the i-th output FlowBlock. | |
const FlowBlock * | getOut (int4 i) const |
Get i-th output FlowBlock. | |
int4 | getOutRevIndex (int4 i) const |
Get the input index of the i-th output FlowBlock. | |
FlowBlock * | getIn (int4 i) |
Get the i-th input FlowBlock. | |
const FlowBlock * | getIn (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 FlowBlock * | getFrontLeaf (void) const |
Get the first leaf FlowBlock. More... | |
FlowBlock * | getFrontLeaf (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. | |
JumpTable * | getJumptable (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 FlowBlock * | findCommonBlock (FlowBlock *bl1, FlowBlock *bl2) |
Find the common dominator of two FlowBlocks. More... | |
static FlowBlock * | findCommonBlock (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. | |
Funcdata * | data |
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. | |
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.
|
virtual |
Restore details about this FlowBlock from an element stream.
decoder | is the stream decoder |
Reimplemented from ghidra::FlowBlock.
|
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.
lng | is the PrintLanguage that provides details of the high-level language being printed |
Reimplemented from ghidra::FlowBlock.
References ghidra::PrintLanguage::emitBlockBasic().
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.
varArray | is the exact list of Varnodes |
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().
|
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().
|
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:
fliplist | will contain the PcodeOps that need to be adjusted |
Reimplemented from ghidra::FlowBlock.
References ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, and ghidra::opFlipInPlaceTest().
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.
References ghidra::Range::getFirstAddr().
Referenced by ghidra::PrintC::emitLabel().
|
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()
Reimplemented from ghidra::FlowBlock.
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.
References ghidra::PcodeOp::isBranch(), and ghidra::PcodeOp::isMarker().
Referenced by noInterveningStatement().
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()
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().
bool ghidra::BlockBasic::isDoNothing | ( | void | ) | const |
Should this block should be removed.
Check if this block is doing anything useful.
References ghidra::PcodeOp::code(), and ghidra::CPUI_BRANCHIND.
|
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.
varArray | is the given array of Varnodes |
slot | is the indicated slot |
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().
|
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
toporbottom | is true if this is the top outermost block of the hierarchy getting negated |
Reimplemented from ghidra::FlowBlock.
References ghidra::PcodeOp::boolean_flip, ghidra::PcodeOp::fallthru_true, ghidra::PcodeOp::flipFlag(), and ghidra::FlowBlock::negateCondition().
|
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.
first | is the CBRANCH operation |
path | is the index of the edge to follow to the other branch |
last | is the other branch operation |
References ghidra::FlowBlock::getOut(), ghidra::PcodeOp::getParent(), hasOnlyMarkers(), and ghidra::FlowBlock::sizeOut().
Referenced by ghidra::JumpBasic::foldInOneGuard().
|
virtual |
Print a simple description of this to stream.
Only print a header for this single block
s | is the output stream |
Reimplemented from ghidra::FlowBlock.
References ghidra::FlowBlock::printHeader().
|
private |
Remove PcodeOp from this basic block.
inst | is 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().
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.
beg | is the address of the first instruction in the block |
end | is 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().
|
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().
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.
outslot | is the index of the outblock that this is getting collapsed to |
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().