ROSE  0.11.83.1
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 };
88 
111 
118 public:
119  virtual ~InterproceduralPredicate() {}
120  virtual bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) = 0;
121 };
122 
125 public:
126  bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) override {
127  return false;
128  }
129 };
130 extern NotInterprocedural NOT_INTERPROCEDURAL;
131 
133 std::vector<SgAsmInstruction*> vertexUnpacker(const DfCfgVertex&);
134 
141 DfCfg buildDfCfg(const Partitioner&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
142  InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);
143 
145 void dumpDfCfg(std::ostream&, const DfCfg&);
146 
153 
159 template<class DfCfg>
161 findReturnVertex(DfCfg &dfCfg) {
162  using namespace Sawyer::Container;
163  typename GraphTraits<DfCfg>::VertexIterator retval = dfCfg.vertices().end();
164  for (typename GraphTraits<DfCfg>::VertexIterator vi = dfCfg.vertices().begin(); vi != dfCfg.vertices().end(); ++vi) {
165  if (vi->value().type() == DfCfgVertex::FUNCRET) {
166  ASSERT_require(retval == dfCfg.vertices().end());
167  retval = vi;
168  }
169  }
170  return retval;
171 }
172 
174 // Transfer function
175 //
176 // The transfer function is reponsible for taking a CFG vertex and an initial state and producing the next state, the final
177 // state for that vertex. Users can use whatever transfer function they want; this one is based on the DfCfg and an
178 // instruction semantics state.
180 
184  BaseSemantics::SValuePtr callRetAdjustment_;
185  const RegisterDescriptor STACK_POINTER_REG;
186  const RegisterDescriptor INSN_POINTER_REG;
187  CallingConvention::DefinitionPtr defaultCallingConvention_;
188 public:
193  : cpu_(cpu), STACK_POINTER_REG(cpu->stackPointerRegister()), INSN_POINTER_REG(cpu->instructionPointerRegister()) {
194  size_t adjustment = STACK_POINTER_REG.nBits() / 8; // sizeof return address on top of stack
195  callRetAdjustment_ = cpu->number_(STACK_POINTER_REG.nBits(), adjustment);
196  }
197 
200 
204  BaseSemantics::DispatcherPtr cpu() const { return cpu_; }
205 
214  CallingConvention::DefinitionPtr defaultCallingConvention() const { return defaultCallingConvention_; }
215  void defaultCallingConvention(const CallingConvention::DefinitionPtr &x) { defaultCallingConvention_ = x; }
218  // Required by data-flow engine
219  std::string toString(const BaseSemantics::StatePtr &state);
220 
221  // Required by data-flow engine: compute new output state given a vertex and input state.
222  BaseSemantics::StatePtr operator()(const DfCfg&, size_t vertexId, const BaseSemantics::StatePtr &incomingState) const;
223 };
224 
230 
233 
246  const BaseSemantics::SValuePtr &initialStackPointer);
247 
253  const BaseSemantics::SValuePtr &initialStackPointer);
254 
261  const BaseSemantics::SValuePtr &initialStackPointer);
262 
267 std::vector<AbstractLocation> findGlobalVariables(const BaseSemantics::RiscOperatorsPtr &ops, size_t wordNBytes);
268 
269 
270 
271 } // namespace
272 } // namespace
273 } // namespace
274 } // namespace
275 
276 #endif
277 #endif
Rose::BinaryAnalysis::DataFlow::Engine< DfCfg, BaseSemantics::StatePtr, TransferFunction, MergeFunction > Engine
Data-Flow engine.
Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction
Data-flow merge function.
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.
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:211
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.
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.
Function::Ptr parentFunction() const
Function owning this vertex.
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.
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: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:289
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.