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

Class for merging low-level Varnodes into high-level HighVariables. More...

#include <merge.hh>

Public Member Functions

 Merge (Funcdata &fd)
 Construct given a specific function.
 
void clear (void)
 Clear the any cached data from the last merge process. More...
 
bool inflateTest (Varnode *a, HighVariable *high)
 Test if we can inflate the Cover of the given Varnode without incurring intersections. More...
 
void inflate (Varnode *a, HighVariable *high)
 Inflate the Cover of a given Varnode with a HighVariable. More...
 
bool mergeTest (HighVariable *high, vector< HighVariable *> &tmplist)
 Test for intersections between a given HighVariable and a list of other HighVariables. More...
 
void mergeOpcode (OpCode opc)
 Try to force merges of input to output for all p-code ops of a given type. More...
 
void mergeByDatatype (VarnodeLocSet::const_iterator startiter, VarnodeLocSet::const_iterator enditer)
 Try to merge all HighVariables in the given range that have the same data-type. More...
 
void mergeAddrTied (void)
 Force the merge of address tried Varnodes. More...
 
void mergeMarker (void)
 Force the merge of input and output Varnodes to MULTIEQUAL and INDIRECT ops. More...
 
void groupPartials (void)
 Run through CONCAT tree roots and group each tree.
 
void mergeAdjacent (void)
 Speculatively merge Varnodes that are input/output to the same p-code op. More...
 
void mergeMultiEntry (void)
 Merge together Varnodes mapped to SymbolEntrys from the same Symbol. More...
 
bool hideShadows (HighVariable *high)
 Hide shadow Varnodes related to the given HighVariable by consolidating COPY chains. More...
 
void processCopyTrims (void)
 Try to reduce/eliminate COPYs produced by the merge trimming process. More...
 
void markInternalCopies (void)
 Mark redundant/internal COPY PcodeOps. More...
 
void registerProtoPartialRoot (Varnode *vn)
 Register an unmapped CONCAT stack with the merge process. More...
 

Private Member Functions

void collectCovering (vector< Varnode *> &vlist, HighVariable *high, PcodeOp *op)
 Collect all instances of the given HighVariable whose Cover intersects a p-code op. More...
 
bool collectCorrectable (const vector< Varnode *> &vlist, list< PcodeOp *> &oplist, vector< int4 > &slotlist, PcodeOp *op)
 Check for for p-code op intersections that are correctable. More...
 
PcodeOpallocateCopyTrim (Varnode *inVn, const Address &addr, PcodeOp *trimOp)
 Allocate COPY PcodeOp designed to trim an overextended Cover. More...
 
void snipReads (Varnode *vn, list< PcodeOp *> &markedop)
 Snip off set of read p-code ops for a given Varnode. More...
 
void snipIndirect (PcodeOp *indop)
 Snip instances of the input of an INDIRECT op that interfere with its output. More...
 
void eliminateIntersect (Varnode *vn, const vector< BlockVarnode > &blocksort)
 Eliminate intersections of given Varnode with other Varnodes in a list. More...
 
void unifyAddress (VarnodeLocSet::const_iterator startiter, VarnodeLocSet::const_iterator enditer)
 Make sure all Varnodes with the same storage address and size can be merged. More...
 
void trimOpOutput (PcodeOp *op)
 Trim the output HighVariable of the given PcodeOp so that its Cover is tiny. More...
 
void trimOpInput (PcodeOp *op, int4 slot)
 Trim the input HighVariable of the given PcodeOp so that its Cover is tiny. More...
 
void mergeRangeMust (VarnodeLocSet::const_iterator startiter, VarnodeLocSet::const_iterator enditer)
 Force the merge of a ranges of Varnodes with the same size and storage address. More...
 
void mergeOp (PcodeOp *op)
 Force the merge of all input and output Varnodes for the given PcodeOp. More...
 
void mergeIndirect (PcodeOp *indop)
 Force the merge of all input and output Varnodes to a given INDIRECT op. More...
 
void mergeLinear (vector< HighVariable *> &highvec)
 Speculatively merge all HighVariables in the given list as well as possible. More...
 
bool merge (HighVariable *high1, HighVariable *high2, bool isspeculative)
 Perform low-level details of merging two HighVariables if possible. More...
 
bool checkCopyPair (HighVariable *high, PcodeOp *domOp, PcodeOp *subOp)
 Check if the given PcodeOp COPYs are redundant. More...
 
void buildDominantCopy (HighVariable *high, vector< PcodeOp *> &copy, int4 pos, int4 size)
 Try to replace a set of COPYs from the same Varnode with a single dominant COPY. More...
 
void markRedundantCopies (HighVariable *high, vector< PcodeOp *> &copy, int4 pos, int4 size)
 Search for and mark redundant COPY ops into the given high as non-printing. More...
 
