Description

Data-flow utilities.

Classes
class	DfCfgVertex
	CFG vertex for data-flow analysis. More...

class	InterproceduralPredicate
	Predicate that decides when to use inter-procedural data-flow. More...

class	NotInterprocedural
	Predicate that always returns false, preventing interprocedural analysis. More...

class	TransferFunction
	Data-Flow transfer functor. More...

Typedefs
using	DfCfg = Sawyer::Container::Graph< DfCfgVertex >
	Control flow graph used by data-flow analysis.

typedef Rose::BinaryAnalysis::DataFlow::SemanticsMerge	MergeFunction
	Data-flow merge function.

using	Engine = Rose::BinaryAnalysis::DataFlow::Engine< DfCfg, InstructionSemantics::BaseSemantics::StatePtr, TransferFunction, MergeFunction >
	Data-Flow engine.

Functions
std::vector< SgAsmInstruction * >	vertexUnpacker (const DfCfgVertex &)
	Unpacks a vertex into a list of instructions.

DfCfg	buildDfCfg (const PartitionerConstPtr &, const ControlFlowGraph &, const ControlFlowGraph::ConstVertexIterator &startVertex, InterproceduralPredicate &predicate=NOT_INTERPROCEDURAL)
	build a cfg useful for data-flow analysis.

void	dumpDfCfg (std::ostream &, const DfCfg &)
	Emit a data-flow CFG as a GraphViz file.

FunctionPtr	bestSummaryFunction (const FunctionSet &functions)
	Choose best function for data-flow summary vertex.

template<class DfCfg >
Sawyer::Container::GraphTraits< DfCfg >::VertexIterator	findReturnVertex (DfCfg &dfCfg)
	Find the return vertex.

