ROSE  0.10.13.0
DataFlow.h
1 #ifndef ROSE_Partitioner2_DataFlow_H
2 #define ROSE_Partitioner2_DataFlow_H
3 
4 #include <rosePublicConfig.h>
5 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
6 
7 #include <BinaryDataFlow.h>
8 #include <BinaryStackVariable.h>
9 #include <Partitioner2/BasicBlock.h>
10 #include <Partitioner2/ControlFlowGraph.h>
11 #include <Partitioner2/Function.h>
12 #include <Sawyer/Graph.h>
13 
14 namespace Rose {
15 namespace BinaryAnalysis {
16 namespace Partitioner2 {
17 
19 namespace DataFlow {
20 
22 // Control Flow Graph
24 
28 class DfCfgVertex {
29 public:
31  enum Type {
36  };
37 
38 private:
39  Type type_;
40  BasicBlock::Ptr bblock_; // attached to BBLOCK vertices
41  Function::Ptr callee_; // function represented by FAKED_CALL
42  Function::Ptr parentFunction_; // function "owning" this vertex
43  size_t inliningId_; // invocation ID for inlining functions during inter-procedural
44 
45 public:
48  : type_(BBLOCK), bblock_(bblock), parentFunction_(parentFunction), inliningId_(inliningId) {
49  ASSERT_not_null(bblock);
50  }
51 
53  explicit DfCfgVertex(const Function::Ptr &function, const Function::Ptr &parentFunction, size_t inliningId)
54  : type_(FAKED_CALL), callee_(function), parentFunction_(parentFunction), inliningId_(inliningId) {}
55 
58  : type_(type), parentFunction_(parentFunction), inliningId_(inliningId) {
59  ASSERT_require2(BBLOCK!=type && FAKED_CALL!=type, "use a different constructor");
60  }
61 
65  Type type() const { return type_; }
66 
71  const BasicBlock::Ptr& bblock() const { return bblock_; }
72 
74  const Function::Ptr& callee() const { return callee_; }
75 
81  Function::Ptr parentFunction() const { return parentFunction_; }
82 
88  size_t inliningId() const { return inliningId_; }
89 };
90 
113 
120 public:
121  virtual ~InterproceduralPredicate() {}
122  virtual bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) = 0;
123 };
124 
127 public:
128  bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) ROSE_OVERRIDE {
129  return false;
130  }
131 };
132 extern NotInterprocedural NOT_INTERPROCEDURAL;
133 
135 std::vector<SgAsmInstruction*> vertexUnpacker(const DfCfgVertex&);
136 
143 DfCfg buildDfCfg(const Partitioner&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
144  InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);
145 
147 void dumpDfCfg(std::ostream&, const DfCfg&);
148 
155 
161 template<class DfCfg>
163 findReturnVertex(DfCfg &dfCfg) {
164  using namespace Sawyer::Container;
165  typename GraphTraits<DfCfg>::VertexIterator retval = dfCfg.vertices().end();
166  for (typename GraphTraits<DfCfg>::VertexIterator vi = dfCfg.vertices().begin(); vi != dfCfg.vertices().end(); ++vi) {
167  if (vi->value().type() == DfCfgVertex::FUNCRET) {
168  ASSERT_require(retval == dfCfg.vertices().end());
169  retval = vi;
170  }
171  }
172  return retval;
173 }
174 
176 // Transfer function
177 //
178 // The transfer function is reponsible for taking a CFG vertex and an initial state and producing the next state, the final
179 // state for that vertex. Users can use whatever transfer function they want; this one is based on the DfCfg and an
180 // instruction semantics state.
182 
186  BaseSemantics::SValuePtr callRetAdjustment_;
187  const RegisterDescriptor STACK_POINTER_REG;
188  const RegisterDescriptor INSN_POINTER_REG;
189  CallingConvention::DefinitionPtr defaultCallingConvention_;
190 public:
195  : cpu_(cpu), STACK_POINTER_REG(cpu->stackPointerRegister()), INSN_POINTER_REG(cpu->instructionPointerRegister()) {
196  size_t adjustment = STACK_POINTER_REG.nBits() / 8; // sizeof return address on top of stack
197  callRetAdjustment_ = cpu->number_(STACK_POINTER_REG.nBits(), adjustment);
198  }
199 
202 
206  BaseSemantics::DispatcherPtr cpu() const { return cpu_; }
207 
216  CallingConvention::DefinitionPtr defaultCallingConvention() const { return defaultCallingConvention_; }
217  void defaultCallingConvention(const CallingConvention::DefinitionPtr &x) { defaultCallingConvention_ = x; }
220  // Required by data-flow engine
221  std::string toString(const BaseSemantics::StatePtr &state);
222 
223  // Required by data-flow engine: compute new output state given a vertex and input state.
224  BaseSemantics::StatePtr operator()(const DfCfg&, size_t vertexId, const BaseSemantics::StatePtr &incomingState) const;
225 };
226 
232 
235 
248  const BaseSemantics::SValuePtr &initialStackPointer);
249 
255  const BaseSemantics::SValuePtr &initialStackPointer);
256 
263  const BaseSemantics::SValuePtr &initialStackPointer);
264 
269 std::vector<AbstractLocation> findGlobalVariables(const BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes);
270 
271 
272 
273 } // namespace
274 } // namespace
275 } // namespace
276 } // namespace
277 
278 #endif
279 #endif
Rose::BinaryAnalysis::DataFlow::Engine< DfCfg, BaseSemantics::StatePtr, TransferFunction, MergeFunction > Engine
Data-Flow engine.
Definition: DataFlow.h:234
Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction
Data-flow merge function.
Definition: DataFlow.h:231
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
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:126
BaseSemantics::DispatcherPtr cpu() const
Property: Virtual CPU.
Definition: DataFlow.h:206
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
size_t nBits() const
Property: Size in bits.
Function::Ptr bestSummaryFunction(const FunctionSet &functions)
Choose best function for data-flow summary vertex.
const BasicBlock::Ptr & bblock() const
Basic block.
Definition: DataFlow.h:71
Sawyer::Container::GraphTraits< DfCfg >::VertexIterator findReturnVertex(DfCfg &dfCfg)
Find the return vertex.
Definition: DataFlow.h:163
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:57
void defaultCallingConvention(const CallingConvention::DefinitionPtr &x)
Property: Default calling convention.
Definition: DataFlow.h:217
Variables::StackVariables findStackVariables(const FunctionPtr &function, const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known stack variables.
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
DfCfgVertex(const Function::Ptr &function, const Function::Ptr &parentFunction, size_t inliningId)
Construct a faked call vertex.
Definition: DataFlow.h:53
Function::Ptr parentFunction() const
Function owning this vertex.
Definition: DataFlow.h:81
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1442
Main namespace for the ROSE library.
Variables::StackVariables findFunctionArguments(const FunctionPtr &function, const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known function arguments.
TransferFunction(const BaseSemantics::DispatcherPtr &cpu)
Construct from a CPU.
Definition: DataFlow.h:194
CFG vertex for data-flow analysis.
Definition: DataFlow.h:28
Vertex represents returning to the caller.
Definition: DataFlow.h:34
DfCfg buildDfCfg(const Partitioner &, const ControlFlowGraph &, const ControlFlowGraph::ConstVertexIterator &startVertex, InterproceduralPredicate &predicate=NOT_INTERPROCEDURAL)
build a cfg useful for data-flow analysis.
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
Container classes that store user-defined values.
Definition: AddressMap.h:31
BaseSemantics::StatePtr initialState() const
Construct an initial state.
Describes (part of) a physical CPU register.
Predicate that decides when to use inter-procedural data-flow.
Definition: DataFlow.h:119
size_t inliningId() const
Inlining invocation number.
Definition: DataFlow.h:88
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: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:35
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:321
Variables::StackVariables findLocalVariables(const FunctionPtr &function, const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known local variables.
Sawyer::Container::Graph< DfCfgVertex > DfCfg
Control flow graph used by data-flow analysis.
Definition: DataFlow.h:112
const Function::Ptr & callee() const
Function represented by faked call.
Definition: DataFlow.h:74
CallingConvention::DefinitionPtr defaultCallingConvention() const
Property: Default calling convention.
Definition: DataFlow.h:216