void processHighDominantCopy (HighVariable *high)
 Try to replace COPYs into the given HighVariable with a single dominant COPY. More...
 
void processHighRedundantCopy (HighVariable *high)
 Mark COPY ops into the given HighVariable that are redundant. More...
 
void groupPartialRoot (Varnode *vn)
 Group the different nodes of a CONCAT tree into a VariableGroup. More...
 

Static Private Member Functions

static bool mergeTestRequired (HighVariable *high_out, HighVariable *high_in)
 Required tests to merge HighVariables that are not Cover related. More...
 
static bool mergeTestAdjacent (HighVariable *high_out, HighVariable *high_in)
 Adjacency tests for merging Varnodes that are input or output to the same p-code op. More...
 
static bool mergeTestSpeculative (HighVariable *high_out, HighVariable *high_in)
 Speculative tests for merging HighVariables that are not Cover related. More...
 
static void mergeTestMust (Varnode *vn)
 Test if the given Varnode that must be merged, can be merged. More...
 
static bool mergeTestBasic (Varnode *vn)
 Test if the given Varnode can ever be merged. More...
 
static void findSingleCopy (HighVariable *high, vector< Varnode *> &singlelist)
 Find instance Varnodes that copied to from outside the given HighVariable. More...
 
static bool compareHighByBlock (const HighVariable *a, const HighVariable *b)
 Compare HighVariables by the blocks they cover. More...
 
static bool compareCopyByInVarnode (PcodeOp *op1, PcodeOp *op2)
 Compare COPY ops first by Varnode input, then by block containing the op. More...
 
static bool shadowedVarnode (const Varnode *vn)
 Determine if given Varnode is shadowed by another Varnode in the same HighVariable. More...
 
static void findAllIntoCopies (HighVariable *high, vector< PcodeOp *> &copyIns, bool filterTemps)
 Find all the COPY ops into the given HighVariable. More...
 

Private Attributes

Funcdatadata
 The function containing the Varnodes to be merged.
 
HighIntersectTest testCache
 Cached intersection tests.
 
vector< PcodeOp * > copyTrims
 COPY ops inserted to facilitate merges.
 
vector< PcodeOp * > protoPartial
 Roots of unmapped CONCAT trees.
 

Detailed Description

Class for merging low-level Varnodes into high-level HighVariables.

As a node in Single Static Assignment (SSA) form, a Varnode has at most one defining operation. To get a suitable notion of a single high-level variable (HighVariable) that may be reassigned at multiple places in a single function, individual Varnode objects can be merged into a HighVariable object. Varnode objects may be merged in this way if there is no pairwise intersection between each Varnode's Cover, the ranges of code where the Varnode holds its value.

For a given function, this class attempts to merge Varnodes using various strategies and keeps track of Cover intersections to facilitate the process. Merge strategies break up into two general categories: forced merges, and speculative merges. Forced merges must happen, and extra Varnodes may be added to split up problematic covers to enforce it. Forced merges include:

Speculative merges are attempted to reduce the overall number of variables defined by a function, but any given merge attempt is abandoned if there are Cover intersections. No modification is made to the data-flow to force the merge. Speculative merges include:

Member Function Documentation

◆ allocateCopyTrim()

PcodeOp * ghidra::Merge::allocateCopyTrim ( Varnode inVn,
const Address addr,
PcodeOp trimOp 
)
private

Allocate COPY PcodeOp designed to trim an overextended Cover.

A COPY is allocated with the given input and data-type. A unique space output is created.

Parameters
inVnis the given input Varnode for the new COPY
addris the address associated with the new COPY
trimOpis an exemplar PcodeOp whose read is being trimmed
Returns
the newly allocated COPY

References ghidra::CPUI_COPY, ghidra::Varnode::getDef(), ghidra::ResolvedUnion::getFieldNum(), ghidra::Varnode::getSize(), ghidra::PcodeOp::getSlot(), ghidra::Varnode::getType(), ghidra::Varnode::isWritten(), and ghidra::Datatype::needsResolution().

◆ buildDominantCopy()

void ghidra::Merge::buildDominantCopy ( HighVariable high,
vector< PcodeOp *> &  copy,
int4  pos,
int4  size 
)
private

Try to replace a set of COPYs from the same Varnode with a single dominant COPY.

All the COPY outputs must be instances of the same HighVariable (not the same Varnode). Either an existing COPY dominates all the others, or a new dominating COPY is constructed. The read locations of all other COPY outputs are replaced with the output of the dominating COPY, if it does not cause intersections in the HighVariable's Cover. Because of intersections, replacement may fail or partially succeed. Replacement only happens with COPY outputs that are temporary registers. The cover of the HighVariable may be extended because of a new COPY output instance.

Parameters
highis the HighVariable being copied to
copyis the list of COPY ops into the HighVariable
posis the index of the first COPY from the specific input Varnode
sizeis the number of COPYs (in sequence) from the same specific Varnode