Variables::StackVariables	findStackVariables (const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
	Returns the list of all known stack variables.

Variables::StackVariables	findLocalVariables (const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
	Returns the list of all known local variables.

Variables::StackVariables	findFunctionArguments (const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
	Returns the list of all known function arguments.

std::vector< AbstractLocation >	findGlobalVariables (const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes)
	Returns a list of global variables.

Variables
NotInterprocedural	NOT_INTERPROCEDURAL

Typedef Documentation

◆ DfCfg

using Rose::BinaryAnalysis::Partitioner2::DataFlow::DfCfg = typedef Sawyer::Container::Graph<DfCfgVertex>

Control flow graph used by data-flow analysis.

The CFG used for data-flow is slightly different than the global CFG maintained by the partitioner. The partitioner's global CFG is tuned for discovering basic blocks and deciding which basic blocks are owned by which functions, whereas a data-flow's CFG is tuned for performing data flow analysis. A data-flow CFG is usually constructed from the partitioner's global CFG, but differs in the following ways:

First, data-flow analysis is usually performed on a subset of the partitioner's global CFG. This function uses the startVertex to select some connected subgraph, such as a subgraph corresponding to a single function definition when given the entry block.

Function return blocks (e.g., RET instructions) are handled differently during data-flow. In the partitioner's global CFG each return block is marked as a function return and has single successor–the indeterminate vertex. In a data-flow CFG the return blocks are not handled specially, but rather all flow into a single special return vertex that has no instructions. This allows data to be merged from all the return points.

Function call sites are modified. In the partitioner global CFG a function call (e.g., CALL instruction) has an edge (or edges) going to the entry block of the called function(s) and a special call-return edge to the return site if there is one (usually the fall-through address). A data-flow analysis often needs to perform some special action for the call-return, thus a call-return edge in the global CFG gets transformed to an edge-vertex-edge sequence in the data-flow CFG where the middle vertex is a special CALLRET vertex with no instructions.

Definition at line 123 of file Partitioner2/DataFlow.h.

◆ MergeFunction

typedef Rose::BinaryAnalysis::DataFlow::SemanticsMerge Rose::BinaryAnalysis::Partitioner2::DataFlow::MergeFunction

Data-flow merge function.

Computes the meet of two states, merging the source state into the destination state and returning true iff the destination state changed.

Definition at line 254 of file Partitioner2/DataFlow.h.

◆ Engine

using Rose::BinaryAnalysis::Partitioner2::DataFlow::Engine = typedef Rose::BinaryAnalysis::DataFlow::Engine<DfCfg, InstructionSemantics::BaseSemantics::StatePtr, TransferFunction, MergeFunction>

Data-Flow engine.

Definition at line 257 of file Partitioner2/DataFlow.h.

Function Documentation

◆ buildDfCfg()

DfCfg Rose::BinaryAnalysis::Partitioner2::DataFlow::buildDfCfg	(	const PartitionerConstPtr &	,
		const ControlFlowGraph &	,
		const ControlFlowGraph::ConstVertexIterator &	startVertex,
		InterproceduralPredicate &	predicate = `NOT_INTERPROCEDURAL`
	)

build a cfg useful for data-flow analysis.

The returned CFG will be constructed from the global CFG vertices that are reachable from startVertex such that the reached vertex belongs to the same function as startVertex.

See also: DfCfg

◆ bestSummaryFunction()

FunctionPtr Rose::BinaryAnalysis::Partitioner2::DataFlow::bestSummaryFunction ( const FunctionSet & functions )

Choose best function for data-flow summary vertex.

When replacing a function call edge with a function summary, we insert a data-flow vertex that points to a function. During the data-flow processing, the function's information summarizes the data-flow state changes that are necessary. If multiple functions own the target block of a function call edge then we need to choose the "best" function to use.

◆ findReturnVertex()

template<class DfCfg >

Sawyer::Container::GraphTraits< DfCfg >::VertexIterator Rose::BinaryAnalysis::Partitioner2::DataFlow::findReturnVertex ( DfCfg & dfCfg )

Find the return vertex.

Finds the FUNCRET vertex. Function returns all flow into this special vertex, but if there are no function return blocks then this vertex also doesn't exist (in which case the end iterator is returned). Do not call this if there's a chance that the data-flow CFG has more than one FUNCRET vertex.

Definition at line 174 of file Partitioner2/DataFlow.h.

References Rose::BinaryAnalysis::Partitioner2::DataFlow::DfCfgVertex::FUNCRET, and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().

◆ findStackVariables()

Variables::StackVariables Rose::BinaryAnalysis::Partitioner2::DataFlow::findStackVariables	(	const FunctionPtr &	function,
		const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &	ops,
		const InstructionSemantics::BaseSemantics::SValuePtr &	initialStackPointer
	)

Returns the list of all known stack variables.

A stack variable is any memory location whose address is a constant offset from an initial stack pointer. That is, the address has the form (add SP0 CONSTANT) where SP0 is a variable supplied as an argument to this function. When CONSTANT is zero the expression is simplified to SP0, so that also is accepted. Although memory is byte addressable and values are stored as individual bytes in memory, this function attempts to sew related addresses back together again to produce variables that are multiple bytes. There are many ways to do this, all of which are heuristic.

The ops provides the operators for comparing stack pointers, and also provides the state which is examined to find the stack variables. The underlying memory state should be of type MemoryCellList or a subclass, or else no stack variables will be found.

◆ findLocalVariables()

Variables::StackVariables Rose::BinaryAnalysis::Partitioner2::DataFlow::findLocalVariables	(	const FunctionPtr &	function,
		const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &	ops,
		const InstructionSemantics::BaseSemantics::SValuePtr &	initialStackPointer
	)

Returns the list of all known local variables.

A local variable is any stack variable whose starting address is less than the specified stack pointer. For the definition of stack variable, see findStackVariables.

◆ findFunctionArguments()

Variables::StackVariables Rose::BinaryAnalysis::Partitioner2::DataFlow::findFunctionArguments	(	const FunctionPtr &	function,
		const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &	ops,
		const InstructionSemantics::BaseSemantics::SValuePtr &	initialStackPointer
	)

Returns the list of all known function arguments.

A function argument is any stack variable whose starting address is greater than or equal to the specified stack pointer. For the definition of stack variable, see findStackVariables. On architectures that pass a return address on the top of the stack, that return address is considered to be the first argument of the function.

◆ findGlobalVariables()

std::vector< AbstractLocation > Rose::BinaryAnalysis::Partitioner2::DataFlow::findGlobalVariables	(	const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &	ops,
		size_t	wordNBytes
	)

Returns a list of global variables.

The returned abstract locations all point to memory. The wordNBytes is the maximum size for any returned variable; larger units of memory written to by the same instruction will be broken into smaller variables.