ROSE  0.9.11.151
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.
57 #if __cplusplus >= 201103L
58  #define ROSE_PARTITIONER_MOVE
59 #elif defined(__GNUC__)
60  #if __GNUC__ > 5
61  #define ROSE_PARTITIONER_MOVE
62  #elif BOOST_VERSION >= 106900 // 1.68.0 might be okay too, but ROSE blacklists it for other reasons
63  #define ROSE_PARTITIONER_MOVE
64  #endif
65 #endif
66 
67 namespace Rose {
68 namespace BinaryAnalysis {
69 
101 namespace Partitioner2 {
102 
316 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
317 #ifdef ROSE_PARTITIONER_MOVE
318  BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
319 #endif
320 
321 public:
324  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
325  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
328  struct Thunk {
330  rose_addr_t target;
331  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
332  };
333 
336 
337 private:
338  BasePartitionerSettings settings_; // settings adjustable from the command-line
339  Configuration config_; // configuration information about functions, blocks, etc.
340  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
341  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
342  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
343  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
344  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
345  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
346  Functions functions_; // List of all attached functions by entry address
347  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
348  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
349  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
350  AddressNameMap addressNames_; // Names for various addresses
351  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
352  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
353  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
354 
355  // Callback lists
356  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
357  BasicBlockCallbacks basicBlockCallbacks_;
358  FunctionPrologueMatchers functionPrologueMatchers_;
359  FunctionPaddingMatchers functionPaddingMatchers_;
360 
361  // Special CFG vertices.
362  ControlFlowGraph::VertexIterator undiscoveredVertex_;
363  ControlFlowGraph::VertexIterator indeterminateVertex_;
364  ControlFlowGraph::VertexIterator nonexistingVertex_;
365  static const size_t nSpecialVertices = 3;
366 
367  // Protects the following data members
368  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
369  Progress::Ptr progress_; // Progress reporter to update, or null
370  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
371 
372 
375  //
376  // Serialization
377  //
380 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
381 private:
382  friend class boost::serialization::access;
383 
384  template<class S>
385  void serializeCommon(S &s, const unsigned /*version*/) {
386  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
387  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
388  s.template register_type<InstructionSemantics2::DispatcherX86>();
389  s.template register_type<InstructionSemantics2::DispatcherM68k>();
390  s.template register_type<InstructionSemantics2::DispatcherPowerpc>();
391  s.template register_type<SymbolicExpr::Interior>();
392  s.template register_type<SymbolicExpr::Leaf>();
393  s.template register_type<YicesSolver>();
394  s.template register_type<Z3Solver>();
395  s.template register_type<Semantics::SValue>();
396  s.template register_type<Semantics::MemoryListState>();
397  s.template register_type<Semantics::MemoryMapState>();
398  s.template register_type<Semantics::RegisterState>();
399  s.template register_type<Semantics::State>();
400  s.template register_type<Semantics::RiscOperators>();
401  s & BOOST_SERIALIZATION_NVP(settings_);
402  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
403  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
404  s & BOOST_SERIALIZATION_NVP(memoryMap_);
405  s & BOOST_SERIALIZATION_NVP(cfg_);
406  // s & vertexIndex_; -- initialized by rebuildVertexIndices
407  s & BOOST_SERIALIZATION_NVP(aum_);
408  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
409  s & BOOST_SERIALIZATION_NVP(functions_);
410  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
411  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
412  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
413  s & BOOST_SERIALIZATION_NVP(addressNames_);
414  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
415  // s & unparser_; -- not saved; restored from disassembler
416  // s & cfgAdjustmentCallbacks_; -- not saved/restored
417  // s & basicBlockCallbacks_; -- not saved/restored
418  // s & functionPrologueMatchers_; -- not saved/restored
419  // s & functionPaddingMatchers_; -- not saved/restored
420  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
421  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
422  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
423  // s & progress_; -- not saved/restored
424  // s & cfgProgressTotal_; -- not saved/restored
425  }
426 
427  template<class S>
428  void save(S &s, const unsigned version) const {
429  const_cast<Partitioner*>(this)->serializeCommon(s, version);
430  }
431 
432  template<class S>
433  void load(S &s, const unsigned version) {
434  serializeCommon(s, version);
435  rebuildVertexIndices();
436  }
437 
438  BOOST_SERIALIZATION_SPLIT_MEMBER();
439 #endif
440 
441 
444  //
445  // Constructors
446  //
449 public:
454  Partitioner();
455 
460  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
461 
462 #ifdef ROSE_PARTITIONER_MOVE
463 
464  Partitioner(BOOST_RV_REF(Partitioner));
465 
467  Partitioner& operator=(BOOST_RV_REF(Partitioner));
468 #else
469  // These are unsafe
470  Partitioner(const Partitioner&);
471  Partitioner& operator=(const Partitioner&);
472 #endif
473 
474  ~Partitioner();
475 
482  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
483 
485  void clear() /*final*/;
486 
494  Configuration& configuration() { return config_; }
495  const Configuration& configuration() const { return config_; }
503  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
504  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
516  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
522  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
523  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
524  }
525 
528  //
529  // Unparsing
530  //
533 
543  Unparser::BasePtr unparser() const /*final*/;
544  void unparser(const Unparser::BasePtr&) /*final*/;
556  Unparser::BasePtr insnUnparser() const /*final*/;
557  void insnUnparser(const Unparser::BasePtr&) /*final*/;
568  std::string unparse(SgAsmInstruction*) const;
569  void unparse(std::ostream&, SgAsmInstruction*) const;
570  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
571  void unparse(std::ostream&, const DataBlock::Ptr&) const;
572  void unparse(std::ostream&, const Function::Ptr&) const;
573  void unparse(std::ostream&) const;
576  //
579  // Partitioner CFG queries
580  //
583 public:
589  size_t nBytes() const /*final*/ { return aum_.size(); }
590 
598  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
599  return undiscoveredVertex_;
600  }
601  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
602  return undiscoveredVertex_;
603  }
616  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
617  return indeterminateVertex_;
618  }
619  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
620  return indeterminateVertex_;
621  }
633  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
634  return nonexistingVertex_;
635  }
636  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
637  return nonexistingVertex_;
638  }
647  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
648 
655  const AddressUsageMap& aum() const /*final*/ { return aum_; }
656 
658  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
659 
664  std::vector<AddressUser> users(rose_addr_t) const /*final*/;
665 
673  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
674 
703  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
704  const Function::Ptr &function = Function::Ptr()) const /*final*/;
705  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
706  const Function::Ptr &function = Function::Ptr()) const /*final*/;
743  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
744  const Function::Ptr &sourceFunction = Function::Ptr(),
745  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
746  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
747  const Function::Ptr &sourceFunction = Function::Ptr(),
748  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
753  //
756  // Partitioner instruction operations
757  //
760 public:
766  size_t nInstructions() const /*final*/;
767 
777  AddressUser instructionExists(rose_addr_t startVa) const /*final*/ {
778  return aum_.findInstruction(startVa);
779  }
781  return aum_.findInstruction(insn);
782  }
791  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
792 
801  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
802 
811  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
812 
822  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
823 
831  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
832 
845  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
846 
851  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
852 
853 
856  //
857  // Partitioner basic block placeholder operations
858  //
861 public:
871  size_t nPlaceholders() const /*final*/;
872 
881  bool placeholderExists(rose_addr_t startVa) const /*final*/;
882 
893  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
894  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
895  return *found;
896  return cfg_.vertices().end();
897  }
898  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
899  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
900  return *found;
901  return cfg_.vertices().end();
902  }
921  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
922 
936  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
937  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
942  //
945  // Partitioner basic block operations
946  //
949 public:
963  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
975  void basicBlockDropSemantics() const /*final*/;
976 
985  size_t nBasicBlocks() const /*final*/;
986 
994  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
995 
1017  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
1018  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
1030  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
1031 
1042  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1043 
1053  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1054 
1061  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1062 
1072  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1073 
1079  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1080 
1105  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1106  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1107  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1122  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1123  SgAsmInstruction *insn) /*final*/;
1124 
1157  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1158  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1246  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1247  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1264  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
1265  Precision::Level precision = Precision::HIGH) const /*final*/;
1266 
1275  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1276 
1295  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1296 
1306  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;
1307 
1318  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1319 
1324  bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;
1325 
1365  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1366  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1377  void forgetStackDeltas() const /*final*/;
1378  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1390  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1391  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1444  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1445 
1446  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1455  void basicBlockMayReturnReset() const /*final*/;
1456 
1457 private:
1458  // Per-vertex data used during may-return analysis
1459  struct MayReturnVertexInfo {
1460  enum State {INIT, CALCULATING, FINISHED};
1461  State state; // current state of vertex
1462  bool processedCallees; // have we processed BBs this vertex calls?
1463  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1464  boost::logic::tribool result; // final result (eventually cached in BB)
1465  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1466  };
1467 
1468  // Is edge significant for analysis? See .C file for full documentation.
1469  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1470  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1471 
1472  // Determine (and cache in vertexInfo) whether any callees return.
1473  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1474  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1475 
1476  // Maximum may-return result from significant successors including phantom call-return edge.
1477  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1478  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1479 
1480  // The guts of the may-return analysis
1481  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1482  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1483 
1484 
1485 
1488  //
1489  // Partitioner data block operations
1490  //
1493 public:
1499  size_t nDataBlocks() const /*final*/;
1500 
1507  DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1508 
1517  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1518 
1530  DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;
1531 
1538  void detachDataBlock(const DataBlock::Ptr&) /*final*/;
1539 
1549  DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;
1550 
1563  DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;
1564 
1574  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1575 
1585  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1586 
1596  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1597 
1604  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1605 
1611  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1612 
1613 
1614 
1617  //
1618  // Partitioner function operations
1619  //
1622 public:
1628  size_t nFunctions() const /*final*/ { return functions_.size(); }
1629 
1648  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1649  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1650  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1658  std::vector<Function::Ptr> functions() const /*final*/;
1659 
1669  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1670 
1681  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1682 
1692  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1693 
1710  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1711  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1712  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1713  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1714  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1715  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1737  size_t attachFunction(const Function::Ptr&) /*final*/;
1738  size_t attachFunctions(const Functions&) /*final*/;
1754  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1755 
1772  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1773  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1789  void detachFunction(const Function::Ptr&) /*final*/;
1790 
1825  std::vector<Function::Ptr>
1826  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1827 
1828  std::vector<Function::Ptr>
1829  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1830 
1831  std::vector<Function::Ptr>
1832  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1833 
1834  std::vector<Function::Ptr>
1835  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1836 
1837  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1838  std::vector<Function::Ptr>
1839  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1840  std::vector<Function::Ptr> retval;
1841  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1842  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1843  insertUnique(retval, function, sortFunctionsByAddress);
1844  }
1845  return retval;
1846  }
1858  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1859 
1871  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1872 
1882  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1883 
1894  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1895 
1902  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1903 
1911  FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;
1912 
1932  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1933 
1937  void allFunctionStackDelta() const /*final*/;
1938 
1945  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1946 
1950  void allFunctionMayReturn() const /*final*/;
1951 
1978  const CallingConvention::Analysis&
1979  functionCallingConvention(const Function::Ptr&,
1980  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1981  const /*final*/;
1982 
1995  void
1996  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1997  const /*final*/;
1998 
2024  CallingConvention::Dictionary
2025  functionCallingConventionDefinitions(const Function::Ptr&,
2026  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2027  const /*final*/;
2028 
2041  void
2042  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
2043  CallingConvention::Definition::Ptr()) const /*final*/;
2044 
2053  void fixInterFunctionEdges() /*final*/;
2054  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2074  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2075 
2081  void allFunctionIsNoop() const /*final*/;
2082 
2090  void forgetFunctionIsNoop() const /*final*/;
2091  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2098  std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;
2099 
2100 
2101 
2104  //
2105  // Callbacks
2106  //
2109 public:
2127  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2128  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2139  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2140  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2143 public:
2151  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2152  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2174  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2175 
2176 public:
2182  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2183  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2193  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2194 
2195 
2196 
2199  //
2200  // Partitioner miscellaneous
2201  //
2204 public:
2216  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2217  bool computeProperties=true) const /*final*/;
2218 
2232  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2233  bool showNeighbors=true) const /*final*/;
2234 
2240  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2241  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2247  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2248 
2254  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2255  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2263  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2264  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2272  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2273  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2279  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2280 
2284  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2285 
2289  static std::string functionName(const Function::Ptr&) /*final*/;
2290 
2308  Progress::Ptr progress() const /*final*/;
2309  void progress(const Progress::Ptr&) /*final*/;
2316  void updateProgress(const std::string &phase, double completion) const;
2317 
2319  void showStatistics() const;
2320 
2321  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2322  void checkConsistency() const;
2323 
2325  // Settings
2327 public:
2328 
2336  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2337  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2348  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2349  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2350  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2374  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2375  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2392  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2393  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2405  void addressName(rose_addr_t, const std::string&) /*final*/;
2406  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2407  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2417  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2418  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2422  //
2425  // Instruction semantics
2426  //
2429 public:
2439  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2440  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2449  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2450 
2461  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2462  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2472  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2473 
2474 
2475 
2478  //
2479  // Python API support functions
2480  //
2483 #ifdef ROSE_ENABLE_PYTHON_API
2484  void pythonUnparse() const;
2485 #endif
2486 
2487 
2488 
2491  //
2492  // Partitioner internal utilities
2493  //
2496 private:
2497  void init(Disassembler*, const MemoryMap::Ptr&);
2498  void init(const Partitioner&);
2499  void updateCfgProgress();
2500 
2501 private:
2502  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2503  // and destination CFGs are identical.
2504  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2505  ControlFlowGraph::ConstVertexIterator otherIter);
2506 
2507  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2508  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2509  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2510 
2511  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2512  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2513  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2514 
2515  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2516  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2517 
2518  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2519  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2520  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2521 
2522  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2523  // The call happens immediately after the CFG/AUM are updated.
2524  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2525 
2526  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2527  void rebuildVertexIndices();
2528 };
2529 
2530 } // namespace
2531 } // namespace
2532 } // namespace
2533 
2534 #endif
Represents information about a thunk.
Definition: Partitioner.h:328
size_t size() const
Number of addresses represented by the map.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:323
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2152
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2449
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:329
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2151
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2406
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2349
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2418
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:619
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:495
Base class for machine instructions.
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2183
AddressUser instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:780
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:647
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:616
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:503
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1442
Main namespace for the ROSE library.
Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
Map address to name.
Definition: Partitioner.h:335
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2139
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:598
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2439
Name space for the entire library.
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:494
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2393
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:898
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:655
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2407
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:2337
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2392
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:330
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:633
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:482
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2350
SemanticMemoryParadigm
Organization of semantic memory.
Definition: BasicTypes.h:80
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2140
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:964
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:1391
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:504
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:2374
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:963
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:601
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:636
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:324
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2182
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2128
API and storage for attributes.
Definition: Attribute.h:208
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:516
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:316
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2417
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:522
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:2348
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2375
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:322
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:325
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2440
Holds configuration information.
Definition: Config.h:210