References ghidra::Cover::addDefPoint(), ghidra::Cover::addRefPoint(), ghidra::Varnode::beginDescend(), ghidra::PcodeOp::clearMark(), ghidra::PcodeOp::code(), ghidra::Varnode::copyShadow(), ghidra::CPUI_COPY, ghidra::Varnode::endDescend(), ghidra::FlowBlock::findCommonBlock(), ghidra::Varnode::getCover(), ghidra::Varnode::getDef(), ghidra::ResolvedUnion::getFieldNum(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::HighVariable::getInstance(), ghidra::Datatype::getMetatype(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ghidra::Varnode::getSize(), ghidra::BlockBasic::getStop(), ghidra::Varnode::getType(), ghidra::Varnode::getTypeReadFacing(), ghidra::Cover::intersect(), ghidra::PcodeOp::isMark(), ghidra::Varnode::isWritten(), ghidra::Cover::merge(), ghidra::HighVariable::merge(), ghidra::Datatype::needsResolution(), ghidra::HighVariable::numInstances(), ghidra::HighVariable::remove(), ghidra::PcodeOp::setMark(), ghidra::TYPE_PARTIALUNION, and ghidra::BlockVarnode::vn.

◆ checkCopyPair()

bool ghidra::Merge::checkCopyPair ( HighVariable high,
PcodeOp domOp,
PcodeOp subOp 
)
private

Check if the given PcodeOp COPYs are redundant.

Both the given COPYs assign to the same HighVariable. One is redundant if there is no other assignment to the HighVariable between the first COPY and the second COPY. The first COPY must come from a block with a smaller or equal index to the second COPY. If the indices are equal, the first COPY must come before the second within the block.

Parameters
highis the HighVariable being assigned to
domOpis the first COPY
subOpis the second COPY
Returns
true if the second COPY is redundant

References ghidra::Cover::addDefPoint(), ghidra::Cover::addRefPoint(), ghidra::PcodeOp::code(), ghidra::Cover::contain(), ghidra::CPUI_COPY, ghidra::FlowBlock::dominates(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::HighVariable::getInstance(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ghidra::Varnode::isWritten(), ghidra::HighVariable::numInstances(), and ghidra::BlockVarnode::vn.

◆ clear()

void ghidra::Merge::clear ( void  )

Clear the any cached data from the last merge process.

Free up resources used by cached intersection tests etc.

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

◆ collectCorrectable()

bool ghidra::Merge::collectCorrectable ( const vector< Varnode *> &  vlist,
list< PcodeOp *> &  oplist,
vector< int4 > &  slotlist,
PcodeOp op 
)
private

Check for for p-code op intersections that are correctable.

Given a list of Varnodes that intersect a specific PcodeOp, check that each intersection is on the boundary, and if so, pass back the read op(s) that cause the intersection.

Parameters
vlistis the given list of intersecting Varnodes
oplistwill hold the boundary intersecting read ops
slotlistwill hold the corresponding input slots of the instance
opis the specific intersecting PcodeOp
Returns
false if any instance in the list intersects the PcodeOp on the interior

References ghidra::Varnode::beginDescend(), ghidra::CoverBlock::boundary(), ghidra::Varnode::endDescend(), ghidra::Varnode::getCover(), ghidra::Cover::getCoverBlock(), ghidra::FlowBlock::getIndex(), ghidra::PcodeOp::getParent(), ghidra::PcodeOp::getSlot(), ghidra::CoverBlock::getUIndex(), and ghidra::BlockVarnode::vn.

◆ collectCovering()

void ghidra::Merge::collectCovering ( vector< Varnode *> &  vlist,
HighVariable high,
PcodeOp op 
)
private

Collect all instances of the given HighVariable whose Cover intersects a p-code op.

Efficiently test if each instance Varnodes contains the specific p-code op in its Cover and return a list of the instances that do.

Parameters
vlistwill hold the resulting list of intersecting instances
highis the given HighVariable
opis the specific PcodeOp to test intersection with

References ghidra::CoverBlock::contain(), ghidra::Varnode::getCover(), ghidra::Cover::getCoverBlock(), ghidra::FlowBlock::getIndex(), ghidra::HighVariable::getInstance(), ghidra::PcodeOp::getParent(), ghidra::HighVariable::numInstances(), and ghidra::BlockVarnode::vn.

◆ compareCopyByInVarnode()

bool ghidra::Merge::compareCopyByInVarnode ( PcodeOp op1,
PcodeOp op2 
)
staticprivate

Compare COPY ops first by Varnode input, then by block containing the op.

A sort designed to group COPY ops from the same Varnode together. Then within a group, COPYs are sorted by their containing basic block (so that dominating ops come first).

Parameters
op1is the first PcodeOp being compared
op2is the second PcodeOp being compared
Returns
true if the first PcodeOp should be ordered before the second

References ghidra::Varnode::getCreateIndex(), ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getIndex(), ghidra::SeqNum::getOrder(), ghidra::PcodeOp::getParent(), and ghidra::PcodeOp::getSeqNum().

◆ compareHighByBlock()

bool ghidra::Merge::compareHighByBlock ( const HighVariable a,
const HighVariable b 
)
inlinestaticprivate

Compare HighVariables by the blocks they cover.

This comparator sorts, based on:

  • Index of the first block containing cover for the HighVariable
  • Address of the first instance
  • Address of the defining p-code op
  • Storage address
Parameters
ais the first HighVariable to compare
bis the second HighVariable
Returns
true if the first HighVariable should be ordered before the second

References ghidra::Cover::compareTo(), ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::HighVariable::getCover(), ghidra::Varnode::getDef(), and ghidra::HighVariable::getInstance().

◆ eliminateIntersect()

void ghidra::Merge::eliminateIntersect ( Varnode vn,
const vector< BlockVarnode > &  blocksort 
)
private

◆ findAllIntoCopies()

void ghidra::Merge::findAllIntoCopies ( HighVariable high,
vector< PcodeOp *> &  copyIns,
bool  filterTemps 
)
staticprivate

Find all the COPY ops into the given HighVariable.

Collect all the COPYs whose output is the given HighVariable but the input is from a different HighVariable. Returned COPYs are sorted first by the input Varnode then by block order.

Parameters
highis the given HighVariable
copyInswill hold the list of COPYs
filterTempsis true if COPYs must have a temporary output

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::Varnode::getDef(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::HighVariable::getInstance(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSpace(), ghidra::AddrSpace::getType(), ghidra::IPTR_INTERNAL, ghidra::Varnode::isWritten(), ghidra::HighVariable::numInstances(), and ghidra::BlockVarnode::vn.

◆ findSingleCopy()

void ghidra::Merge::findSingleCopy ( HighVariable high,
vector< Varnode *> &  singlelist 
)
staticprivate

Find instance Varnodes that copied to from outside the given HighVariable.

Find all Varnodes in the HighVariable which are defined by a COPY from another Varnode which is not part of the same HighVariable.

Parameters
highis the given HighVariable
singlelistwill hold the resulting list of copied instances

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::Varnode::getDef(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::HighVariable::getInstance(), ghidra::Varnode::isWritten(), ghidra::HighVariable::numInstances(), and ghidra::BlockVarnode::vn.

◆ groupPartialRoot()

void ghidra::Merge::groupPartialRoot ( Varnode vn)
private

Group the different nodes of a CONCAT tree into a VariableGroup.

This formally labels all the Varnodes in the tree as overlapping pieces of the same variable. The tree is reconstructed from the root Varnode.

Parameters
vnis the root Varnode

References ghidra::Varnode::clearProtoPartial(), ghidra::PieceNode::gatherPieces(), ghidra::Varnode::getDef(), ghidra::Varnode::getHigh(), ghidra::SymbolEntry::getOffset(), ghidra::Varnode::getSymbolEntry(), ghidra::BlockVarnode::getVarnode(), ghidra::HighVariable::groupWith(), ghidra::Varnode::isProtoPartial(), and ghidra::HighVariable::numInstances().

◆ hideShadows()

bool ghidra::Merge::hideShadows ( HighVariable high)

Hide shadow Varnodes related to the given HighVariable by consolidating COPY chains.

If two Varnodes are copied from the same common ancestor then they will always contain the same value and can be considered shadows of the same variable. If the paths from the ancestor to the two Varnodes aren't properly nested, the two Varnodes will still look like distinct variables. This routine searches for this situation, relative to a single HighVariable, and alters data-flow so that copying from ancestor to first Varnode to second Varnode becomes a single path. Both Varnodes then ultimately become instances of the same HighVariable.

Parameters
highis the given HighVariable to search near
Returns
true if a change was made to data-flow

References ghidra::Cover::containVarnodeDef(), ghidra::Varnode::copyShadow(), ghidra::Varnode::getCover(), and ghidra::Varnode::getDef().

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

◆ inflate()

void ghidra::Merge::inflate ( Varnode a,
HighVariable high 
)

Inflate the Cover of a given Varnode with a HighVariable.

An expression involving a HighVariable can be propagated to all the read sites of the output Varnode of the expression if the Varnode Cover can be inflated to include the Cover of the HighVariable, even though the Varnode is not part of the HighVariable. This routine performs the inflation, assuming an intersection test is already performed.

Parameters
ais the given Varnode to inflate
highis the HighVariable to inflate with

References ghidra::Varnode::cover, ghidra::HighVariable::coverDirty(), ghidra::Varnode::getHigh(), ghidra::HighVariable::getInstance(), ghidra::Cover::merge(), and ghidra::HighVariable::numInstances().

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

◆ inflateTest()

bool ghidra::Merge::inflateTest ( Varnode a,
HighVariable high 
)

Test if we can inflate the Cover of the given Varnode without incurring intersections.

This routine tests whether an expression involving a HighVariable can be propagated to all the read sites of the output Varnode of the expression. This is possible only if the Varnode Cover can be inflated to include the Cover of the HighVariable, even though the Varnode is not part of the HighVariable.

Parameters
ais the given Varnode to inflate
highis the HighVariable being propagated
Returns
true if inflating the Varnode causes an intersection

References ghidra::Varnode::copyShadow(), ghidra::Varnode::getCover(), ghidra::VariablePiece::getHigh(), ghidra::Varnode::getHigh(), ghidra::HighVariable::getInstance(), ghidra::VariablePiece::getIntersection(), ghidra::VariablePiece::getOffset(), ghidra::HighVariable::internalCover, ghidra::Cover::intersect(), ghidra::HighVariable::numInstances(), ghidra::VariablePiece::numIntersection(), ghidra::Varnode::partialCopyShadow(), ghidra::HighVariable::piece, and ghidra::VariablePiece::updateIntersections().

Referenced by ghidra::ActionMarkImplied::checkImpliedCover().

◆ markInternalCopies()

void ghidra::Merge::markInternalCopies ( void  )

Mark redundant/internal COPY PcodeOps.

Run through all COPY, SUBPIECE, and PIECE operations (PcodeOps that copy data) and characterize those that are internal (copy data between storage locations representing the same variable) or redundant (perform the same copy as an earlier operation). These, as a result, are not printed in the final source code representation.

References ghidra::HighVariable::clearCopyIns(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_PIECE, ghidra::CPUI_SUBPIECE, ghidra::VariablePiece::getGroup(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::VariablePiece::getOffset(), ghidra::Varnode::getOffset(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::Varnode::getSpace(), ghidra::HighVariable::hasCopyIn1(), ghidra::HighVariable::hasCopyIn2(), ghidra::Varnode::hasNoDescend(), ghidra::AddrSpace::isBigEndian(), ghidra::HighVariable::piece, ghidra::HighVariable::setCopyIn1(), and ghidra::HighVariable::setCopyIn2().

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

◆ markRedundantCopies()

void ghidra::Merge::markRedundantCopies ( HighVariable high,
vector< PcodeOp *> &  copy,
int4  pos,
int4  size 
)
private

Search for and mark redundant COPY ops into the given high as non-printing.

Trimming during the merge process can insert multiple COPYs from the same source. In some cases, one or more COPYs may be redundant and shouldn't be printed. This method searches for redundancy among COPY ops that assign to the given HighVariable.

Parameters
highis the given HighVariable
copyis the list of COPYs coming from the same source HighVariable
posis the starting index of a set of COPYs coming from the same Varnode
sizeis the number of Varnodes in the set coming from the same Varnode

References ghidra::PcodeOp::isDead().

◆ merge()

bool ghidra::Merge::merge ( HighVariable high1,
HighVariable high2,
bool  isspeculative 
)
private

Perform low-level details of merging two HighVariables if possible.

This routine only fails (returning false) if there is a Cover intersection between the two variables. Otherwise, all the Varnode instances from the second HighVariable are merged into the first and its Cover is updated. The second variable is deleted. The cached intersection tests are also updated to reflect the merge.

Parameters
high1is the first HighVariable being merged
high2is the second
isspeculativeis true if the desired merge is speculative
Returns
true if the merge was successful

References ghidra::HighVariable::merge(), and ghidra::HighVariable::updateCover().

◆ mergeAddrTied()

void ghidra::Merge::mergeAddrTied ( void  )

Force the merge of address tried Varnodes.

For each set of address tied Varnodes with the same size and storage address, merge them into a single HighVariable. The merges are forced, so any Cover intersections must be resolved by altering data-flow, which involves inserting additional COPY ops and unique Varnodes.

References ghidra::Varnode::addrtied, ghidra::Varnode::getAddr(), ghidra::Varnode::getHigh(), ghidra::Varnode::getOffset(), ghidra::Varnode::getSize(), ghidra::AddrSpace::getType(), ghidra::HighVariable::groupWith(), ghidra::IPTR_PROCESSOR, ghidra::IPTR_SPACEBASE, ghidra::Varnode::isFree(), and ghidra::BlockVarnode::vn.

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

◆ mergeAdjacent()

void ghidra::Merge::mergeAdjacent ( void  )

Speculatively merge Varnodes that are input/output to the same p-code op.

If a single p-code op has an input and output HighVariable that share the same data-type, attempt to merge them. Each merge is speculative and is skipped if it would introduce Cover intersections.

References ghidra::Varnode::getDef(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::PcodeOp::inputTypeLocal(), ghidra::PcodeOp::isCall(), ghidra::Varnode::isInput(), ghidra::PcodeOp::numInput(), and ghidra::PcodeOp::outputTypeLocal().

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

◆ mergeByDatatype()

void ghidra::Merge::mergeByDatatype ( VarnodeLocSet::const_iterator  startiter,
VarnodeLocSet::const_iterator  enditer 
)

Try to merge all HighVariables in the given range that have the same data-type.

HighVariables that have an instance within the given Varnode range are sorted into groups based on their data-type. Then an attempt is made to merge all the HighVariables within a group. If a particular merge causes Cover intersection, it is skipped.

Parameters
startiteris the start of the given range of Varnodes
enditeris the end of the given range

References ghidra::HighVariable::getType(), ghidra::Varnode::isFree(), ghidra::HighVariable::isMark(), ghidra::HighVariable::setMark(), and ghidra::BlockVarnode::vn.

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

◆ mergeIndirect()

void ghidra::Merge::mergeIndirect ( PcodeOp indop)
private

Force the merge of all input and output Varnodes to a given INDIRECT op.

Merging INDIRECTs take a little care if their output is address forced because by convention the value must be present at the address BEFORE the indirect effect operation takes place.

Parameters
indopis the given INDIRECT

References ghidra::PcodeOp::getAddr(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSymbolEntry(), and ghidra::Varnode::isAddrForce().

◆ mergeLinear()

void ghidra::Merge::mergeLinear ( vector< HighVariable *> &  highvec)
private

Speculatively merge all HighVariables in the given list as well as possible.

The variables are first sorted by the index of the earliest block in their range. Then proceeding in order, an attempt is made to merge each variable with the first. The attempt fails if the speculative test doesn't pass or if there are Cover intersections, in which case that particular merge is skipped.

◆ mergeMarker()

void ghidra::Merge::mergeMarker ( void  )

Force the merge of input and output Varnodes to MULTIEQUAL and INDIRECT ops.

Run through all MULTIEQUAL and INDIRECT ops in the function. Force the merge of each input Varnode with the output Varnode, doing data-flow modification if necessary to resolve Cover intersections.

References ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::PcodeOp::isIndirectCreation(), and ghidra::PcodeOp::isMarker().

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

◆ mergeMultiEntry()

void ghidra::Merge::mergeMultiEntry ( void  )

Merge together Varnodes mapped to SymbolEntrys from the same Symbol.

Symbols that have more than one SymbolEntry may attach to more than one Varnode. These Varnodes need to be merged to properly represent a single variable.

References ghidra::Symbol::getMapEntry(), ghidra::Symbol::getName(), ghidra::SymbolEntry::getSize(), ghidra::Datatype::getSize(), ghidra::Symbol::getType(), ghidra::Symbol::numEntries(), ghidra::Symbol::setMergeProblems(), and ghidra::HighVariable::setUnmerged().

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

◆ mergeOp()

void ghidra::Merge::mergeOp ( PcodeOp op)
private

Force the merge of all input and output Varnodes for the given PcodeOp.

Data-flow for specific input and output Varnodes are snipped until everything can be merged.

Parameters
opis the given PcodeOp

References ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getSeqNum(), and ghidra::PcodeOp::numInput().

◆ mergeOpcode()

void ghidra::Merge::mergeOpcode ( OpCode  opc)

Try to force merges of input to output for all p-code ops of a given type.

For a given opcode, run through all ops in the function in block/address order and try to merge each input HighVariable with the output HighVariable. If this would introduce Cover intersections, the merge is skipped. This is generally used to try to merge the input and output of COPY ops if possible.

Parameters
opcis the op-code type to merge

References ghidra::BlockBasic::beginOp(), ghidra::PcodeOp::code(), ghidra::BlockBasic::endOp(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), and ghidra::PcodeOp::numInput().

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

◆ mergeRangeMust()

void ghidra::Merge::mergeRangeMust ( VarnodeLocSet::const_iterator  startiter,
VarnodeLocSet::const_iterator  enditer 
)
private

Force the merge of a ranges of Varnodes with the same size and storage address.

The list of Varnodes to be merged is provided as a range in the main location sorted container. Any Cover intersection is assumed to already be snipped, so any problems with merging cause an exception to be thrown.

Parameters
startiteris the beginning of the range of Varnodes with the same storage address
enditeris the end of the range

References ghidra::Varnode::getHigh(), and ghidra::BlockVarnode::vn.

◆ mergeTest()

bool ghidra::Merge::mergeTest ( HighVariable high,
vector< HighVariable *> &  tmplist 
)

Test for intersections between a given HighVariable and a list of other HighVariables.

If there is any Cover intersection between the given HighVariable and one in the list, this routine returns false. Otherwise, the given HighVariable is added to the end of the list and true is returned.

Parameters
highis the given HighVariable
tmplistis the list of HighVariables to test against
Returns
true if there are no pairwise intersections.

References ghidra::Varnode::getHigh(), ghidra::HighVariable::hasCopyIn1(), ghidra::HighVariable::hasCover(), ghidra::Varnode::hasCover(), ghidra::HighVariable::setCopyIn1(), and ghidra::BlockVarnode::vn.

◆ mergeTestAdjacent()

bool ghidra::Merge::mergeTestAdjacent ( HighVariable high_out,
HighVariable high_in 
)
staticprivate

Adjacency tests for merging Varnodes that are input or output to the same p-code op.

All the required tests (mergeTestRequired()) are performed, and then some additional tests are performed. This does not perform any Cover tests.

Parameters
high_outis the output HighVariable to test
high_inis the input HighVariable to test
Returns
true if tests pass and the HighVariables are not forbidden to merge

References ghidra::HighVariable::getInputVarnode(), ghidra::HighVariable::getSymbol(), ghidra::HighVariable::getType(), ghidra::Varnode::isIllegalInput(), ghidra::Varnode::isIndirectOnly(), ghidra::HighVariable::isInput(), ghidra::Symbol::isIsolated(), ghidra::HighVariable::isNameLock(), ghidra::HighVariable::piece, and ghidra::BlockVarnode::vn.

◆ mergeTestBasic()

bool ghidra::Merge::mergeTestBasic ( Varnode vn)
staticprivate

Test if the given Varnode can ever be merged.

Some Varnodes (constants, annotations, implied, spacebase) are never merged with another Varnode.

Parameters
vnis the Varnode to test
Returns
true if the Varnode is not forbidden from ever merging

References ghidra::Varnode::hasCover(), ghidra::Varnode::isImplied(), ghidra::Varnode::isProtoPartial(), and ghidra::Varnode::isSpacebase().

◆ mergeTestMust()

void ghidra::Merge::mergeTestMust ( Varnode vn)
staticprivate

Test if the given Varnode that must be merged, can be merged.

If it cannot be merged, throw an exception.

Parameters
vnis the given Varnode

References ghidra::Varnode::hasCover(), and ghidra::Varnode::isImplied().

◆ mergeTestRequired()

bool ghidra::Merge::mergeTestRequired ( HighVariable high_out,
HighVariable high_in 
)
staticprivate

Required tests to merge HighVariables that are not Cover related.

This is designed to short circuit merge tests, when we know properties of the two HighVariables preclude merging. For example, you can't merge HighVariables if:

  • They are locked to different data-types
  • They are both mapped to different address ranges
  • One is a parameter one is a global
Parameters
high_outis the first HighVariable to test
high_inis the second HighVariable to test
Returns
true if tests pass and the HighVariables are not forbidden to merge

References ghidra::Varnode::getAddr(), ghidra::VariablePiece::getGroup(), ghidra::VariableGroup::getSize(), ghidra::VariablePiece::getSize(), ghidra::HighVariable::getSymbol(), ghidra::HighVariable::getSymbolOffset(), ghidra::HighVariable::getTiedVarnode(), ghidra::HighVariable::getType(), ghidra::HighVariable::isAddrTied(), ghidra::HighVariable::isExtraOut(), ghidra::HighVariable::isInput(), ghidra::HighVariable::isPersist(), ghidra::HighVariable::isProtoPartial(), ghidra::HighVariable::isTypeLock(), and ghidra::HighVariable::piece.

◆ mergeTestSpeculative()

bool ghidra::Merge::mergeTestSpeculative ( HighVariable high_out,
HighVariable high_in 
)
staticprivate

Speculative tests for merging HighVariables that are not Cover related.

This does all the required and adjacency merge tests and then performs additional tests required for speculative merges.

Parameters
high_outis the first HighVariable to test
high_inis the second HighVariable to test
Returns
true if tests pass and the HighVariables are not forbidden to merge

References ghidra::HighVariable::isAddrTied(), ghidra::HighVariable::isInput(), and ghidra::HighVariable::isPersist().

◆ processCopyTrims()

void ghidra::Merge::processCopyTrims ( void  )

Try to reduce/eliminate COPYs produced by the merge trimming process.

In order to force merging of certain Varnodes, extra COPY operations may be inserted to reduce their Cover ranges, and multiple COPYs from the same Varnode can be created this way. This method collects sets of COPYs generated in this way that have the same input Varnode and then tries to replace the COPYs with fewer or a single COPY.

References ghidra::HighVariable::clearCopyIns(), ghidra::HighVariable::hasCopyIn1(), ghidra::HighVariable::hasCopyIn2(), ghidra::HighVariable::setCopyIn1(), and ghidra::HighVariable::setCopyIn2().

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

◆ processHighDominantCopy()

void ghidra::Merge::processHighDominantCopy ( HighVariable high)
private

Try to replace COPYs into the given HighVariable with a single dominant COPY.

Find groups of COPYs into the given HighVariable that come from a single source Varnode, then try to replace them with a COPY.

Parameters
highis the given HighVariable

◆ processHighRedundantCopy()

void ghidra::Merge::processHighRedundantCopy ( HighVariable high)
private

Mark COPY ops into the given HighVariable that are redundant.

A COPY is redundant if another COPY performs the same action and has dominant control flow. The redundant COPY is not removed but is marked so that it doesn't print in the final source output.

Parameters
highis the given HighVariable

◆ registerProtoPartialRoot()

void ghidra::Merge::registerProtoPartialRoot ( Varnode vn)

Register an unmapped CONCAT stack with the merge process.

The given Varnode must be the root of a tree of CPUI_PIECE operations as produced by PieceNode::gatherPieces. These will be grouped together into a single variable.

Parameters
vnis the given root Varnode

References ghidra::Varnode::getDef().

Referenced by ghidra::RulePieceStructure::applyOp().

◆ shadowedVarnode()

bool ghidra::Merge::shadowedVarnode ( const Varnode vn)
staticprivate

Determine if given Varnode is shadowed by another Varnode in the same HighVariable.

Parameters
vnis the Varnode to check for shadowing
Returns
true if vn is shadowed by another Varnode in its high-level variable

References ghidra::Varnode::getCover(), ghidra::Varnode::getHigh(), ghidra::HighVariable::getInstance(), ghidra::Cover::intersect(), and ghidra::HighVariable::numInstances().

◆ snipIndirect()

void ghidra::Merge::snipIndirect ( PcodeOp indop)
private

Snip instances of the input of an INDIRECT op that interfere with its output.

Examine the input and output HighVariable for the given INDIRECT op. Varnode instances of the input that intersect the output Cover are snipped by creating a new COPY op from the input to a new temporary and then replacing the Varnode reads with the temporary.

Parameters
indopis the given INDIRECT op

References ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::Varnode::getHigh(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOpFromConst(), and ghidra::PcodeOp::getOut().

◆ snipReads()

void ghidra::Merge::snipReads ( Varnode vn,
list< PcodeOp *> &  markedop 
)
private

Snip off set of read p-code ops for a given Varnode.

The data-flow for the given Varnode is truncated by creating a COPY p-code from the Varnode into a new temporary Varnode, then replacing the Varnode reads for a specific set of p-code ops with the temporary.

Parameters
vnis the given Varnode
markedopis the specific set of PcodeOps reading the Varnode

References ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOpFromConst(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ghidra::PcodeOp::getSlot(), ghidra::BlockBasic::getStart(), and ghidra::Varnode::isInput().

◆ trimOpInput()

void ghidra::Merge::trimOpInput ( PcodeOp op,
int4  slot 
)
private

Trim the input HighVariable of the given PcodeOp so that its Cover is tiny.

The given PcodeOp is assumed to force merging so that input and output Covers shouldn't intersect. A new COPY is inserted right before the given PcodeOp with a new unique output that replaces the specified input, disassociating it from the other original inputs and output.

Parameters
opis the given PcodeOp
slotis the specified slot of the input Varnode to be trimmed

References ghidra::PcodeOp::code(), ghidra::CPUI_MULTIEQUAL, ghidra::PcodeOp::getAddr(), ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getIn(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ghidra::BlockBasic::getStop(), and ghidra::BlockVarnode::vn.

◆ trimOpOutput()

void ghidra::Merge::trimOpOutput ( PcodeOp op)
private

Trim the output HighVariable of the given PcodeOp so that its Cover is tiny.

The given PcodeOp is assumed to force merging so that input and output Covers shouldn't intersect. The original PcodeOp output is moved so that it becomes the output of a new COPY, disassociating the original output Varnode from the inputs.

Parameters
opis the given PcodeOp

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INDIRECT, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::PcodeOp::getIn(), ghidra::Datatype::getMetatype(), ghidra::PcodeOp::getOpFromConst(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::Varnode::getType(), ghidra::Varnode::getTypeDefFacing(), ghidra::Datatype::needsResolution(), ghidra::TYPE_PARTIALUNION, and ghidra::BlockVarnode::vn.

◆ unifyAddress()

void ghidra::Merge::unifyAddress ( VarnodeLocSet::const_iterator  startiter,
VarnodeLocSet::const_iterator  enditer 
)
private

Make sure all Varnodes with the same storage address and size can be merged.

The list of Varnodes to be merged is provided as a range in the main location sorted container. Any discovered intersection is snipped by splitting data-flow for one of the Varnodes into two or more flows, which involves inserting new COPY ops and temporaries.

Parameters
startiteris the beginning of the range of Varnodes with the same storage address
enditeris the end of the range

References ghidra::Varnode::isFree(), and ghidra::BlockVarnode::vn.


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