ROSE  0.9.9.139
BinaryDataFlow.h
1 #ifndef ROSE_BinaryAnalysis_DataFlow_H
2 #define ROSE_BinaryAnalysis_DataFlow_H
3 
4 #include "DataFlowSemantics2.h"
5 #include "Diagnostics.h"
6 #include "SymbolicSemantics2.h"
7 
8 #include <boost/foreach.hpp>
9 #include <boost/lexical_cast.hpp>
10 #include <list>
11 #include <Sawyer/GraphTraversal.h>
12 #include <Sawyer/DistinctList.h>
13 #include <sstream>
14 #include <string>
15 #include <vector>
16 
17 namespace Rose {
18 namespace BinaryAnalysis {
19 
67 class DataFlow {
68 public:
75 
82 
84  typedef std::list<Variable> VariableList;
85 
92 
93 public:
95  class Exception: public std::runtime_error {
96  public:
97  explicit Exception(const std::string &s): std::runtime_error(s) {}
98  };
99 
101  class NotConverging: public Exception {
102  public:
103  explicit NotConverging(const std::string &s): Exception(s) {}
104  };
105 
106 private:
107  InstructionSemantics2::BaseSemantics::RiscOperatorsPtr userOps_; // operators (and state) provided by the user
108  InstructionSemantics2::DataFlowSemantics::RiscOperatorsPtr dfOps_; // data-flow operators (which point to user ops)
109  InstructionSemantics2::BaseSemantics::DispatcherPtr dispatcher_; // copy of user's dispatcher but with DataFlowSemantics
110  static Sawyer::Message::Facility mlog; // diagnostics for data-flow
112 
113 public:
120  init(userDispatcher);
121  }
122 
126  static void initDiagnostics();
127 
128 public:
137  Graph buildGraph(const std::vector<SgAsmInstruction*>&);
146  public:
147  typedef std::vector<SgAsmInstruction*> Instructions;
148  Instructions operator()(SgAsmInstruction *insn) { return Instructions(1, insn); }
149  Instructions operator()(SgAsmBlock *blk);
150  };
151 
152 public:
164  template<class CFG, class VertexUnpacker>
165  VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker) {
166  using namespace Diagnostics;
167  ASSERT_this();
168  ASSERT_require(startVertex < cfg.nVertices());
169  Stream mesg(mlog[WHERE] <<"buildGraphPerVertex startVertex=" <<startVertex);
170 
171  VertexFlowGraphs result;
172  result.insert(startVertex, buildGraph(vertexUnpacker(cfg.findVertex(startVertex)->value())));
173  std::vector<InstructionSemantics2::BaseSemantics::StatePtr> postState(cfg.nVertices()); // user-defined states
174  postState[startVertex] = userOps_->currentState();
175 
177  for (Traversal t(cfg, cfg.findVertex(startVertex)); t; ++t) {
178  typename CFG::ConstVertexIterator source = t->source();
179  typename CFG::ConstVertexIterator target = t->target();
180  InstructionSemantics2::BaseSemantics::StatePtr state = postState[target->id()];
181  if (state==NULL) {
182  ASSERT_not_null(postState[source->id()]);
183  state = postState[target->id()] = postState[source->id()]->clone();
184  userOps_->currentState(state);
185  std::vector<SgAsmInstruction*> insns = vertexUnpacker(target->value());
186  result.insert(target->id(), buildGraph(insns));
187  }
188  }
189 
190  mesg <<"; processed " <<StringUtility::plural(result.size(), "vertices", "vertex") <<"\n";
191  return result;
192  }
193 
194  template<class CFG>
195  VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex) {
196  return buildGraphPerVertex(cfg, startVertex, DefaultVertexUnpacker());
197  }
204  VariableList getUniqueVariables(const VertexFlowGraphs&);
205 
211  public:
213  explicit SemanticsMerge(const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu): ops_(cpu->get_operators()) {}
214 
215  bool operator()(InstructionSemantics2::BaseSemantics::StatePtr &dst /*in,out*/,
217  struct T {
221  : ops(ops), state(ops->currentState()) {}
222  ~T() { ops->currentState(state); }
223  } t(ops_);
224  if (!dst) {
225  dst = src->clone();
226  return true;
227  } else {
228  ops_->currentState(src);
229  return dst->merge(src, ops_.get());
230  }
231  }
232  };
233 
282  template<class CFG, class State, class TransferFunction, class MergeFunction>
283  class Engine {
284  public:
285  typedef std::vector<State> VertexStates;
287  private:
288  const CFG &cfg_;
289  TransferFunction &xfer_;
290  MergeFunction merge_;
291  VertexStates incomingState_; // incoming data-flow state per CFG vertex ID
292  VertexStates outgoingState_; // outgoing data-flow state per CFG vertex ID
294  WorkList workList_; // CFG vertex IDs to be visited, last in first out w/out duplicates
295  size_t maxIterations_; // max number of iterations to allow
296  size_t nIterations_; // number of iterations since last reset
297 
298  public:
304  Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge = MergeFunction())
305  : cfg_(cfg), xfer_(xfer), merge_(merge), maxIterations_(-1), nIterations_(0) {}
306 
311  const CFG &cfg() const {
312  return cfg_;
313  }
314 
316  void reset(State initialState = State()) {
317  ASSERT_this();
318  incomingState_.clear();
319  incomingState_.resize(cfg_.nVertices(), initialState);
320  outgoingState_.clear();
321  outgoingState_.resize(cfg_.nVertices(), initialState);
322  workList_.clear();
323  nIterations_ = 0;
324  }
325 
332  size_t maxIterations() const { return maxIterations_; }
333  void maxIterations(size_t n) { maxIterations_ = n; }
339  size_t nIterations() const { return nIterations_; }
340 
346  using namespace Diagnostics;
347  if (!workList_.isEmpty()) {
348  if (++nIterations_ > maxIterations_) {
349  throw NotConverging("data-flow max iterations reached"
350  " (max=" + StringUtility::numberToString(maxIterations_) + ")");
351  }
352  size_t cfgVertexId = workList_.popFront();
353  if (mlog[DEBUG]) {
354  mlog[DEBUG] <<"runOneIteration: vertex #" <<cfgVertexId <<"\n";
355  mlog[DEBUG] <<" remaining worklist is {";
356  BOOST_FOREACH (size_t id, workList_.items())
357  mlog[DEBUG] <<" " <<id;
358  mlog[DEBUG] <<" }\n";
359  }
360 
361  ASSERT_require2(cfgVertexId < cfg_.nVertices(),
362  "vertex " + boost::lexical_cast<std::string>(cfgVertexId) + " must be valid within CFG");
363  typename CFG::ConstVertexIterator vertex = cfg_.findVertex(cfgVertexId);
364  State state = incomingState_[cfgVertexId];
365  if (mlog[DEBUG]) {
366  mlog[DEBUG] <<" incoming state for vertex #" <<cfgVertexId
367  <<StringUtility::prefixLines(xfer_.printState(state), " ", false) <<"\n";
368  }
369 
370  state = outgoingState_[cfgVertexId] = xfer_(cfg_, cfgVertexId, state);
371  if (mlog[DEBUG]) {
372  mlog[DEBUG] <<" outgoing state for vertex #" <<cfgVertexId
373  <<StringUtility::prefixLines(xfer_.printState(state), " ", false) <<"\n";
374  }
375 
376  // Outgoing state must be merged into the incoming states for the CFG successors. Any such incoming state that
377  // is modified as a result will have its CFG vertex added to the work list.
378  SAWYER_MESG(mlog[DEBUG]) <<" forwarding vertex #" <<cfgVertexId <<" output state to "
379  <<StringUtility::plural(vertex->nOutEdges(), "vertices", "vertex") <<"\n";
380  BOOST_FOREACH (const typename CFG::Edge &edge, vertex->outEdges()) {
381  size_t nextVertexId = edge.target()->id();
382  if (merge_(incomingState_[nextVertexId], state)) {
383  if (mlog[DEBUG]) {
384  mlog[DEBUG] <<" merged with vertex #" <<nextVertexId <<" (which changed as a result)\n";
385  mlog[DEBUG] <<" merge state is: "
386  <<StringUtility::prefixLines(xfer_.printState(incomingState_[nextVertexId]),
387  " ", false) <<"\n";
388  }
389  workList_.pushBack(nextVertexId);
390  } else {
391  SAWYER_MESG(mlog[DEBUG]) <<" merged with vertex #" <<nextVertexId <<" (no change)\n";
392  }
393  }
394  }
395  return !workList_.isEmpty();
396  }
397 
399  void insertStartingVertex(size_t startVertexId, const State &initialState) {
400  incomingState_[startVertexId] = initialState;
401  workList_.pushBack(startVertexId);
402  }
403 
410  while (runOneIteration()) /*void*/;
411  }
412 
416  void runToFixedPoint(size_t startVertexId, const State &initialState) {
417  reset();
418  insertStartingVertex(startVertexId, initialState);
419  while (runOneIteration()) /*void*/;
420  }
421 
426  State getInitialState(size_t cfgVertexId) const {
427  return incomingState_[cfgVertexId];
428  }
429 
431  void setInitialState(size_t cfgVertexId, State state) {
432  incomingState_[cfgVertexId] = state;
433  }
434 
439  State getFinalState(size_t cfgVertexId) const {
440  return outgoingState_[cfgVertexId];
441  }
442 
447  const VertexStates& getInitialStates() const {
448  return incomingState_;
449  }
450 
455  const VertexStates& getFinalStates() const {
456  return outgoingState_;
457  }
458  };
459 };
460 
461 } // namespace
462 } // namespace
463 
464 #endif
size_t nIterations() const
Number of iterations run.
Sawyer::Container::Map< size_t, Graph > VertexFlowGraphs
Map from CFG vertex to data-flow graph.
ROSE_UTIL_API std::string numberToString(long long)
Convert an integer to a string.
State getFinalState(size_t cfgVertexId) const
Return the outgoing state for the specified CFG vertex.
Instruction basic block.
InstructionSemantics2::DataFlowSemantics::DataFlowGraph Graph
Data-flow graph.
Basic merge operation for instruction semantics.
Base class for machine instructions.
Collection of streams.
Definition: Message.h:1579
const CFG & cfg() const
Data-flow control flow graph.
AbstractLocation Variable
Variable participating in data flow.
std::vector< State > VertexStates
Data-flow states indexed by vertex ID.
Depth-first, forward traversal for edges.
static void initDiagnostics()
Initialize diagnostics.
std::list< Variable > VariableList
List of variables.
const VertexStates & getInitialStates() const
All incoming states.
const VertexStates & getFinalStates() const
All outgoing states.
DataFlow(const InstructionSemantics2::BaseSemantics::DispatcherPtr &userDispatcher)
Constructor.
Main namespace for the ROSE library.
bool isEmpty() const
Determines whether list is empty.
Definition: DistinctList.h:66
Graph buildGraph(const std::vector< SgAsmInstruction * > &)
Compute data-flow.
ROSE_UTIL_API std::string prefixLines(const std::string &lines, const std::string &prefix, bool prefixAtFront=true, bool prefixAtBack=false)
Insert a prefix string before every line.
void reset(State initialState=State())
Reset engine to initial state.
void runToFixedPoint()
Run data-flow until it reaches a fixed point.
VariableList getUniqueVariables(const VertexFlowGraphs &)
Get list of unique variables.
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.
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex)
Compute data-flow per CFG vertex.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Exceptions when a fixed point is not reached.
const Items & items() const
Return all items as a list.
Definition: DistinctList.h:181
void pushBack(const Item &item)
Insert item at back of list if distinct.
Definition: DistinctList.h:133
bool runOneIteration()
Runs one iteration.
size_t maxIterations() const
Max number of iterations to allow.
Item popFront()
Return and erase item at front of list.
Definition: DistinctList.h:145
void setInitialState(size_t cfgVertexId, State state)
Set the initial state for the specified CFG vertex.
Data-flow exception base class.
void insertStartingVertex(size_t startVertexId, const State &initialState)
Add a starting vertex.
Various tools for data-flow analysis.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:530
Functor to return instructions for a cfg vertex.
std::string plural(T n, const std::string &plural_word, const std::string &singular_word="")
Helpful way to print singular or plural words.
void maxIterations(size_t n)
Max number of iterations to allow.
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker)
Compute data-flow per CFG vertex.
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:322
Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge=MergeFunction())
Constructor.
void clear()
Clear the list.
Definition: DistinctList.h:58
void runToFixedPoint(size_t startVertexId, const State &initialState)
Add starting point and run to fixed point.
State getInitialState(size_t cfgVertexId) const
Return the incoming state for the specified CFG vertex.