ROSE  0.9.11.56
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/move/utility_core.hpp>
30 #include <boost/serialization/access.hpp>
31 #include <boost/serialization/split_member.hpp>
32 
33 #include <ostream>
34 #include <set>
35 #include <string>
36 #include <vector>
37 
38 // Derived classes needed for serialization
39 #include <BinaryYicesSolver.h>
40 #include <BinaryZ3Solver.h>
41 #include <DispatcherM68k.h>
42 #include <DispatcherPowerpc.h>
43 #include <DispatcherX86.h>
44 
45 // Define ROSE_PARTITIONER_MOVE if boost::move works. Mainly this is to work around a GCC bug that reports this error:
46 //
47 // prototype for
48 // 'Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)'
49 // does not match any in class 'Rose::BinaryAnalysis::Partitioner2::Partitioner'
50 //
51 // followed by saying that the exact same signature is one of the candidates:
52 //
53 // candidates are:
54 // Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)
55 //
56 // This is apparently GCC issue 49377 [https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49377] fixed in GCC-6.1.0, however we've
57 // seen it on a more limited basis so far.
58 #if __cplusplus >= 201103L
59  #define ROSE_PARTITIONER_MOVE
60 #elif defined(__GNUC__)
61  #if __GNUC__ > 4
62  #define ROSE_PARTITIONER_MOVE
63  #elif BOOST_VERSION >= 106900 // 1.68.0 might be okay too, but ROSE blacklists it for other reasons
64  #define ROSE_PARTITIONER_MOVE
65  #endif
66 #endif
67 
68 namespace Rose {
69 namespace BinaryAnalysis {
70 
102 namespace Partitioner2 {
103 
317 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
318 #ifdef ROSE_PARTITIONER_MOVE
319  BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
320 #endif
321 
322 public:
325  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
326  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
329  struct Thunk {
331  rose_addr_t target;
332  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
333  };
334 
337 
338 private:
339  BasePartitionerSettings settings_; // settings adjustable from the command-line
340  Configuration config_; // configuration information about functions, blocks, etc.
341  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
342  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
343  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
344  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
345  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
346  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
347  Functions functions_; // List of all attached functions by entry address
348  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
349  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
350  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
351  AddressNameMap addressNames_; // Names for various addresses
352  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
353  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
354  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
355 
356  // Callback lists
357  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
358  BasicBlockCallbacks basicBlockCallbacks_;
359  FunctionPrologueMatchers functionPrologueMatchers_;
360  FunctionPaddingMatchers functionPaddingMatchers_;
361 
362  // Special CFG vertices.
363  ControlFlowGraph::VertexIterator undiscoveredVertex_;
364  ControlFlowGraph::VertexIterator indeterminateVertex_;
365  ControlFlowGraph::VertexIterator nonexistingVertex_;
366  static const size_t nSpecialVertices = 3;
367 
368  // Protects the following data members
369  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
370  Progress::Ptr progress_; // Progress reporter to update, or null
371  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
372 
373 
376  //
377  // Serialization
378  //
381 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
382 private:
383  friend class boost::serialization::access;
384 
385  template<class S>
386  void serializeCommon(S &s, const unsigned /*version*/) {
387  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
388  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
389  s.template register_type<InstructionSemantics2::DispatcherX86>();
390  s.template register_type<InstructionSemantics2::DispatcherM68k>();
391  s.template register_type<InstructionSemantics2::DispatcherPowerpc>();
392  s.template register_type<SymbolicExpr::Interior>();
393  s.template register_type<SymbolicExpr::Leaf>();
394  s.template register_type<YicesSolver>();
395  s.template register_type<Z3Solver>();
396  s.template register_type<Semantics::SValue>();
397  s.template register_type<Semantics::MemoryListState>();
398  s.template register_type<Semantics::MemoryMapState>();
399  s.template register_type<Semantics::RegisterState>();
400  s.template register_type<Semantics::State>();
401  s.template register_type<Semantics::RiscOperators>();
402  s & BOOST_SERIALIZATION_NVP(settings_);
403  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
404  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
405  s & BOOST_SERIALIZATION_NVP(memoryMap_);
406  s & BOOST_SERIALIZATION_NVP(cfg_);
407  // s & vertexIndex_; -- initialized by rebuildVertexIndices
408  s & BOOST_SERIALIZATION_NVP(aum_);
409  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
410  s & BOOST_SERIALIZATION_NVP(functions_);
411  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
412  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
413  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
414  s & BOOST_SERIALIZATION_NVP(addressNames_);
415  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
416  // s & unparser_; -- not saved; restored from disassembler
417  // s & cfgAdjustmentCallbacks_; -- not saved/restored
418  // s & basicBlockCallbacks_; -- not saved/restored
419  // s & functionPrologueMatchers_; -- not saved/restored
420  // s & functionPaddingMatchers_; -- not saved/restored
421  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
422  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
423  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
424  // s & progress_; -- not saved/restored
425  // s & cfgProgressTotal_; -- not saved/restored
426  }
427 
428  template<class S>
429  void save(S &s, const unsigned version) const {
430  const_cast<Partitioner*>(this)->serializeCommon(s, version);
431  }
432 
433  template<class S>
434  void load(S &s, const unsigned version) {
435  serializeCommon(s, version);
436  rebuildVertexIndices();
437  }
438 
439  BOOST_SERIALIZATION_SPLIT_MEMBER();
440 #endif
441 
442 
445  //
446  // Constructors
447  //
450 public:
455  Partitioner();
456 
461  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
462 
463 #ifdef ROSE_PARTITIONER_MOVE
464 
465  Partitioner(BOOST_RV_REF(Partitioner));
466 
468  Partitioner& operator=(BOOST_RV_REF(Partitioner));
469 #else
470  // These are unsafe
471  Partitioner(const Partitioner&);
472  Partitioner& operator=(const Partitioner&);
473 #endif
474 
475  ~Partitioner();
476 
483  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
484 
486  void clear() /*final*/;
487 
495  Configuration& configuration() { return config_; }
496  const Configuration& configuration() const { return config_; }
504  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
505  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
517  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
523  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
524  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
525  }
526 
529  //
530  // Unparsing
531  //
534 
544  Unparser::BasePtr unparser() const /*final*/;
545  void unparser(const Unparser::BasePtr&) /*final*/;
557  Unparser::BasePtr insnUnparser() const /*final*/;
558  void insnUnparser(const Unparser::BasePtr&) /*final*/;
569  std::string unparse(SgAsmInstruction*) const;
570  void unparse(std::ostream&, SgAsmInstruction*) const;
571  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
572  void unparse(std::ostream&, const DataBlock::Ptr&) const;
573  void unparse(std::ostream&, const Function::Ptr&) const;
574  void unparse(std::ostream&) const;
577  //
580  // Partitioner CFG queries
581  //
584 public:
590  size_t nBytes() const /*final*/ { return aum_.size(); }
591 
599  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
600  return undiscoveredVertex_;
601  }
602  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
603  return undiscoveredVertex_;
604  }
617  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
618  return indeterminateVertex_;
619  }
620  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
621  return indeterminateVertex_;
622  }
634  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
635  return nonexistingVertex_;
636  }
637  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
638  return nonexistingVertex_;
639  }
648  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
649 
656  const AddressUsageMap& aum() const /*final*/ { return aum_; }
657 
659  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
660 
665  std::vector<AddressUser> users(rose_addr_t) const /*final*/;
666 
674  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
675 
704  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
705  const Function::Ptr &function = Function::Ptr()) const /*final*/;
706  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
707  const Function::Ptr &function = Function::Ptr()) const /*final*/;
744  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
745  const Function::Ptr &sourceFunction = Function::Ptr(),
746  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
747  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
748  const Function::Ptr &sourceFunction = Function::Ptr(),
749  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
754  //
757  // Partitioner instruction operations
758  //
761 public:
767  size_t nInstructions() const /*final*/;
768 
778  AddressUser instructionExists(rose_addr_t startVa) const /*final*/ {
779  return aum_.findInstruction(startVa);
780  }
782  return aum_.findInstruction(insn);
783  }
792  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
793 
802  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
803 
812  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
813 
823  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
824 
832  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
833 
846  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
847 
852  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
853 
854 
857  //
858  // Partitioner basic block placeholder operations
859  //
862 public:
872  size_t nPlaceholders() const /*final*/;
873 
882  bool placeholderExists(rose_addr_t startVa) const /*final*/;
883 
894  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
895  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
896  return *found;
897  return cfg_.vertices().end();
898  }
899  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
900  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
901  return *found;
902  return cfg_.vertices().end();
903  }
922  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
923 
937  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
938  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
943  //
946  // Partitioner basic block operations
947  //
950 public:
964  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
976  void basicBlockDropSemantics() const /*final*/;
977 
986  size_t nBasicBlocks() const /*final*/;
987 
995  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
996 
1018  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
1019  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
1031  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
1032 
1043  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1044 
1054  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1055 
1062  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1063 
1073  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1074 
1080  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1081 
1106  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1107  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1108  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1123  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1124  SgAsmInstruction *insn) /*final*/;
1125 
1158  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1159  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1247  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1248  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1265  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
1266  Precision::Level precision = Precision::HIGH) const /*final*/;
1267 
1276  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1277 
1296  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1297 
1307  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;
1308 
1319  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1320 
1325  bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;
1326 
1366  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1367  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1378  void forgetStackDeltas() const /*final*/;
1379  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1391  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1392  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1445  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1446 
1447  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1456  void basicBlockMayReturnReset() const /*final*/;
1457 
1458 private:
1459  // Per-vertex data used during may-return analysis
1460  struct MayReturnVertexInfo {
1461  enum State {INIT, CALCULATING, FINISHED};
1462  State state; // current state of vertex
1463  bool processedCallees; // have we processed BBs this vertex calls?
1464  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1465  boost::logic::tribool result; // final result (eventually cached in BB)
1466  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1467  };
1468 
1469  // Is edge significant for analysis? See .C file for full documentation.
1470  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1471  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1472 
1473  // Determine (and cache in vertexInfo) whether any callees return.
1474  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1475  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1476 
1477  // Maximum may-return result from significant successors including phantom call-return edge.
1478  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1479  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1480 
1481  // The guts of the may-return analysis
1482  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1483  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1484 
1485 
1486 
1489  //
1490  // Partitioner data block operations
1491  //
1494 public:
1500  size_t nDataBlocks() const /*final*/;
1501 
1508  DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1509 
1518  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1519 
1531  DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;
1532 
1539  void detachDataBlock(const DataBlock::Ptr&) /*final*/;
1540 
1550  DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;
1551 
1564  DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;
1565 
1575  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1576 
1586  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1587 
1597  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1598 
1605  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1606 
1612  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1613 
1614 
1615 
1618  //
1619  // Partitioner function operations
1620  //
1623 public:
1629  size_t nFunctions() const /*final*/ { return functions_.size(); }
1630 
1649  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1650  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1651  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1659  std::vector<Function::Ptr> functions() const /*final*/;
1660 
1670  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1671 
1682  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1683 
1693  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1694 
1711  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1712  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1713  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1714  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1715  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1716  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1738  size_t attachFunction(const Function::Ptr&) /*final*/;
1739  size_t attachFunctions(const Functions&) /*final*/;
1755  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1756 
1773  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1774  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1790  void detachFunction(const Function::Ptr&) /*final*/;
1791 
1826  std::vector<Function::Ptr>
1827  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1828 
1829  std::vector<Function::Ptr>
1830  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1831 
1832  std::vector<Function::Ptr>
1833  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1834 
1835  std::vector<Function::Ptr>
1836  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1837 
1838  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1839  std::vector<Function::Ptr>
1840  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1841  std::vector<Function::Ptr> retval;
1842  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1843  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1844  insertUnique(retval, function, sortFunctionsByAddress);
1845  }
1846  return retval;
1847  }
1859  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1860 
1872  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1873 
1883  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1884 
1895  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1896 
1903  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1904 
1912  FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;
1913 
1933  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1934 
1938  void allFunctionStackDelta() const /*final*/;
1939 
1946  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1947 
1951  void allFunctionMayReturn() const /*final*/;
1952 
1979  const CallingConvention::Analysis&
1980  functionCallingConvention(const Function::Ptr&,
1981  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1982  const /*final*/;
1983 
1996  void
1997  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1998  const /*final*/;
1999 
2025  CallingConvention::Dictionary
2026  functionCallingConventionDefinitions(const Function::Ptr&,
2027  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2028  const /*final*/;
2029 
2042  void
2043  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
2044  CallingConvention::Definition::Ptr()) const /*final*/;
2045 
2054  void fixInterFunctionEdges() /*final*/;
2055  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2075  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2076 
2082  void allFunctionIsNoop() const /*final*/;
2083 
2091  void forgetFunctionIsNoop() const /*final*/;
2092  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2099  std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;
2100 
2101 
2102 
2105  //
2106  // Callbacks
2107  //
2110 public:
2128  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2129  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2140  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2141  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2144 public:
2152  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2153  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2175  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2176 
2177 public:
2183  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2184  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2194  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2195 
2196 
2197 
2200  //
2201  // Partitioner miscellaneous
2202  //
2205 public:
2217  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2218  bool computeProperties=true) const /*final*/;
2219 
2233  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2234  bool showNeighbors=true) const /*final*/;
2235 
2241  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2242  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2248  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2249 
2255  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2256  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2264  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2265  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2273  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2274  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2280  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2281 
2285  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2286 
2290  static std::string functionName(const Function::Ptr&) /*final*/;
2291 
2309  Progress::Ptr progress() const /*final*/;
2310  void progress(const Progress::Ptr&) /*final*/;
2317  void updateProgress(const std::string &phase, double completion) const;
2318 
2320  void showStatistics() const;
2321 
2322  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2323  void checkConsistency() const;
2324 
2326  // Settings
2328 public:
2329 
2337  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2338  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2349  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2350  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2351  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2375  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2376  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2393  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2394  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2406  void addressName(rose_addr_t, const std::string&) /*final*/;
2407  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2408  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2418  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2419  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2423  //
2426  // Instruction semantics
2427  //
2430 public:
2440  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2441  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2450  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2451 
2462  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2463  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2473  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2474 
2475 
2476 
2479  //
2480  // Python API support functions
2481  //
2484 #ifdef ROSE_ENABLE_PYTHON_API
2485  void pythonUnparse() const;
2486 #endif
2487 
2488 
2489 
2492  //
2493  // Partitioner internal utilities
2494  //
2497 private:
2498  void init(Disassembler*, const MemoryMap::Ptr&);
2499  void init(const Partitioner&);
2500  void updateCfgProgress();
2501 
2502 private:
2503  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2504  // and destination CFGs are identical.
2505  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2506  ControlFlowGraph::ConstVertexIterator otherIter);
2507 
2508  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2509  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2510  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2511 
2512  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2513  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2514  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2515 
2516  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2517  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2518 
2519  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2520  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2521  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2522 
2523  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2524  // The call happens immediately after the CFG/AUM are updated.
2525  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2526 
2527  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2528  void rebuildVertexIndices();
2529 };
2530 
2531 } // namespace
2532 } // namespace
2533 } // namespace
2534 
2535 #endif
Represents information about a thunk.
Definition: Partitioner.h:329
size_t size() const
Number of addresses represented by the map.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:324
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2153
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2450
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:330
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2152
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2407
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2350
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2419
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:620
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:496
Base class for machine instructions.
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2184
AddressUser instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:781
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:648
Provides and caches instructions.
Settings that directly control a partitioner.
Definition: BasicTypes.h:277
STL namespace.
Holds a value or nothing.
Definition: Optional.h:49
ControlFlowGraph::VertexIterator indeterminateVertex()
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:617
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:504
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1462
Main namespace for the ROSE library.
Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
Map address to name.
Definition: Partitioner.h:336
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2140
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:599
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2440
Name space for the entire library.
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:495
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2394
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:899
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:656
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2408
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: HashMap.h:434
Base classes for instruction semantics.
void settings(const BasePartitionerSettings &s)
Partitioner settings.
Definition: Partitioner.h:2338
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2393
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:331
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:634
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:483
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2351
SemanticMemoryParadigm
Organization of semantic memory.
Definition: BasicTypes.h:80
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2141
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:965
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:577
void stackDeltaInterproceduralLimit(size_t n)
Property: max depth for inter-procedural stack delta analysis.
Definition: Partitioner.h:1392
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:505
bool checkingCallBranch
Check for situations where CALL is used as a branch.
Definition: BasicTypes.h:282
bool usingSemantics
Whether instruction semantics are used.
Definition: BasicTypes.h:278
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:2375
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
bool basicBlockSemanticsAutoDrop() const
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:964
bool basicBlockSemanticsAutoDrop
Conserve memory by dropping semantics for attached basic blocks.
Definition: BasicTypes.h:283
ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:602
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:637
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:325
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2183
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2129
API and storage for attributes.
Definition: Attribute.h:208
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:517
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:317
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2418
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:523
Virtual base class for instruction disassemblers.
Definition: Disassembler.h:48
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:386
void enableSymbolicSemantics(bool b=true)
Use or not use symbolic semantics.
Definition: Partitioner.h:2349
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2376
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:323
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:326
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2441
Holds configuration information.
Definition: Config.h:210