ROSE  0.9.10.103
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  Function::Ptr parentFunction_; // function "owning" this vertex
40  size_t inliningId_; // invocation ID for inlining functions during inter-procedural
41 
42 public:
45  : type_(BBLOCK), bblock_(bblock), parentFunction_(parentFunction), inliningId_(inliningId) {
46  ASSERT_not_null(bblock);
47  }
48 
50  explicit DfCfgVertex(const Function::Ptr &function, const Function::Ptr &parentFunction, size_t inliningId)
51  : type_(FAKED_CALL), callee_(function), parentFunction_(parentFunction), inliningId_(inliningId) {}
52 
55  : type_(type), parentFunction_(parentFunction), inliningId_(inliningId) {
56  ASSERT_require2(BBLOCK!=type && FAKED_CALL!=type, "use a different constructor");
57  }
58 
62  Type type() const { return type_; }
63 
68  const BasicBlock::Ptr& bblock() const { return bblock_; }
69 
71  const Function::Ptr& callee() const { return callee_; }
72 
78  Function::Ptr parentFunction() const { return parentFunction_; }
79 
85  size_t inliningId() const { return inliningId_; }
86 };
87 
110 
117 public:
118  virtual ~InterproceduralPredicate() {}
119  virtual bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) = 0;
120 };
121 
124 public:
125  bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) ROSE_OVERRIDE {
126  return false;
127  }
128 };
129 extern NotInterprocedural NOT_INTERPROCEDURAL;
130 
132 std::vector<SgAsmInstruction*> vertexUnpacker(const DfCfgVertex&);
133 
140 DfCfg buildDfCfg(const Partitioner&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
141  InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);
142 
144 void dumpDfCfg(std::ostream&, const DfCfg&);
145 
152 
158 template<class DfCfg>
160 findReturnVertex(DfCfg &dfCfg) {
161  using namespace Sawyer::Container;
162  typename GraphTraits<DfCfg>::VertexIterator retval = dfCfg.vertices().end();
163  for (typename GraphTraits<DfCfg>::VertexIterator vi = dfCfg.vertices().begin(); vi != dfCfg.vertices().end(); ++vi) {
164  if (vi->value().type() == DfCfgVertex::FUNCRET) {
165  ASSERT_require(retval == dfCfg.vertices().end());
166  retval = vi;
167  }
168  }
169  return retval;
170 }
171 
173 // Transfer function
174 //
175 // The transfer function is reponsible for taking a CFG vertex and an initial state and producing the next state, the final
176 // state for that vertex. Users can use whatever transfer function they want; this one is based on the DfCfg and an
177 // instruction semantics state.
179 
183  BaseSemantics::SValuePtr callRetAdjustment_;
184  const RegisterDescriptor STACK_POINTER_REG;
185  const RegisterDescriptor INSN_POINTER_REG;
186  CallingConvention::DefinitionPtr defaultCallingConvention_;
187 public:
192  : cpu_(cpu), STACK_POINTER_REG(cpu->stackPointerRegister()), INSN_POINTER_REG(cpu->instructionPointerRegister()) {
193  size_t adjustment = STACK_POINTER_REG.get_nbits() / 8; // sizeof return address on top of stack
194  callRetAdjustment_ = cpu->number_(STACK_POINTER_REG.get_nbits(), adjustment);
195  }
196 
199 
203  BaseSemantics::DispatcherPtr cpu() const { return cpu_; }
204 
213  CallingConvention::DefinitionPtr defaultCallingConvention() const { return defaultCallingConvention_; }
214  void defaultCallingConvention(const CallingConvention::DefinitionPtr &x) { defaultCallingConvention_ = x; }
217  // Required by data-flow engine
218  std::string printState(const BaseSemantics::StatePtr &state);
219 
220  // Required by data-flow engine: compute new output state given a vertex and input state.
221  BaseSemantics::StatePtr operator()(const DfCfg&, size_t vertexId, const BaseSemantics::StatePtr &incomingState) const;
222 };
223 
229 
232 
245  const BaseSemantics::SValuePtr &initialStackPointer);
246 
252  const BaseSemantics::SValuePtr &initialStackPointer);
253 
260  const BaseSemantics::SValuePtr &initialStackPointer);
261 
266 std::vector<AbstractLocation> findGlobalVariables(const BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes);
267 
268 
269 
270 } // namespace
271 } // namespace
272 } // namespace
273 } // namespace
274 
275 #endif
Rose::BinaryAnalysis::DataFlow::Engine< DfCfg, BaseSemantics::StatePtr, TransferFunction, MergeFunction > Engine
Data-Flow engine.
Definition: DataFlow.h:231
Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction
Data-flow merge function.
Definition: DataFlow.h:228
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:123
BaseSemantics::DispatcherPtr cpu() const
Property: Virtual CPU.
Definition: DataFlow.h:203
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:68
Sawyer::Container::GraphTraits< DfCfg >::VertexIterator findReturnVertex(DfCfg &dfCfg)
Find the return vertex.
Definition: DataFlow.h:160
std::vector< StackVariable > StackVariables
Multiple stack variables.
Basic merge operation for instruction semantics.
DfCfgVertex(Type type, const Function::Ptr &parentFunction, size_t inliningId)
Construct a vertex of specified type that takes no auxiliary data.
Definition: DataFlow.h:54
void defaultCallingConvention(const CallingConvention::DefinitionPtr &x)
Property: Default calling convention.
Definition: DataFlow.h:214
DfCfgVertex(const Function::Ptr &function, const Function::Ptr &parentFunction, size_t inliningId)
Construct a faked call vertex.
Definition: DataFlow.h:50
Function::Ptr parentFunction() const
Function owning this vertex.
Definition: DataFlow.h:78
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1462
Main namespace for the ROSE library.
Describes (part of) a physical CPU register.
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:191
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:116
StackVariables findLocalVariables(const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known local variables.
size_t inliningId() const
Inlining invocation number.
Definition: DataFlow.h:85
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 BasicBlock::Ptr &bblock, const Function::Ptr &parentFunction, size_t inliningId)
Construct a basic block vertex.
Definition: DataFlow.h:44
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:293
Sawyer::Container::Graph< DfCfgVertex > DfCfg
Control flow graph used by data-flow analysis.
Definition: DataFlow.h:109
const Function::Ptr & callee() const
Function represented by faked call.
Definition: DataFlow.h:71
CallingConvention::DefinitionPtr defaultCallingConvention() const
Property: Default calling convention.
Definition: DataFlow.h:213