ROSE  0.9.9.109
DataFlow.h
1 #ifndef ROSE_Partitioner2_DataFlow_H
2 #define ROSE_Partitioner2_DataFlow_H
3 
4 #include <BinaryDataFlow.h>
5 #include <BinaryStackVariable.h>
6 #include <Partitioner2/BasicBlock.h>
7 #include <Partitioner2/ControlFlowGraph.h>
8 #include <Partitioner2/Function.h>
9 #include <Sawyer/Graph.h>
10 
11 namespace Rose {
12 namespace BinaryAnalysis {
13 namespace Partitioner2 {
14 
16 namespace DataFlow {
17 
19 // Control Flow Graph
21 
25 class DfCfgVertex {
26 public:
28  enum Type {
33  };
34 
35 private:
36  Type type_;
37  BasicBlock::Ptr bblock_; // attached to BBLOCK vertices
38  Function::Ptr callee_; // function represented by FAKED_CALL
39 
40 public:
42  explicit DfCfgVertex(const BasicBlock::Ptr &bblock): type_(BBLOCK), bblock_(bblock) {
43  ASSERT_not_null(bblock);
44  }
45 
47  explicit DfCfgVertex(const Function::Ptr &function): type_(FAKED_CALL), callee_(function) {}
48 
50  explicit DfCfgVertex(Type type): type_(type) {
51  ASSERT_require2(BBLOCK!=type && FAKED_CALL!=type, "use a different constructor");
52  }
53 
57  Type type() const { return type_; }
58 
63  const BasicBlock::Ptr& bblock() const { return bblock_; }
64 
66  const Function::Ptr& callee() const { return callee_; }
67 };
68 
91 
98 public:
99  virtual ~InterproceduralPredicate() {}
100  virtual bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) = 0;
101 };
102 
105 public:
106  bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) ROSE_OVERRIDE {
107  return false;
108  }
109 };
110 extern NotInterprocedural NOT_INTERPROCEDURAL;
111 
113 std::vector<SgAsmInstruction*> vertexUnpacker(const DfCfgVertex&);
114 
121 DfCfg buildDfCfg(const Partitioner&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
122  InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);
123 
125 void dumpDfCfg(std::ostream&, const DfCfg&);
126 
133 
139 template<class DfCfg>
141 findReturnVertex(DfCfg &dfCfg) {
142  using namespace Sawyer::Container;
143  typename GraphTraits<DfCfg>::VertexIterator retval = dfCfg.vertices().end();
144  for (typename GraphTraits<DfCfg>::VertexIterator vi = dfCfg.vertices().begin(); vi != dfCfg.vertices().end(); ++vi) {
145  if (vi->value().type() == DfCfgVertex::FUNCRET) {
146  ASSERT_require(retval == dfCfg.vertices().end());
147  retval = vi;
148  }
149  }
150  return retval;
151 }
152 
154 // Transfer function
155 //
156 // The transfer function is reponsible for taking a CFG vertex and an initial state and producing the next state, the final
157 // state for that vertex. Users can use whatever transfer function they want; this one is based on the DfCfg and an
158 // instruction semantics state.
160 
164  BaseSemantics::SValuePtr callRetAdjustment_;
165  const RegisterDescriptor STACK_POINTER_REG;
166  CallingConvention::DefinitionPtr defaultCallingConvention_;
167 public:
172  : cpu_(cpu), STACK_POINTER_REG(cpu->stackPointerRegister()) {
173  size_t adjustment = STACK_POINTER_REG.get_nbits() / 8; // sizeof return address on top of stack
174  callRetAdjustment_ = cpu->number_(STACK_POINTER_REG.get_nbits(), adjustment);
175  }
176 
179 
183  BaseSemantics::DispatcherPtr cpu() const { return cpu_; }
184 
193  CallingConvention::DefinitionPtr defaultCallingConvention() const { return defaultCallingConvention_; }
194  void defaultCallingConvention(const CallingConvention::DefinitionPtr &x) { defaultCallingConvention_ = x; }
197  // Required by data-flow engine
198  std::string printState(const BaseSemantics::StatePtr &state);
199 
200  // Required by data-flow engine: compute new output state given a vertex and input state.
201  BaseSemantics::StatePtr operator()(const DfCfg&, size_t vertexId, const BaseSemantics::StatePtr &incomingState) const;
202 };
203 
209 
212 
225  const BaseSemantics::SValuePtr &initialStackPointer);
226 
232  const BaseSemantics::SValuePtr &initialStackPointer);
233 
240  const BaseSemantics::SValuePtr &initialStackPointer);
241 
246 std::vector<AbstractLocation> findGlobalVariables(const BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes);
247 
248 
249 
250 } // namespace
251 } // namespace
252 } // namespace
253 } // namespace
254 
255 #endif
Rose::BinaryAnalysis::DataFlow::Engine< DfCfg, BaseSemantics::StatePtr, TransferFunction, MergeFunction > Engine
Data-Flow engine.
Definition: DataFlow.h:211
Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction
Data-flow merge function.
Definition: DataFlow.h:208
std::vector< AbstractLocation > findGlobalVariables(const BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes)
Returns a list of global variables.
Predicate that always returns false, preventing interprocedural analysis.
Definition: DataFlow.h:104
BaseSemantics::DispatcherPtr cpu() const
Property: Virtual CPU.
Definition: DataFlow.h:183
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
Function::Ptr bestSummaryFunction(const FunctionSet &functions)
Choose best function for data-flow summary vertex.
const BasicBlock::Ptr & bblock() const
Basic block.
Definition: DataFlow.h:63
Sawyer::Container::GraphTraits< DfCfg >::VertexIterator findReturnVertex(DfCfg &dfCfg)
Find the return vertex.
Definition: DataFlow.h:141
std::vector< StackVariable > StackVariables
Multiple stack variables.
Basic merge operation for instruction semantics.
void defaultCallingConvention(const CallingConvention::DefinitionPtr &x)
Property: Default calling convention.
Definition: DataFlow.h:194
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1454
Main namespace for the ROSE library.
Describes (part of) a physical CPU register.
DfCfgVertex(Type type)
Construct a vertex of specified type that takes no auxiliary data.
Definition: DataFlow.h:50
StackVariables findStackVariables(const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known stack variables.
TransferFunction(const BaseSemantics::DispatcherPtr &cpu)
Construct from a CPU.
Definition: DataFlow.h:171
CFG vertex for data-flow analysis.
Definition: DataFlow.h:25
Vertex represents returning to the caller.
Definition: DataFlow.h:31
DfCfg buildDfCfg(const Partitioner &, const ControlFlowGraph &, const ControlFlowGraph::ConstVertexIterator &startVertex, InterproceduralPredicate &predicate=NOT_INTERPROCEDURAL)
build a cfg useful for data-flow analysis.
Container classes that store user-defined values.
Definition: AddressMap.h:31
boost::shared_ptr< class State > StatePtr
Shared-ownership pointer to a semantic state.
boost::shared_ptr< class Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
BaseSemantics::StatePtr initialState() const
Construct an initial state.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Predicate that decides when to use inter-procedural data-flow.
Definition: DataFlow.h:97
StackVariables findLocalVariables(const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known local variables.
DfCfgVertex(const BasicBlock::Ptr &bblock)
Construct a basic block vertex.
Definition: DataFlow.h:42
StackVariables findFunctionArguments(const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known function arguments.
std::vector< SgAsmInstruction * > vertexUnpacker(const DfCfgVertex &)
Unpacks a vertex into a list of instructions.
DfCfgVertex(const Function::Ptr &function)
Construct a faked call vertex.
Definition: DataFlow.h:47
Various tools for data-flow analysis.
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
Definition: Graph.h:295
void dumpDfCfg(std::ostream &, const DfCfg &)
Emit a data-flow CFG as a GraphViz file.
Indeterminate basic block where no information is available.
Definition: DataFlow.h:32
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:289
Sawyer::Container::Graph< DfCfgVertex > DfCfg
Control flow graph used by data-flow analysis.
Definition: DataFlow.h:90
const Function::Ptr & callee() const
Function represented by faked call.
Definition: DataFlow.h:66
CallingConvention::DefinitionPtr defaultCallingConvention() const
Property: Default calling convention.
Definition: DataFlow.h:193