ROSE  0.11.98.0
DataFlow.h
1 #ifndef ROSE_BinaryAnalysis_DataFlow_H
2 #define ROSE_BinaryAnalysis_DataFlow_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/InstructionSemantics/DataFlowSemantics.h>
7 #include <Rose/Diagnostics.h>
8 #include <Rose/Exception.h>
9 #include <Rose/BinaryAnalysis/InstructionSemantics/SymbolicSemantics.h>
10 
11 #include <boost/lexical_cast.hpp>
12 #include <list>
13 #include <Sawyer/GraphTraversal.h>
14 #include <Sawyer/DistinctList.h>
15 #include <sstream>
16 #include <string>
17 #include <vector>
18 
19 namespace Rose {
20 namespace BinaryAnalysis {
21 
69 class DataFlow {
70 public:
77 
84 
86  typedef std::list<Variable> VariableList;
87 
94 
95 public:
97  class Exception: public Rose::Exception {
98  public:
99  explicit Exception(const std::string &s): Rose::Exception(s) {}
100  };
101 
103  class NotConverging: public Exception {
104  public:
105  explicit NotConverging(const std::string &s): Exception(s) {}
106  };
107 
108 private:
109  InstructionSemantics::BaseSemantics::RiscOperatorsPtr userOps_; // operators (and state) provided by the user
110  InstructionSemantics::DataFlowSemantics::RiscOperatorsPtr dfOps_; // data-flow operators (which point to user ops)
111  InstructionSemantics::BaseSemantics::DispatcherPtr dispatcher_; // copy of user's dispatcher but with DataFlowSemantics
112 
113 public:
114  static Sawyer::Message::Facility mlog; // diagnostics for data-flow
115 
116 public:
123  init(userDispatcher);
124  }
125 
129  static void initDiagnostics();
130 
131 private:
133 
134 public:
143  Graph buildGraph(const std::vector<SgAsmInstruction*>&);
152  public:
153  typedef std::vector<SgAsmInstruction*> Instructions;
154  Instructions operator()(SgAsmInstruction *insn) { return Instructions(1, insn); }
155  Instructions operator()(SgAsmBlock *blk);
156  };
157 
158 public:
170  template<class CFG, class VertexUnpacker>
171  VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker) {
172  using namespace Diagnostics;
173  ASSERT_this();
174  ASSERT_require(startVertex < cfg.nVertices());
175  Stream mesg(mlog[WHERE] <<"buildGraphPerVertex startVertex=" <<startVertex);
176 
177  VertexFlowGraphs result;
178  result.insert(startVertex, buildGraph(vertexUnpacker(cfg.findVertex(startVertex)->value())));
179  std::vector<InstructionSemantics::BaseSemantics::StatePtr> postState(cfg.nVertices()); // user-defined states
180  postState[startVertex] = userOps_->currentState();
181 
183  for (Traversal t(cfg, cfg.findVertex(startVertex)); t; ++t) {
184  typename CFG::ConstVertexIterator source = t->source();
185  typename CFG::ConstVertexIterator target = t->target();
186  InstructionSemantics::BaseSemantics::StatePtr state = postState[target->id()];
187  if (state==NULL) {
188  ASSERT_not_null(postState[source->id()]);
189  state = postState[target->id()] = postState[source->id()]->clone();
190  userOps_->currentState(state);
191  std::vector<SgAsmInstruction*> insns = vertexUnpacker(target->value());
192  result.insert(target->id(), buildGraph(insns));
193  }
194  }
195 
196  mesg <<"; processed " <<StringUtility::plural(result.size(), "vertices", "vertex") <<"\n";
197  return result;
198  }
199 
200  template<class CFG>
201  VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex) {
202  return buildGraphPerVertex(cfg, startVertex, DefaultVertexUnpacker());
203  }
210  VariableList getUniqueVariables(const VertexFlowGraphs&);
211 
217  public:
219  explicit SemanticsMerge(const InstructionSemantics::BaseSemantics::DispatcherPtr &cpu): ops_(cpu->operators()) {}
220 
221  bool operator()(InstructionSemantics::BaseSemantics::StatePtr &dst /*in,out*/,
223  struct PreserveCurrentState {
226  PreserveCurrentState(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops)
227  : ops(ops), state(ops->currentState()) {}
228  ~PreserveCurrentState() { ops->currentState(state); }
229  } t(ops_);
230 
231  if (!dst) {
232  dst = src->clone();
233  return true;
234  } else {
235  ops_->currentState(src);
236  return dst->merge(src, ops_.get());
237  }
238  }
239  };
240 
245  template<class CFG, class State>
247  public:
248  bool operator()(const CFG&, const typename CFG::Edge&, const State&, const State&) {
249  return true;
250  }
251  };
252 
310  template<class CFG, class State, class TransferFunction, class MergeFunction,
311  class PathFeasibility = PathAlwaysFeasible<CFG, State> >
312  class Engine {
313  public:
314  typedef std::vector<State> VertexStates;
316  private:
317  std::string name_; // optional name for debugging
318  const CFG &cfg_;
319  TransferFunction &xfer_;
320  MergeFunction merge_;
321  VertexStates incomingState_; // incoming data-flow state per CFG vertex ID
322  VertexStates outgoingState_; // outgoing data-flow state per CFG vertex ID
324  WorkList workList_; // CFG vertex IDs to be visited, last in first out w/out duplicates
325  size_t maxIterations_; // max number of iterations to allow
326  size_t nIterations_; // number of iterations since last reset
327  PathFeasibility isFeasible_; // predicate to test path feasibility
328 
329  public:
335  Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge = MergeFunction(),
336  PathFeasibility isFeasible = PathFeasibility())
337  : cfg_(cfg), xfer_(xfer), merge_(merge), maxIterations_(-1), nIterations_(0), isFeasible_(isFeasible) {
338  reset();
339  }
340 
345  const CFG &cfg() const {
346  return cfg_;
347  }
348 
350  void reset(State initialState = State()) {
351  ASSERT_this();
352  incomingState_.clear();
353  incomingState_.resize(cfg_.nVertices(), initialState);
354  outgoingState_.clear();
355  outgoingState_.resize(cfg_.nVertices(), initialState);
356  workList_.clear();
357  nIterations_ = 0;
358  }
359 
365  const std::string& name() const { return name_; }
366  void name(const std::string &s) { name_ = s; }
370  std::string prefix() const {
371  if (name_.empty()) {
372  return "";
373  } else {
374  return name_ + ": ";
375  }
376  }
377 
384  size_t maxIterations() const { return maxIterations_; }
385  void maxIterations(size_t n) { maxIterations_ = n; }
391  size_t nIterations() const { return nIterations_; }
392 
398  using namespace Diagnostics;
399  if (!workList_.isEmpty()) {
400  if (++nIterations_ > maxIterations_) {
401  throw NotConverging("data-flow max iterations reached"
402  " (max=" + StringUtility::numberToString(maxIterations_) + ")");
403  }
404  size_t cfgVertexId = workList_.popFront();
405  if (mlog[DEBUG]) {
406  mlog[DEBUG] <<prefix() <<"runOneIteration: vertex #" <<cfgVertexId <<"\n";
407  mlog[DEBUG] <<prefix() <<" remaining worklist is {";
408  for (size_t id: workList_.items())
409  mlog[DEBUG] <<" " <<id;
410  mlog[DEBUG] <<" }\n";
411  }
412 
413  ASSERT_require2(cfgVertexId < cfg_.nVertices(),
414  "vertex " + boost::lexical_cast<std::string>(cfgVertexId) + " must be valid within CFG");
415  typename CFG::ConstVertexIterator vertex = cfg_.findVertex(cfgVertexId);
416  State state = incomingState_[cfgVertexId];
417  if (mlog[DEBUG]) {
418  mlog[DEBUG] <<prefix() <<" incoming state for vertex #" <<cfgVertexId <<":\n"
419  <<StringUtility::prefixLines(xfer_.toString(state), prefix() + " ") <<"\n";
420  }
421 
422  state = outgoingState_[cfgVertexId] = xfer_(cfg_, cfgVertexId, state);
423  if (mlog[DEBUG]) {
424  mlog[DEBUG] <<prefix() <<" outgoing state for vertex #" <<cfgVertexId <<":\n"
425  <<StringUtility::prefixLines(xfer_.toString(state), prefix() + " ") <<"\n";
426  }
427 
428  // Outgoing state must be merged into the incoming states for the CFG successors. Any such incoming state that
429  // is modified as a result will have its CFG vertex added to the work list.
430  SAWYER_MESG(mlog[DEBUG]) <<prefix() <<" forwarding vertex #" <<cfgVertexId <<" output state to "
431  <<StringUtility::plural(vertex->nOutEdges(), "vertices", "vertex") <<"\n";
432  for (const typename CFG::Edge &edge: vertex->outEdges()) {
433  size_t nextVertexId = edge.target()->id();
434  if (!isFeasible_(cfg_, edge, state, incomingState_[nextVertexId])) {
435  SAWYER_MESG(mlog[DEBUG]) <<prefix() <<" path to vertex #" <<nextVertexId
436  <<" is not feasible, thus skipped\n";
437  } else if (merge_(incomingState_[nextVertexId], state)) {
438  if (mlog[DEBUG]) {
439  mlog[DEBUG] <<prefix() <<" merged with vertex #" <<nextVertexId <<" (which changed as a result)\n";
440  mlog[DEBUG] <<prefix() <<" merge state is: "
441  <<StringUtility::prefixLines(xfer_.toString(incomingState_[nextVertexId]),
442  prefix() + " ", false) <<"\n";
443  }
444  workList_.pushBack(nextVertexId);
445  } else {
446  SAWYER_MESG(mlog[DEBUG]) <<prefix() <<" merged with vertex #" <<nextVertexId <<" (no change)\n";
447  }
448  }
449  }
450  return !workList_.isEmpty();
451  }
452 
454  void insertStartingVertex(size_t startVertexId, const State &initialState) {
455  incomingState_[startVertexId] = initialState;
456  workList_.pushBack(startVertexId);
457  }
458 
465  while (runOneIteration()) /*void*/;
466  }
467 
471  void runToFixedPoint(size_t startVertexId, const State &initialState) {
472  reset();
473  insertStartingVertex(startVertexId, initialState);
474  while (runOneIteration()) /*void*/;
475  }
476 
481  State getInitialState(size_t cfgVertexId) const {
482  return incomingState_[cfgVertexId];
483  }
484 
486  void setInitialState(size_t cfgVertexId, State state) {
487  incomingState_[cfgVertexId] = state;
488  }
489 
494  State getFinalState(size_t cfgVertexId) const {
495  return outgoingState_[cfgVertexId];
496  }
497 
502  const VertexStates& getInitialStates() const {
503  return incomingState_;
504  }
505 
510  const VertexStates& getFinalStates() const {
511  return outgoingState_;
512  }
513  };
514 };
515 
516 } // namespace
517 } // namespace
518 
519 #endif
520 #endif
void name(const std::string &s)
Property: Name for debugging.
Definition: DataFlow.h:366
Sawyer::Container::Map< size_t, Graph > VertexFlowGraphs
Map from CFG vertex to data-flow graph.
Definition: DataFlow.h:93
ROSE_UTIL_API std::string numberToString(long long)
Convert an integer to a string.
Instruction basic block.
std::string plural(T n, const std::string &plural_phrase, const std::string &singular_phrase="")
Helpful way to print singular or plural words.
Basic merge operation for instruction semantics.
Definition: DataFlow.h:215
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Base class for machine instructions.
Collection of streams.
Definition: Message.h:1606
AbstractLocation Variable
Variable participating in data flow.
Definition: DataFlow.h:83
Depth-first, forward traversal for edges.
Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge=MergeFunction(), PathFeasibility isFeasible=PathFeasibility())
Constructor.
Definition: DataFlow.h:335
static void initDiagnostics()
Initialize diagnostics.
std::list< Variable > VariableList
List of variables.
Definition: DataFlow.h:86
Main namespace for the ROSE library.
bool isEmpty() const
Determines whether list is empty.
Definition: DistinctList.h:66
std::string prefix() const
Line prefix for debugging.
Definition: DataFlow.h:370
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.
InstructionSemantics::DataFlowSemantics::DataFlowGraph Graph
Data-flow graph.
Definition: DataFlow.h:76
void runToFixedPoint()
Run data-flow until it reaches a fixed point.
Definition: DataFlow.h:464
bool runOneIteration()
Runs one iteration.
Definition: DataFlow.h:397
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
const CFG & cfg() const
Data-flow control flow graph.
Definition: DataFlow.h:345
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
State getInitialState(size_t cfgVertexId) const
Return the incoming state for the specified CFG vertex.
Definition: DataFlow.h:481
DataFlow(const InstructionSemantics::BaseSemantics::DispatcherPtr &userDispatcher)
Constructor.
Definition: DataFlow.h:122
VariableList getUniqueVariables(const VertexFlowGraphs &)
Get list of unique variables.
const VertexStates & getInitialStates() const
All incoming states.
Definition: DataFlow.h:502
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex)
Compute data-flow per CFG vertex.
Definition: DataFlow.h:201
Exceptions when a fixed point is not reached.
Definition: DataFlow.h:103
Trivial path feasibility predicate.
Definition: DataFlow.h:246
State getFinalState(size_t cfgVertexId) const
Return the outgoing state for the specified CFG vertex.
Definition: DataFlow.h:494
const Items & items() const
Return all items as a list.
Definition: DistinctList.h:181
size_t nIterations() const
Number of iterations run.
Definition: DataFlow.h:391
void pushBack(const Item &item)
Insert item at back of list if distinct.
Definition: DistinctList.h:133
std::vector< State > VertexStates
Data-flow states indexed by vertex ID.
Definition: DataFlow.h:314
Binary analysis.
Item popFront()
Return and erase item at front of list.
Definition: DistinctList.h:145
Data-flow exception base class.
Definition: DataFlow.h:97
void reset(State initialState=State())
Reset engine to initial state.
Definition: DataFlow.h:350
Various tools for data-flow analysis.
Definition: DataFlow.h:69
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:603
Functor to return instructions for a cfg vertex.
Definition: DataFlow.h:151
void maxIterations(size_t n)
Max number of iterations to allow.
Definition: DataFlow.h:385
void insertStartingVertex(size_t startVertexId, const State &initialState)
Add a starting vertex.
Definition: DataFlow.h:454
Base class for all ROSE exceptions.
Definition: Rose/Exception.h:9
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker)
Compute data-flow per CFG vertex.
Definition: DataFlow.h:171
void runToFixedPoint(size_t startVertexId, const State &initialState)
Add starting point and run to fixed point.
Definition: DataFlow.h:471
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:395
const std::string & name() const
Property: Name for debugging.
Definition: DataFlow.h:365
void clear()
Clear the list.
Definition: DistinctList.h:58
size_t maxIterations() const
Max number of iterations to allow.
Definition: DataFlow.h:384
const VertexStates & getFinalStates() const
All outgoing states.
Definition: DataFlow.h:510
void setInitialState(size_t cfgVertexId, State state)
Set the initial state for the specified CFG vertex.
Definition: DataFlow.h:486