1 #ifndef ROSE_BinaryAnalysis_DataFlow_H
2 #define ROSE_BinaryAnalysis_DataFlow_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
6 #include <Rose/BinaryAnalysis/InstructionSemantics2/DataFlowSemantics.h>
7 #include <Rose/Diagnostics.h>
8 #include <Rose/Exception.h>
9 #include <Rose/BinaryAnalysis/InstructionSemantics2/SymbolicSemantics.h>
11 #include <boost/lexical_cast.hpp>
13 #include <Sawyer/GraphTraversal.h>
14 #include <Sawyer/DistinctList.h>
20 namespace BinaryAnalysis {
110 InstructionSemantics2::DataFlowSemantics::RiscOperatorsPtr dfOps_;
122 init(userDispatcher);
139 Graph
buildGraph(
const std::vector<SgAsmInstruction*>&);
149 typedef std::vector<SgAsmInstruction*> Instructions;
150 Instructions operator()(
SgAsmInstruction *insn) {
return Instructions(1, insn); }
166 template<
class CFG,
class VertexUnpacker>
168 using namespace Diagnostics;
170 ASSERT_require(startVertex < cfg.nVertices());
171 Stream mesg(mlog[WHERE] <<
"buildGraphPerVertex startVertex=" <<startVertex);
173 VertexFlowGraphs result;
174 result.
insert(startVertex,
buildGraph(vertexUnpacker(cfg.findVertex(startVertex)->value())));
175 std::vector<InstructionSemantics2::BaseSemantics::StatePtr> postState(cfg.nVertices());
176 postState[startVertex] = userOps_->currentState();
179 for (Traversal t(cfg, cfg.findVertex(startVertex)); t; ++t) {
180 typename CFG::ConstVertexIterator source = t->source();
181 typename CFG::ConstVertexIterator target = t->target();
184 ASSERT_not_null(postState[source->id()]);
185 state = postState[target->id()] = postState[source->id()]->clone();
186 userOps_->currentState(state);
187 std::vector<SgAsmInstruction*> insns = vertexUnpacker(target->value());
219 struct PreserveCurrentState {
223 : ops(ops), state(ops->currentState()) {}
224 ~PreserveCurrentState() { ops->currentState(state); }
231 ops_->currentState(src);
232 return dst->merge(src, ops_.get());
241 template<
class CFG,
class State>
244 bool operator()(
const CFG&,
const typename CFG::Edge&,
const State&,
const State&) {
306 template<
class CFG,
class State,
class TransferFunction,
class MergeFunction,
314 TransferFunction &xfer_;
315 MergeFunction merge_;
316 VertexStates incomingState_;
317 VertexStates outgoingState_;
320 size_t maxIterations_;
322 PathFeasibility isFeasible_;
330 Engine(
const CFG &
cfg, TransferFunction &xfer, MergeFunction merge = MergeFunction(),
331 PathFeasibility isFeasible = PathFeasibility())
332 : cfg_(cfg), xfer_(xfer), merge_(merge), maxIterations_(-1), nIterations_(0), isFeasible_(isFeasible) {
345 void reset(State initialState = State()) {
347 incomingState_.clear();
348 incomingState_.resize(cfg_.nVertices(), initialState);
349 outgoingState_.clear();
350 outgoingState_.resize(cfg_.nVertices(), initialState);
375 using namespace Diagnostics;
377 if (++nIterations_ > maxIterations_) {
381 size_t cfgVertexId = workList_.
popFront();
383 mlog[DEBUG] <<
"runOneIteration: vertex #" <<cfgVertexId <<
"\n";
384 mlog[DEBUG] <<
" remaining worklist is {";
385 for (
size_t id: workList_.
items())
386 mlog[DEBUG] <<
" " <<
id;
387 mlog[DEBUG] <<
" }\n";
390 ASSERT_require2(cfgVertexId < cfg_.nVertices(),
391 "vertex " + boost::lexical_cast<std::string>(cfgVertexId) +
" must be valid within CFG");
392 typename CFG::ConstVertexIterator vertex = cfg_.findVertex(cfgVertexId);
393 State state = incomingState_[cfgVertexId];
395 mlog[DEBUG] <<
" incoming state for vertex #" <<cfgVertexId <<
":\n"
399 state = outgoingState_[cfgVertexId] = xfer_(cfg_, cfgVertexId, state);
401 mlog[DEBUG] <<
" outgoing state for vertex #" <<cfgVertexId <<
":\n"
407 SAWYER_MESG(mlog[DEBUG]) <<
" forwarding vertex #" <<cfgVertexId <<
" output state to "
409 for (
const typename CFG::Edge &edge: vertex->outEdges()) {
410 size_t nextVertexId = edge.target()->id();
411 if (!isFeasible_(cfg_, edge, state, incomingState_[nextVertexId])) {
412 SAWYER_MESG(mlog[DEBUG]) <<
" path to vertex #" <<nextVertexId <<
" is not feasible, thus skipped\n";
413 }
else if (merge_(incomingState_[nextVertexId], state)) {
415 mlog[DEBUG] <<
" merged with vertex #" <<nextVertexId <<
" (which changed as a result)\n";
416 mlog[DEBUG] <<
" merge state is: "
422 SAWYER_MESG(mlog[DEBUG]) <<
" merged with vertex #" <<nextVertexId <<
" (no change)\n";
431 incomingState_[startVertexId] = initialState;
458 return incomingState_[cfgVertexId];
463 incomingState_[cfgVertexId] = state;
471 return outgoingState_[cfgVertexId];
479 return incomingState_;
487 return outgoingState_;
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.
ROSE_UTIL_API std::string numberToString(long long)
Convert an integer to a string.
InstructionSemantics2::DataFlowSemantics::DataFlowGraph Graph
Data-flow graph.
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.
Base class for machine instructions.
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
AbstractLocation Variable
Variable participating in data flow.
Depth-first, forward traversal for edges.
Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge=MergeFunction(), PathFeasibility isFeasible=PathFeasibility())
Constructor.
static void initDiagnostics()
Initialize diagnostics.
std::list< Variable > VariableList
List of variables.
DataFlow(const InstructionSemantics2::BaseSemantics::DispatcherPtr &userDispatcher)
Constructor.
Main namespace for the ROSE library.
bool isEmpty() const
Determines whether list is empty.
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.
bool runOneIteration()
Runs one iteration.
const CFG & cfg() const
Data-flow control flow graph.
State getInitialState(size_t cfgVertexId) const
Return the incoming state for the specified CFG vertex.
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.
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex)
Compute data-flow per CFG vertex.
Exceptions when a fixed point is not reached.
Trivial path feasibility predicate.
State getFinalState(size_t cfgVertexId) const
Return the outgoing state for the specified CFG vertex.
const Items & items() const
Return all items as a list.
size_t nIterations() const
Number of iterations run.
void pushBack(const Item &item)
Insert item at back of list if distinct.
std::vector< State > VertexStates
Data-flow states indexed by vertex ID.
Item popFront()
Return and erase item at front of list.
Data-flow exception base class.
void reset(State initialState=State())
Reset engine to initial state.
Various tools for data-flow analysis.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Functor to return instructions for a cfg vertex.
void maxIterations(size_t n)
Max number of iterations to allow.
void insertStartingVertex(size_t startVertexId, const State &initialState)
Add a starting vertex.
Base class for all ROSE exceptions.
VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker)
Compute data-flow per CFG vertex.
void runToFixedPoint(size_t startVertexId, const State &initialState)
Add starting point and run to fixed point.
size_t size() const
Number of nodes, keys, or values in this container.
void clear()
Clear the list.
size_t maxIterations() const
Max number of iterations to allow.
const VertexStates & getFinalStates() const
All outgoing states.
void setInitialState(size_t cfgVertexId, State state)
Set the initial state for the specified CFG vertex.