ROSE 0.11.145.147
Partitioner2/DataFlow.h
1#ifndef ROSE_BinaryAnalysis_Partitioner2_DataFlow_H
2#define ROSE_BinaryAnalysis_Partitioner2_DataFlow_H
3#include <featureTests.h>
4#ifdef ROSE_ENABLE_BINARY_ANALYSIS
5#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
6#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/BasicTypes.h>
7
8#include <Rose/BinaryAnalysis/DataFlow.h>
9#include <Rose/BinaryAnalysis/Variables.h>
10#include <Sawyer/Graph.h>
11
12#include <ostream>
13#include <string>
14
15namespace Rose {
16namespace BinaryAnalysis {
17namespace Partitioner2 {
18
20namespace DataFlow {
21
23// Control Flow Graph
25
30public:
38
39private:
40 Type type_;
41 BasicBlockPtr bblock_; // attached to BBLOCK vertices
42 FunctionPtr callee_; // function represented by FAKED_CALL
43 FunctionPtr parentFunction_; // function "owning" this vertex
44 size_t inliningId_; // invocation ID for inlining functions during inter-procedural
45
46public:
48
51
54
57
61 Type type() const;
62
67 const BasicBlockPtr& bblock() const;
68
70 const FunctionPtr& callee() const;
71
78
84 size_t inliningId() const;
85
90
94 void print(std::ostream&) const;
95
99 std::string toString() const;
100};
101
124
131public:
132 virtual ~InterproceduralPredicate() {}
133 virtual bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) = 0;
134};
135
138public:
139 bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t /*depth*/) override {
140 return false;
141 }
142};
143extern NotInterprocedural NOT_INTERPROCEDURAL;
144
146std::vector<SgAsmInstruction*> vertexUnpacker(const DfCfgVertex&);
147
154DfCfg buildDfCfg(const PartitionerConstPtr&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
155 InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);
156
158void dumpDfCfg(std::ostream&, const DfCfg&);
159
166
172template<class DfCfg>
175 using namespace Sawyer::Container;
176 typename GraphTraits<DfCfg>::VertexIterator retval = dfCfg.vertices().end();
177 for (typename GraphTraits<DfCfg>::VertexIterator vi = dfCfg.vertices().begin(); vi != dfCfg.vertices().end(); ++vi) {
178 if (vi->value().type() == DfCfgVertex::FUNCRET) {
179 ASSERT_require(retval == dfCfg.vertices().end());
180 retval = vi;
181 }
182 }
183 return retval;
184}
185
187// Transfer function
188//
189// The transfer function is reponsible for taking a CFG vertex and an initial state and producing the next state, the final
190// state for that vertex. Users can use whatever transfer function they want; this one is based on the DfCfg and an
191// instruction semantics state.
193
198 const RegisterDescriptor STACK_POINTER_REG;
199 const RegisterDescriptor INSN_POINTER_REG;
200 CallingConvention::DefinitionPtr defaultCallingConvention_;
201 bool ignoringSemanticFailures_;
202
203public:
205
210
213
218
242 // Required by data-flow engine
243 std::string toString(const InstructionSemantics::BaseSemantics::StatePtr &state);
244
245 // Required by data-flow engine: compute new output state given a vertex and input state.
247 operator()(const DfCfg&, size_t vertexId, const InstructionSemantics::BaseSemantics::StatePtr &incomingState) const;
248};
249
255
261
275 const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer);
276
283 const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer);
284
292 const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer);
293
299 size_t wordNBytes);
300
301} // namespace
302} // namespace
303} // namespace
304} // namespace
305
306#endif
307#endif
Basic merge operation for instruction semantics.
Definition DataFlow.h:218
DfCfgVertex(const BasicBlockPtr &, const FunctionPtr &parentFunction, size_t inliningId)
Construct a basic block vertex.
std::string toString() const
Single-line description of this vertex.
void print(std::ostream &) const
Print a short description of this vertex.
Sawyer::Optional< rose_addr_t > address() const
Virtual address of vertex.
DfCfgVertex(Type type, const FunctionPtr &parentFunction, size_t inliningId)
Construct a vertex of specified type that takes no auxiliary data.
FunctionPtr parentFunction() const
Function owning this vertex.
size_t inliningId() const
Inlining invocation number.
DfCfgVertex(const FunctionPtr &function, const FunctionPtr &parentFunction, size_t inliningId)
Construct a faked call vertex.
@ FUNCRET
Vertex represents returning to the caller.
@ INDET
Indeterminate basic block where no information is available.
const FunctionPtr & callee() const
Function represented by faked call.
const BasicBlockPtr & bblock() const
Basic block.
Predicate that decides when to use inter-procedural data-flow.
Predicate that always returns false, preventing interprocedural analysis.
void ignoringSemanticFailures(bool)
Property: Whether to ignore instructions with unknown semantics.
InstructionSemantics::BaseSemantics::DispatcherPtr cpu() const
Property: Virtual CPU.
bool ignoringSemanticFailures() const
Property: Whether to ignore instructions with unknown semantics.
TransferFunction(const InstructionSemantics::BaseSemantics::DispatcherPtr &)
Construct from a CPU.
void defaultCallingConvention(const CallingConvention::DefinitionPtr &)
Property: Default calling convention.
InstructionSemantics::BaseSemantics::StatePtr initialState() const
Construct an initial state.
CallingConvention::DefinitionPtr defaultCallingConvention() const
Property: Default calling convention.
Describes (part of) a physical CPU register.
Graph containing user-defined vertices and edges.
Definition Graph.h:634
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition Graph.h:1538
Holds a value or nothing.
Definition Optional.h:56
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
std::vector< SgAsmInstruction * > vertexUnpacker(const DfCfgVertex &)
Unpacks a vertex into a list of instructions.
FunctionPtr bestSummaryFunction(const FunctionSet &functions)
Choose best function for data-flow summary vertex.
Variables::StackVariables findFunctionArguments(const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known function arguments.
Variables::StackVariables findStackVariables(const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known stack variables.
Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction
Data-flow merge function.
Sawyer::Container::Graph< DfCfgVertex > DfCfg
Control flow graph used by data-flow analysis.
std::vector< AbstractLocation > findGlobalVariables(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes)
Returns a list of global variables.
Sawyer::Container::GraphTraits< DfCfg >::VertexIterator findReturnVertex(DfCfg &dfCfg)
Find the return vertex.
DfCfg buildDfCfg(const PartitionerConstPtr &, const ControlFlowGraph &, const ControlFlowGraph::ConstVertexIterator &startVertex, InterproceduralPredicate &predicate=NOT_INTERPROCEDURAL)
build a cfg useful for data-flow analysis.
Variables::StackVariables findLocalVariables(const FunctionPtr &function, const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops, const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known local variables.
void dumpDfCfg(std::ostream &, const DfCfg &)
Emit a data-flow CFG as a GraphViz file.
The ROSE library.
Container classes that store user-defined values.
Definition AddressMap.h:31
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
Definition Graph.h:292