ROSE  0.9.10.54
Partitioner.h
1 #ifndef ROSE_Partitioner2_Partitioner_H
2 #define ROSE_Partitioner2_Partitioner_H
3 
4 #include <Partitioner2/AddressUsageMap.h>
5 #include <Partitioner2/BasicBlock.h>
6 #include <Partitioner2/BasicTypes.h>
7 #include <Partitioner2/Config.h>
8 #include <Partitioner2/ControlFlowGraph.h>
9 #include <Partitioner2/DataBlock.h>
10 #include <Partitioner2/Function.h>
11 #include <Partitioner2/FunctionCallGraph.h>
12 #include <Partitioner2/InstructionProvider.h>
13 #include <Partitioner2/Modules.h>
14 #include <Partitioner2/Reference.h>
15 
16 #include <Sawyer/Attribute.h>
17 #include <Sawyer/Callbacks.h>
18 #include <Sawyer/IntervalSet.h>
19 #include <Sawyer/Map.h>
20 #include <Sawyer/Message.h>
21 #include <Sawyer/Optional.h>
22 #include <Sawyer/ProgressBar.h>
23 #include <Sawyer/SharedPointer.h>
24 
25 #include <BinaryUnparser.h>
26 #include <Progress.h>
27 
28 #include <boost/filesystem.hpp>
29 #include <boost/serialization/access.hpp>
30 #include <boost/serialization/split_member.hpp>
31 
32 #include <ostream>
33 #include <set>
34 #include <string>
35 #include <vector>
36 
37 // Derived classes needed for serialization
38 #include <BinaryYicesSolver.h>
39 #include <BinaryZ3Solver.h>
40 #include <DispatcherM68k.h>
41 #include <DispatcherX86.h>
42 
43 namespace Rose {
44 namespace BinaryAnalysis {
45 
77 namespace Partitioner2 {
78 
292 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
293 public:
296  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
297  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
300  struct Thunk {
302  rose_addr_t target;
303  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
304  };
305 
308 
309 private:
310  BasePartitionerSettings settings_; // settings adjustable from the command-line
311  Configuration config_; // configuration information about functions, blocks, etc.
312  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
313  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
314  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
315  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
316  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
317  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
318  Functions functions_; // List of all attached functions by entry address
319  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
320  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
321  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
322  AddressNameMap addressNames_; // Names for various addresses
323  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
324  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
325  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
326 
327  // Callback lists
328  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
329  BasicBlockCallbacks basicBlockCallbacks_;
330  FunctionPrologueMatchers functionPrologueMatchers_;
331  FunctionPaddingMatchers functionPaddingMatchers_;
332 
333  // Special CFG vertices.
334  ControlFlowGraph::VertexIterator undiscoveredVertex_;
335  ControlFlowGraph::VertexIterator indeterminateVertex_;
336  ControlFlowGraph::VertexIterator nonexistingVertex_;
337  static const size_t nSpecialVertices = 3;
338 
339  // Protects the following data members
340  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
341  Progress::Ptr progress_; // Progress reporter to update, or null
342  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
343 
344 
347  //
348  // Serialization
349  //
352 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
353 private:
354  friend class boost::serialization::access;
355 
356  template<class S>
357  void serializeCommon(S &s, const unsigned /*version*/) {
358  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
359  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
360  s.template register_type<InstructionSemantics2::DispatcherX86>();
361  s.template register_type<InstructionSemantics2::DispatcherM68k>();
362  s.template register_type<SymbolicExpr::Interior>();
363  s.template register_type<SymbolicExpr::Leaf>();
364  s.template register_type<YicesSolver>();
365  s.template register_type<Z3Solver>();
366  s.template register_type<Semantics::SValue>();
367  s.template register_type<Semantics::MemoryListState>();
368  s.template register_type<Semantics::MemoryMapState>();
369  s.template register_type<Semantics::RegisterState>();
370  s.template register_type<Semantics::State>();
371  s.template register_type<Semantics::RiscOperators>();
372  s & BOOST_SERIALIZATION_NVP(settings_);
373  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
374  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
375  s & BOOST_SERIALIZATION_NVP(memoryMap_);
376  s & BOOST_SERIALIZATION_NVP(cfg_);
377  // s & vertexIndex_; -- initialized by rebuildVertexIndices
378  s & BOOST_SERIALIZATION_NVP(aum_);
379  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
380  s & BOOST_SERIALIZATION_NVP(functions_);
381  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
382  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
383  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
384  s & BOOST_SERIALIZATION_NVP(addressNames_);
385  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
386  // s & unparser_; -- not saved; restored from disassembler
387  // s & cfgAdjustmentCallbacks_; -- not saved/restored
388  // s & basicBlockCallbacks_; -- not saved/restored
389  // s & functionPrologueMatchers_; -- not saved/restored
390  // s & functionPaddingMatchers_; -- not saved/restored
391  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
392  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
393  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
394  // s & progress_; -- not saved/restored
395  // s & cfgProgressTotal_; -- not saved/restored
396  }
397 
398  template<class S>
399  void save(S &s, const unsigned version) const {
400  const_cast<Partitioner*>(this)->serializeCommon(s, version);
401  }
402 
403  template<class S>
404  void load(S &s, const unsigned version) {
405  serializeCommon(s, version);
406  rebuildVertexIndices();
407  }
408 
409  BOOST_SERIALIZATION_SPLIT_MEMBER();
410 #endif
411 
412 
415  //
416  // Constructors
417  //
420 public:
425  Partitioner();
426 
431  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
432 
433  // FIXME[Robb P. Matzke 2014-11-08]: This is not ready for use yet. The problem is that because of the shallow copy, both
434  // partitioners are pointing to the same basic blocks, data blocks, and functions. This is okay by itself since these
435  // things are reference counted, but the paradigm of locked/unlocked blocks and functions breaks down somewhat -- does
436  // unlocking a basic block from one partitioner make it modifiable even though it's still locked in the other partitioner?
437  // FIXME[Robb P. Matzke 2014-12-27]: Not the most efficient implementation, but saves on cut-n-paste which would surely rot
438  // after a while.
439  Partitioner(const Partitioner &other);
440  Partitioner& operator=(const Partitioner &other);
441 
442  ~Partitioner();
443 
450  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
451 
453  void clear() /*final*/;
454 
462  Configuration& configuration() { return config_; }
463  const Configuration& configuration() const { return config_; }
471  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
472  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
484  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
490  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
491  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
492  }
493 
496  //
497  // Unparsing
498  //
501 
511  Unparser::BasePtr unparser() const /*final*/;
512  void unparser(const Unparser::BasePtr&) /*final*/;
524  Unparser::BasePtr insnUnparser() const /*final*/;
525  void insnUnparser(const Unparser::BasePtr&) /*final*/;
536  std::string unparse(SgAsmInstruction*) const;
537  void unparse(std::ostream&, SgAsmInstruction*) const;
538  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
539  void unparse(std::ostream&, const DataBlock::Ptr&) const;
540  void unparse(std::ostream&, const Function::Ptr&) const;
541  void unparse(std::ostream&) const;
544  //
547  // Partitioner CFG queries
548  //
551 public:
557  size_t nBytes() const /*final*/ { return aum_.size(); }
558 
566  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
567  return undiscoveredVertex_;
568  }
569  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
570  return undiscoveredVertex_;
571  }
584  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
585  return indeterminateVertex_;
586  }
587  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
588  return indeterminateVertex_;
589  }
601  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
602  return nonexistingVertex_;
603  }
604  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
605  return nonexistingVertex_;
606  }
615  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
616 
623  const AddressUsageMap& aum() const /*final*/ { return aum_; }
624 
626  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
627 
635  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
636 
665  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
666  const Function::Ptr &function = Function::Ptr()) const /*final*/;
667  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
668  const Function::Ptr &function = Function::Ptr()) const /*final*/;
705  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
706  const Function::Ptr &sourceFunction = Function::Ptr(),
707  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
708  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
709  const Function::Ptr &sourceFunction = Function::Ptr(),
710  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
715  //
718  // Partitioner instruction operations
719  //
722 public:
728  size_t nInstructions() const /*final*/;
729 
739  Sawyer::Optional<AddressUser> instructionExists(rose_addr_t startVa) const /*final*/ {
740  return aum_.instructionExists(startVa);
741  }
743  return insn==NULL ? Sawyer::Nothing() : instructionExists(insn->get_address());
744  }
753  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
754 
763  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
764 
773  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
774 
784  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
785 
793  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
794 
807  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
808 
813  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
814 
815 
818  //
819  // Partitioner basic block placeholder operations
820  //
823 public:
833  size_t nPlaceholders() const /*final*/;
834 
843  bool placeholderExists(rose_addr_t startVa) const /*final*/;
844 
855  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
856  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
857  return *found;
858  return cfg_.vertices().end();
859  }
860  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
861  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
862  return *found;
863  return cfg_.vertices().end();
864  }
883  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
884 
898  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
899  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
904  //
907  // Partitioner basic block operations
908  //
911 public:
925  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
937  void basicBlockDropSemantics() const /*final*/;
938 
947  size_t nBasicBlocks() const /*final*/;
948 
956  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
957 
979  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
980  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
992  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
993 
1004  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1005 
1015  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1016 
1023  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1024 
1034  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1035 
1041  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1042 
1067  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1068  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1069  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1084  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1085  SgAsmInstruction *insn) /*final*/;
1086 
1117  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1118  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1206  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1207  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1220  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&) const /*final*/;
1221 
1230  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1231 
1250  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1251 
1261  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&) const /*final*/;
1262 
1273  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1274 
1314  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1315  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1326  void forgetStackDeltas() const /*final*/;
1327  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1339  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1340  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1393  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1394 
1395  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1404  void basicBlockMayReturnReset() const /*final*/;
1405 
1406 private:
1407  // Per-vertex data used during may-return analysis
1408  struct MayReturnVertexInfo {
1409  enum State {INIT, CALCULATING, FINISHED};
1410  State state; // current state of vertex
1411  bool processedCallees; // have we processed BBs this vertex calls?
1412  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1413  boost::logic::tribool result; // final result (eventually cached in BB)
1414  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1415  };
1416 
1417  // Is edge significant for analysis? See .C file for full documentation.
1418  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1419  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1420 
1421  // Determine (and cache in vertexInfo) whether any callees return.
1422  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1423  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1424 
1425  // Maximum may-return result from significant successors including phantom call-return edge.
1426  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1427  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1428 
1429  // The guts of the may-return analysis
1430  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1431  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1432 
1433 
1434 
1437  //
1438  // Partitioner data block operations
1439  //
1442 public:
1448  size_t nDataBlocks() const /*final*/;
1449 
1455  bool dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1456 
1465  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1466 
1475  void attachDataBlock(const DataBlock::Ptr&) /*final*/;
1476 
1483  DataBlock::Ptr detachDataBlock(const DataBlock::Ptr&) /*final*/;
1484 
1494  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1495 
1505  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1506 
1516  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1517 
1524  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1525 
1531  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1532 
1533 
1534 
1537  //
1538  // Partitioner function operations
1539  //
1542 public:
1548  size_t nFunctions() const /*final*/ { return functions_.size(); }
1549 
1568  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1569  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1570  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1578  std::vector<Function::Ptr> functions() const /*final*/;
1579 
1589  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1590 
1601  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1602 
1612  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1613 
1630  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1631  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1632  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1633  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1634  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1635  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1657  size_t attachFunction(const Function::Ptr&) /*final*/;
1658  size_t attachFunctions(const Functions&) /*final*/;
1674  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1675 
1692  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1693  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1709  void detachFunction(const Function::Ptr&) /*final*/;
1710 
1721  DataBlock::Ptr attachFunctionDataBlock(const Function::Ptr&, rose_addr_t startVa, size_t nBytes) /*final*/;
1722 
1728  void attachFunctionDataBlock(const Function::Ptr&, const DataBlock::Ptr&) /*final*/;
1729 
1764  std::vector<Function::Ptr>
1765  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1766 
1767  std::vector<Function::Ptr>
1768  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1769 
1770  std::vector<Function::Ptr>
1771  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1772 
1773  std::vector<Function::Ptr>
1774  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1775 
1776  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1777  std::vector<Function::Ptr>
1778  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1779  std::vector<Function::Ptr> retval;
1780  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1781  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1782  insertUnique(retval, function, sortFunctionsByAddress);
1783  }
1784  return retval;
1785  }
1797  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1798 
1810  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1811 
1821  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1822 
1833  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1834 
1841  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1842 
1850  FunctionCallGraph functionCallGraph(bool allowParallelEdges = true) const /*final*/;
1851 
1871  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1872 
1876  void allFunctionStackDelta() const /*final*/;
1877 
1884  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1885 
1889  void allFunctionMayReturn() const /*final*/;
1890 
1917  const CallingConvention::Analysis&
1918  functionCallingConvention(const Function::Ptr&,
1919  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1920  const /*final*/;
1921 
1934  void
1935  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1936  const /*final*/;
1937 
1963  CallingConvention::Dictionary
1964  functionCallingConventionDefinitions(const Function::Ptr&,
1965  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1966  const /*final*/;
1967 
1980  void
1981  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
1982  CallingConvention::Definition::Ptr()) const /*final*/;
1983 
1992  void fixInterFunctionEdges() /*final*/;
1993  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2013  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2014 
2020  void allFunctionIsNoop() const /*final*/;
2021 
2029  void forgetFunctionIsNoop() const /*final*/;
2030  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2035  //
2038  // Callbacks
2039  //
2042 public:
2060  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2061  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2072  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2073  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2076 public:
2084  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2085  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2107  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2108 
2109 public:
2115  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2116  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2126  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2127 
2128 
2129 
2132  //
2133  // Partitioner miscellaneous
2134  //
2137 public:
2149  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2150  bool computeProperties=true) const /*final*/;
2151 
2165  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2166  bool showNeighbors=true) const /*final*/;
2167 
2173  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2174  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2180  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2181 
2187  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2188  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2196  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2197  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2205  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2206  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2212  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2213 
2217  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2218 
2222  static std::string functionName(const Function::Ptr&) /*final*/;
2223 
2231  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2232  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2252  Progress::Ptr progress() const /*final*/;
2253  void progress(const Progress::Ptr&) /*final*/;
2260  void updateProgress(const std::string &phase, double completion) const;
2261 
2270  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2271  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2272  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2296  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2297  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2314  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2315  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2327  void addressName(rose_addr_t, const std::string&) /*final*/;
2328  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2329  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2339  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2340  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2344  //
2347  // Instruction semantics
2348  //
2351 public:
2361  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2362  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2371  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2372 
2383  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2384  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2394  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2395 
2396 
2397 
2398 
2401  //
2402  // Partitioner internal utilities
2403  //
2406 private:
2407  void init(Disassembler*, const MemoryMap::Ptr&);
2408  void init(const Partitioner&);
2409  void updateCfgProgress();
2410 
2411 private:
2412  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2413  // and destination CFGs are identical.
2414  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2415  ControlFlowGraph::ConstVertexIterator otherIter);
2416 
2417  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2418  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2419  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2420 
2421  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2422  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2423  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2424 
2425  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2426  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2427 
2428  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2429  void checkConsistency() const;
2430 
2431  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2432  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2433  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2434 
2435  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2436  // The call happens immediately after the CFG/AUM are updated.
2437  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2438 
2439  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2440  void rebuildVertexIndices();
2441 };
2442 
2443 } // namespace
2444 } // namespace
2445 } // namespace
2446 
2447 #endif
Represents information about a thunk.
Definition: Partitioner.h:300
size_t size() const
Number of addresses represented by the map.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:295
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2085
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2371
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:301
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:486
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2084
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2328
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2271
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2340
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:587
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:463
Base class for machine instructions.
Sawyer::Optional< AddressUser > instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:742
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2116
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:615
Provides and caches instructions.
Settings that directly control a partitioner.
Definition: BasicTypes.h:251
STL namespace.
Holds a value or nothing.
Definition: Optional.h:49
ControlFlowGraph::VertexIterator indeterminateVertex()
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:584
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:471
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1448
Main namespace for the ROSE library.
Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
Map address to name.
Definition: Partitioner.h:307
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2072
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:566
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2361
Name space for the entire library.
Definition: Access.h:13
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:462
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2315
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:860
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:623
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2329
Base classes for instruction semantics.
void settings(const BasePartitionerSettings &s)
Partitioner settings.
Definition: Partitioner.h:2232
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2314
bool instructionExists(SgAsmInstruction *) const
Determines whether an instruction exists in the map.
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:302
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
ControlFlowGraph::VertexIterator nonexistingVertex()
Returns the special "non-existing" vertex.
Definition: Partitioner.h:601
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:450
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2272
SemanticMemoryParadigm
Organization of semantic memory.
Definition: BasicTypes.h:60
An efficient mapping from an address space to stored data.
Definition: MemoryMap.h:97
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2073
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:926
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:513
void stackDeltaInterproceduralLimit(size_t n)
Property: max depth for inter-procedural stack delta analysis.
Definition: Partitioner.h:1340
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:472
bool checkingCallBranch
Check for situations where CALL is used as a branch.
Definition: BasicTypes.h:256
bool usingSemantics
Whether instruction semantics are used.
Definition: BasicTypes.h:252
A general, thread-safe way to report progress made on some task.
Definition: Progress.h:164
void autoAddCallReturnEdges(bool b)
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2296
bool basicBlockSemanticsAutoDrop() const
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:925
bool basicBlockSemanticsAutoDrop
Conserve memory by dropping semantics for attached basic blocks.
Definition: BasicTypes.h:257
ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:569
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:604
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:296
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2115
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2061
API and storage for attributes.
Definition: Attribute.h:208
Represents no value.
Definition: Optional.h:32
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:484
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:292
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2339
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:490
Virtual base class for instruction disassemblers.
Definition: Disassembler.h:41
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:322
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2297
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:294
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:297
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2362
Holds configuration information.
Definition: Config.h:210