ROSE  0.11.109.0
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 
6 #include <Rose/BinaryAnalysis/DataFlow.h>
7 #include <Rose/BinaryAnalysis/Partitioner2/BasicBlock.h>
8 #include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
9 #include <Rose/BinaryAnalysis/Partitioner2/Function.h>
10 #include <Sawyer/Graph.h>
11 
12 namespace Rose {
13 namespace BinaryAnalysis {
14 namespace Partitioner2 {
15 
17 namespace DataFlow {
18 
20 // Control Flow Graph
22 
26 class DfCfgVertex {
27 public:
29  enum Type {
34  };
35 
36 private:
37  Type type_;
38  BasicBlock::Ptr bblock_; // attached to BBLOCK vertices
39  Function::Ptr callee_; // function represented by FAKED_CALL
40  Function::Ptr parentFunction_; // function "owning" this vertex
41  size_t inliningId_; // invocation ID for inlining functions during inter-procedural
42 
43 public:
46  : type_(BBLOCK), bblock_(bblock), parentFunction_(parentFunction), inliningId_(inliningId) {
47  ASSERT_not_null(bblock);
48  }
49 
51  explicit DfCfgVertex(const Function::Ptr &function, const Function::Ptr &parentFunction, size_t inliningId)
52  : type_(FAKED_CALL), callee_(function), parentFunction_(parentFunction), inliningId_(inliningId) {}
53 
56  : type_(type), parentFunction_(parentFunction), inliningId_(inliningId) {
57  ASSERT_require2(BBLOCK!=type && FAKED_CALL!=type, "use a different constructor");
58  }
59 
63  Type type() const { return type_; }
64 
69  const BasicBlock::Ptr& bblock() const { return bblock_; }
70 
72  const Function::Ptr& callee() const { return callee_; }
73 
79  Function::Ptr parentFunction() const { return parentFunction_; }
80 
86  size_t inliningId() const { return inliningId_; }
87 
92 };
93 
116 
123 public:
124  virtual ~InterproceduralPredicate() {}
125  virtual bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) = 0;
126 };
127 
130 public:
131  bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t /*depth*/) override {
132  return false;
133  }
134 };
135 extern NotInterprocedural NOT_INTERPROCEDURAL;
136 
138 std::vector<SgAsmInstruction*> vertexUnpacker(const DfCfgVertex&);
139 
146 DfCfg buildDfCfg(const Partitioner&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
147  InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);
148 
150 void dumpDfCfg(std::ostream&, const DfCfg&);
151 
158 
164 template<class DfCfg>
166 findReturnVertex(DfCfg &dfCfg) {
167  using namespace Sawyer::Container;
168  typename GraphTraits<DfCfg>::VertexIterator retval = dfCfg.vertices().end();
169  for (typename GraphTraits<DfCfg>::VertexIterator vi = dfCfg.vertices().begin(); vi != dfCfg.vertices().end(); ++vi) {
170  if (vi->value().type() == DfCfgVertex::FUNCRET) {
171  ASSERT_require(retval == dfCfg.vertices().end());
172  retval = vi;
173  }
174  }
175  return retval;
176 }
177 
179 // Transfer function
180 //
181 // The transfer function is reponsible for taking a CFG vertex and an initial state and producing the next state, the final
182 // state for that vertex. Users can use whatever transfer function they want; this one is based on the DfCfg and an
183 // instruction semantics state.
185 
189  BaseSemantics::SValuePtr callRetAdjustment_;
190  const RegisterDescriptor STACK_POINTER_REG;
191  const RegisterDescriptor INSN_POINTER_REG;
192  CallingConvention::DefinitionPtr defaultCallingConvention_;
193 public:
198  : cpu_(cpu), STACK_POINTER_REG(cpu->stackPointerRegister()), INSN_POINTER_REG(cpu->instructionPointerRegister()) {
199  size_t adjustment = STACK_POINTER_REG.nBits() / 8; // sizeof return address on top of stack
200  callRetAdjustment_ = cpu->number_(STACK_POINTER_REG.nBits(), adjustment);
201  }
202 
205 
209  BaseSemantics::DispatcherPtr cpu() const { return cpu_; }
210 
219  CallingConvention::DefinitionPtr defaultCallingConvention() const { return defaultCallingConvention_; }
220  void defaultCallingConvention(const CallingConvention::DefinitionPtr &x) { defaultCallingConvention_ = x; }
223  // Required by data-flow engine
224  std::string toString(const BaseSemantics::StatePtr &state);
225 
226  // Required by data-flow engine: compute new output state given a vertex and input state.
227  BaseSemantics::StatePtr operator()(const DfCfg&, size_t vertexId, const BaseSemantics::StatePtr &incomingState) const;
228 };
229 
235 
238 
251  const BaseSemantics::SValuePtr &initialStackPointer);
252 
258  const BaseSemantics::SValuePtr &initialStackPointer);
259 
266  const BaseSemantics::SValuePtr &initialStackPointer);
267 
272 std::vector<AbstractLocation> findGlobalVariables(const BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes);
273 
274 
275 
276 } // namespace
277 } // namespace
278 } // namespace
279 } // namespace
280 
281 #endif
282 #endif
Rose::BinaryAnalysis::DataFlow::Engine< DfCfg, BaseSemantics::StatePtr, TransferFunction, MergeFunction > Engine
Data-Flow engine.
Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction
Data-flow merge function.
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.
BaseSemantics::DispatcherPtr cpu() const
Property: Virtual CPU.
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.
Sawyer::Container::GraphTraits< DfCfg >::VertexIterator findReturnVertex(DfCfg &dfCfg)
Find the return vertex.
Basic merge operation for instruction semantics.
Definition: DataFlow.h:215
DfCfgVertex(Type type, const Function::Ptr &parentFunction, size_t inliningId)
Construct a vertex of specified type that takes no auxiliary data.
void defaultCallingConvention(const CallingConvention::DefinitionPtr &x)
Property: Default calling convention.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Variables::StackVariables findStackVariables(const FunctionPtr &function, const BaseSemantics::RiscOperatorsPtr &ops, const BaseSemantics::SValuePtr &initialStackPointer)
Returns the list of all known stack variables.
Sawyer::Optional< rose_addr_t > address() const
Virtual address of vertex.
DfCfgVertex(const Function::Ptr &function, const Function::Ptr &parentFunction, size_t inliningId)
Construct a faked call vertex.
Function::Ptr parentFunction() const
Function owning this vertex.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1460
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.
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
TransferFunction(const BaseSemantics::DispatcherPtr &cpu)
Construct from a CPU.
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
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:35
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.
size_t inliningId() const
Inlining invocation number.
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.
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.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:294
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.
const Function::Ptr & callee() const
Function represented by faked call.
CallingConvention::DefinitionPtr defaultCallingConvention() const
Property: Default calling convention.