ROSE  0.11.50.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/InstructionSemantics2/DataFlowSemantics.h>
7 #include <Rose/Diagnostics.h>
8 #include <Rose/Exception.h>
9 #include <Rose/BinaryAnalysis/InstructionSemantics2/SymbolicSemantics.h>
10 
11 #include <boost/foreach.hpp>
12 #include <boost/lexical_cast.hpp>
13 #include <list>
14 #include <Sawyer/GraphTraversal.h>
15 #include <Sawyer/DistinctList.h>
16 #include <sstream>
17 #include <string>
18 #include <vector>
19 
20 namespace Rose {
21 namespace BinaryAnalysis {
22 
70 class DataFlow {
71 public:
78 
85 
87  typedef std::list<Variable> VariableList;
88 
95 
96 public:
98  class Exception: public Rose::Exception {
99  public:
100  explicit Exception(const std::string &s): Rose::Exception(s) {}
101  };
102 
104  class NotConverging: public Exception {
105  public:
106  explicit NotConverging(const std::string &s): Exception(s) {}
107  };
108 
109 private:
110  InstructionSemantics2::BaseSemantics::RiscOperatorsPtr userOps_; // operators (and state) provided by the user
111  InstructionSemantics2::DataFlowSemantics::RiscOperatorsPtr dfOps_; // data-flow operators (which point to user ops)
112  InstructionSemantics2::BaseSemantics::DispatcherPtr dispatcher_; // copy of user's dispatcher but with DataFlowSemantics
113  static Sawyer::Message::Facility mlog; // diagnostics for data-flow
115 
116 public:
123  init(userDispatcher);
124  }
125 
129  static void initDiagnostics();
130 
131 public:
140  Graph buildGraph(const std::vector<SgAsmInstruction*>&);
149  public:
150  typedef std::vector<SgAsmInstruction*> Instructions;
151  Instructions operator()(SgAsmInstruction *insn) { return Instructions(1, insn); }
152  Instructions operator()(SgAsmBlock *blk);
153  };
154 
155 public:
167  template<class CFG, class VertexUnpacker>
168  VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker) {
169  using namespace Diagnostics;
170  ASSERT_this();
171  ASSERT_require(startVertex < cfg.nVertices());
172  Stream mesg(mlog[WHERE] <<"buildGraphPerVertex startVertex=" <<startVertex);
173 
174  VertexFlowGraphs result;
175  result.insert(startVertex, buildGraph(vertexUnpacker(cfg.findVertex(startVertex)->value())));
176  std::vector<InstructionSemantics2::BaseSemantics::StatePtr> postState(cfg.nVertices()); // user-defined states
177  postState[startVertex] = userOps_->currentState();
178 
180  for (Traversal t(cfg, cfg.findVertex(startVertex)); t; ++t) {
181  typename CFG::ConstVertexIterator source = t->source();
182  typename CFG::ConstVertexIterator target = t->target();
183  InstructionSemantics2::BaseSemantics::StatePtr state = postState[target->id()];
184  if (state==NULL) {
185  ASSERT_not_null(postState[source->id()]);
186  state = postState[target->id()] = postState[source->id()]->clone();
187  userOps_->currentState(state);
188  std::vector<SgAsmInstruction*> insns = vertexUnpacker(target->value());
189  result.insert(target->id(), buildGraph(insns));
190  }
191  }
192 
193  mesg <<"; processed " <<StringUtility::plural(result.size(), "vertices", "vertex") <<"\n";
194  return result;
195  }
196 
197  template<class CFG>
198  VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex) {
199  return buildGraphPerVertex(cfg, startVertex, DefaultVertexUnpacker());
200  }
207  VariableList getUniqueVariables(const VertexFlowGraphs&);
208 
214  public:
216  explicit SemanticsMerge(const InstructionSemantics2::BaseSemantics::DispatcherPtr &cpu): ops_(cpu->operators()) {}
217 
218  bool operator()(InstructionSemantics2::BaseSemantics::StatePtr &dst /*in,out*/,
220  struct PreserveCurrentState {
223  PreserveCurrentState(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &ops)
224  : ops(ops), state(ops->currentState()) {}
225  ~PreserveCurrentState() { ops->currentState(state); }
226  } t(ops_);
227 
228  if (!dst) {
229  dst = src->clone();
230  return true;
231  } else {
232  ops_->currentState(src);
233  return dst->merge(src, ops_.get());
234  }
235  }
236  };
237 
242  template<class CFG, class State>
244  public:
245  bool operator()(const CFG&, const typename CFG::Edge&, const State&, const State&) {
246  return true;
247  }
248  };
249 
307  template<class CFG, class State, class TransferFunction, class MergeFunction,
308  class PathFeasibility = PathAlwaysFeasible<CFG, State> >
309  class Engine {
310  public:
311  typedef std::vector<State> VertexStates;
313  private:
314  const CFG &cfg_;
315  TransferFunction &xfer_;
316  MergeFunction merge_;
317  VertexStates incomingState_; // incoming data-flow state per CFG vertex ID
318  VertexStates outgoingState_; // outgoing data-flow state per CFG vertex ID
320  WorkList workList_; // CFG vertex IDs to be visited, last in first out w/out duplicates
321  size_t maxIterations_; // max number of iterations to allow
322  size_t nIterations_; // number of iterations since last reset
323  PathFeasibility isFeasible_; // predicate to test path feasibility
324 
325  public:
331  Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge = MergeFunction(),
332  PathFeasibility isFeasible = PathFeasibility())
333  : cfg_(cfg), xfer_(xfer), merge_(merge), maxIterations_(-1), nIterations_(0), isFeasible_(isFeasible) {
334  reset();
335  }
336 
341  const CFG &cfg() const {
342  return cfg_;
343  }
344 
346  void reset(State initialState = State()) {
347  ASSERT_this();
348  incomingState_.clear();
349  incomingState_.resize(cfg_.nVertices(), initialState);
350  outgoingState_.clear();
351  outgoingState_.resize(cfg_.nVertices(), initialState);
352  workList_.clear();
353  nIterations_ = 0;
354  }
355 
362  size_t maxIterations() const { return maxIterations_; }
363  void maxIterations(size_t n) { maxIterations_ = n; }
369  size_t nIterations() const { return nIterations_; }
370 
376  using namespace Diagnostics;
377  if (!workList_.isEmpty()) {
378  if (++nIterations_ > maxIterations_) {
379  throw NotConverging("data-flow max iterations reached"
380  " (max=" + StringUtility::numberToString(maxIterations_) + ")");
381  }
382  size_t cfgVertexId = workList_.popFront();
383  if (mlog[DEBUG]) {
384  mlog[DEBUG] <<"runOneIteration: vertex #" <<cfgVertexId <<"\n";
385  mlog[DEBUG] <<" remaining worklist is {";
386  BOOST_FOREACH (size_t id, workList_.items())
387  mlog[DEBUG] <<" " <<id;
388  mlog[DEBUG] <<" }\n";
389  }
390 
391  ASSERT_require2(cfgVertexId < cfg_.nVertices(),
392  "vertex " + boost::lexical_cast<std::string>(cfgVertexId) + " must be valid within CFG");
393  typename CFG::ConstVertexIterator vertex = cfg_.findVertex(cfgVertexId);
394  State state = incomingState_[cfgVertexId];
395  if (mlog[DEBUG]) {
396  mlog[DEBUG] <<" incoming state for vertex #" <<cfgVertexId <<":\n"
397  <<StringUtility::prefixLines(xfer_.toString(state), " ") <<"\n";
398  }
399 
400  state = outgoingState_[cfgVertexId] = xfer_(cfg_, cfgVertexId, state);
401  if (mlog[DEBUG]) {
402  mlog[DEBUG] <<" outgoing state for vertex #" <<cfgVertexId <<":\n"
403  <<StringUtility::prefixLines(xfer_.toString(state), " ") <<"\n";
404  }
405 
406  // Outgoing state must be merged into the incoming states for the CFG successors. Any such incoming state that
407  // is modified as a result will have its CFG vertex added to the work list.
408  SAWYER_MESG(mlog[DEBUG]) <<" forwarding vertex #" <<cfgVertexId <<" output state to "
409  <<StringUtility::plural(vertex->nOutEdges(), "vertices", "vertex") <<"\n";
410  BOOST_FOREACH (const typename CFG::Edge &edge, vertex->outEdges()) {
411  size_t nextVertexId = edge.target()->id();
412  if (!isFeasible_(cfg_, edge, state, incomingState_[nextVertexId])) {
413  SAWYER_MESG(mlog[DEBUG]) <<" path to vertex #" <<nextVertexId <<" is not feasible, thus skipped\n";
414  } else if (merge_(incomingState_[nextVertexId], state)) {
415  if (mlog[DEBUG]) {
416  mlog[DEBUG] <<" merged with vertex #" <<nextVertexId <<" (which changed as a result)\n";
417  mlog[DEBUG] <<" merge state is: "
418  <<StringUtility::prefixLines(xfer_.toString(incomingState_[nextVertexId]),
419  " ", false) <<"\n";
420  }
421  workList_.pushBack(nextVertexId);
422  } else {
423  SAWYER_MESG(mlog[DEBUG]) <<" merged with vertex #" <<nextVertexId <<" (no change)\n";
424  }
425  }
426  }
427  return !workList_.isEmpty();
428  }
429 
431  void insertStartingVertex(size_t startVertexId, const State &initialState) {
432  incomingState_[startVertexId] = initialState;
433  workList_.pushBack(startVertexId);
434  }
435 
442  while (runOneIteration()) /*void*/;
443  }
444 
448  void runToFixedPoint(size_t startVertexId, const State &initialState) {
449  reset();
450  insertStartingVertex(startVertexId, initialState);
451  while (runOneIteration()) /*void*/;
452  }
453 
458  State getInitialState(size_t cfgVertexId) const {
459  return incomingState_[cfgVertexId];
460  }
461 
463  void setInitialState(size_t cfgVertexId, State state) {
464  incomingState_[cfgVertexId] = state;
465  }
466 
471  State getFinalState(size_t cfgVertexId) const {
472  return outgoingState_[cfgVertexId];
473  }
474 
479  const VertexStates& getInitialStates() const {
480  return incomingState_;
481  }
482 
487  const VertexStates& getFinalStates() const {
488  return outgoingState_;
489  }
490  };
491 };
492 
493 } // namespace
494 } // namespace
495 
496 #endif
497 #endif
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Sawyer::Container::Map< size_t, Graph > VertexFlowGraphs
Map from CFG vertex to data-flow graph.
Definition: DataFlow.h:94
ROSE_UTIL_API std::string numberToString(long long)
Convert an integer to a string.
Instruction basic block.
InstructionSemantics2::DataFlowSemantics::DataFlowGraph Graph
Data-flow graph.
Definition: DataFlow.h:77
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:212
Base class for machine instructions.
Collection of streams.
Definition: Message.h:1606
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
AbstractLocation Variable
Variable participating in data flow.
Definition: DataFlow.h:84
Depth-first, forward traversal for edges.
Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge=MergeFunction(), PathFeasibility isFeasible=PathFeasibility())
Constructor.
Definition: DataFlow.h:331
static void initDiagnostics()
Initialize diagnostics.
std::list< Variable > VariableList
List of variables.
Definition: DataFlow.h:87
DataFlow(const InstructionSemantics2::BaseSemantics::DispatcherPtr &userDispatcher)
Constructor.
Definition: DataFlow.h:122
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 runToFixedPoint()
Run data-flow until it reaches a fixed point.
Definition: DataFlow.h:441
bool runOneIteration()
Runs one iteration.
Definition: DataFlow.h:375
const CFG & cfg() const
Data-flow control flow graph.
Definition: DataFlow.h:341
State getInitialState(size_t cfgVertexId) const
Return the incoming state for the specified CFG vertex.
Definition: DataFlow.h:458
VariableList getUniqueVariables(const VertexFlowGraphs &)
Get list of unique variables.
boost::shared_ptr< Dispatcher > DispatcherPtr
Shared-ownership pointer to a semantics instruction dispatcher.
const VertexStates & getInitialStates() const
All incoming states.
Definition: DataFlow.h:479
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex)
Compute data-flow per CFG vertex.
Definition: DataFlow.h:198
Exceptions when a fixed point is not reached.
Definition: DataFlow.h:104
Trivial path feasibility predicate.
Definition: DataFlow.h:243
State getFinalState(size_t cfgVertexId) const
Return the outgoing state for the specified CFG vertex.
Definition: DataFlow.h:471
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:369
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:311
Item popFront()
Return and erase item at front of list.
Definition: DistinctList.h:145
Data-flow exception base class.
Definition: DataFlow.h:98
void reset(State initialState=State())
Reset engine to initial state.
Definition: DataFlow.h:346
Various tools for data-flow analysis.
Definition: DataFlow.h:70
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:594
Functor to return instructions for a cfg vertex.
Definition: DataFlow.h:148
void maxIterations(size_t n)
Max number of iterations to allow.
Definition: DataFlow.h:363
void insertStartingVertex(size_t startVertexId, const State &initialState)
Add a starting vertex.
Definition: DataFlow.h:431
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:168
void runToFixedPoint(size_t startVertexId, const State &initialState)
Add starting point and run to fixed point.
Definition: DataFlow.h:448
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:386
void clear()
Clear the list.
Definition: DistinctList.h:58
size_t maxIterations() const
Max number of iterations to allow.
Definition: DataFlow.h:362
const VertexStates & getFinalStates() const
All outgoing states.
Definition: DataFlow.h:487
void setInitialState(size_t cfgVertexId, State state)
Set the initial state for the specified CFG vertex.
Definition: DataFlow.h:463