ROSE  0.11.4.0
Partitioner.h
1 #ifndef ROSE_Partitioner2_Partitioner_H
2 #define ROSE_Partitioner2_Partitioner_H
3 
4 #include <rosePublicConfig.h>
5 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
6 
7 #include <Partitioner2/AddressUsageMap.h>
8 #include <Partitioner2/BasicBlock.h>
9 #include <Partitioner2/BasicTypes.h>
10 #include <Partitioner2/Config.h>
11 #include <Partitioner2/ControlFlowGraph.h>
12 #include <Partitioner2/DataBlock.h>
13 #include <Partitioner2/Function.h>
14 #include <Partitioner2/FunctionCallGraph.h>
15 #include <Partitioner2/InstructionProvider.h>
16 #include <Partitioner2/Modules.h>
17 #include <Partitioner2/Reference.h>
18 
19 #include <Sawyer/Attribute.h>
20 #include <Sawyer/Callbacks.h>
21 #include <Sawyer/IntervalSet.h>
22 #include <Sawyer/Map.h>
23 #include <Sawyer/Message.h>
24 #include <Sawyer/Optional.h>
25 #include <Sawyer/ProgressBar.h>
26 #include <Sawyer/SharedPointer.h>
27 
28 #include <BinarySourceLocations.h>
29 #include <BinaryUnparser.h>
30 #include <Progress.h>
31 
32 #include <boost/filesystem.hpp>
33 #include <boost/move/utility_core.hpp>
34 #include <boost/serialization/access.hpp>
35 #include <boost/serialization/split_member.hpp>
36 #include <boost/serialization/version.hpp>
37 
38 #include <ostream>
39 #include <set>
40 #include <string>
41 #include <vector>
42 
43 // Derived classes needed for serialization
44 #include <BinaryYicesSolver.h>
45 #include <BinaryZ3Solver.h>
46 #include <DispatcherA64.h>
47 #include <DispatcherM68k.h>
48 #include <DispatcherPowerpc.h>
49 #include <DispatcherX86.h>
50 
51 // Define ROSE_PARTITIONER_MOVE if boost::move works. Mainly this is to work around a GCC bug that reports this error:
52 //
53 // prototype for
54 // 'Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)'
55 // does not match any in class 'Rose::BinaryAnalysis::Partitioner2::Partitioner'
56 //
57 // followed by saying that the exact same signature is one of the candidates:
58 //
59 // candidates are:
60 // Rose::BinaryAnalysis::Partitioner2::Partitioner::Partitioner(boost::rv<Rose::BinaryAnalysis::Partitioner2::Partitioner>&)
61 //
62 // This is apparently GCC issue 49377 [https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49377] fixed in GCC-6.1.0.
63 #if __cplusplus >= 201103L
64  #define ROSE_PARTITIONER_MOVE
65 #elif defined(__GNUC__)
66  #if __GNUC__ > 5
67  #define ROSE_PARTITIONER_MOVE
68  #elif BOOST_VERSION >= 106900 // 1.68.0 might be okay too, but ROSE blacklists it for other reasons
69  #define ROSE_PARTITIONER_MOVE
70  #endif
71 #endif
72 
73 namespace Rose {
74 namespace BinaryAnalysis {
75 
107 namespace Partitioner2 {
108 
322 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
323 #ifdef ROSE_PARTITIONER_MOVE
324  BOOST_MOVABLE_BUT_NOT_COPYABLE(Partitioner)
325 #endif
326 
327 public:
330  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
331  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
334  struct Thunk {
336  rose_addr_t target;
337  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
338  };
339 
342 
343 private:
344  BasePartitionerSettings settings_; // settings adjustable from the command-line
345  Configuration config_; // configuration information about functions, blocks, etc.
346  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
347  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
348  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
349  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
350  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
351  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
352  Functions functions_; // List of all attached functions by entry address
353  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
354  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
355  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
356  AddressNameMap addressNames_; // Names for various addresses
357  SourceLocations sourceLocations_; // Mapping between source locations and addresses
358  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
359  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
360  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
361 
362  // Callback lists
363  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
364  BasicBlockCallbacks basicBlockCallbacks_;
365  FunctionPrologueMatchers functionPrologueMatchers_;
366  FunctionPaddingMatchers functionPaddingMatchers_;
367 
368  // Special CFG vertices.
369  ControlFlowGraph::VertexIterator undiscoveredVertex_;
370  ControlFlowGraph::VertexIterator indeterminateVertex_;
371  ControlFlowGraph::VertexIterator nonexistingVertex_;
372  static const size_t nSpecialVertices = 3;
373 
374  // Protects the following data members
375  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
376  Progress::Ptr progress_; // Progress reporter to update, or null
377  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
378 
379 
382  //
383  // Serialization
384  //
387 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
388 private:
389  friend class boost::serialization::access;
390 
391  template<class S>
392  void serializeCommon(S &s, const unsigned version) {
393  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
394  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
395 #ifdef ROSE_ENABLE_ASM_A64
396  s.template register_type<InstructionSemantics2::DispatcherA64>();
397 #endif
398  s.template register_type<InstructionSemantics2::DispatcherX86>();
399  s.template register_type<InstructionSemantics2::DispatcherM68k>();
400  s.template register_type<InstructionSemantics2::DispatcherPowerpc>();
401  s.template register_type<SymbolicExpr::Interior>();
402  s.template register_type<SymbolicExpr::Leaf>();
403  s.template register_type<YicesSolver>();
404  s.template register_type<Z3Solver>();
405  s.template register_type<Semantics::SValue>();
406  s.template register_type<Semantics::MemoryListState>();
407  s.template register_type<Semantics::MemoryMapState>();
408  s.template register_type<Semantics::RegisterState>();
409  s.template register_type<Semantics::State>();
410  s.template register_type<Semantics::RiscOperators>();
411  s & BOOST_SERIALIZATION_NVP(settings_);
412  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
413  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
414  s & BOOST_SERIALIZATION_NVP(memoryMap_);
415  s & BOOST_SERIALIZATION_NVP(cfg_);
416  // s & vertexIndex_; -- initialized by rebuildVertexIndices
417  s & BOOST_SERIALIZATION_NVP(aum_);
418  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
419  s & BOOST_SERIALIZATION_NVP(functions_);
420  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
421  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
422  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
423  s & BOOST_SERIALIZATION_NVP(addressNames_);
424  if (version >= 1)
425  s & BOOST_SERIALIZATION_NVP(sourceLocations_);
426  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
427  // s & unparser_; -- not saved; restored from disassembler
428  // s & cfgAdjustmentCallbacks_; -- not saved/restored
429  // s & basicBlockCallbacks_; -- not saved/restored
430  // s & functionPrologueMatchers_; -- not saved/restored
431  // s & functionPaddingMatchers_; -- not saved/restored
432  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
433  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
434  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
435  // s & progress_; -- not saved/restored
436  // s & cfgProgressTotal_; -- not saved/restored
437  }
438 
439  template<class S>
440  void save(S &s, const unsigned version) const {
441  const_cast<Partitioner*>(this)->serializeCommon(s, version);
442  }
443 
444  template<class S>
445  void load(S &s, const unsigned version) {
446  serializeCommon(s, version);
447  rebuildVertexIndices();
448  }
449 
450  BOOST_SERIALIZATION_SPLIT_MEMBER();
451 #endif
452 
453 
456  //
457  // Constructors
458  //
461 public:
466  Partitioner();
467 
472  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
473 
474 #ifdef ROSE_PARTITIONER_MOVE
475 
476  Partitioner(BOOST_RV_REF(Partitioner));
477 
479  Partitioner& operator=(BOOST_RV_REF(Partitioner));
480 #else
481  // These are unsafe
482  Partitioner(const Partitioner&);
483  Partitioner& operator=(const Partitioner&);
484 #endif
485 
486  ~Partitioner();
487 
494  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
495 
497  void clear() /*final*/;
498 
506  Configuration& configuration() { return config_; }
507  const Configuration& configuration() const { return config_; }
515  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
516  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
528  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
534  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
535  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
536  }
537 
540  //
541  // Unparsing
542  //
545 
555  Unparser::BasePtr unparser() const /*final*/;
556  void unparser(const Unparser::BasePtr&) /*final*/;
568  Unparser::BasePtr insnUnparser() const /*final*/;
569  void insnUnparser(const Unparser::BasePtr&) /*final*/;
573  void configureInsnUnparser(const Unparser::BasePtr&) const /*final*/;
574 
583  std::string unparse(SgAsmInstruction*) const;
584  void unparse(std::ostream&, SgAsmInstruction*) const;
585  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
586  void unparse(std::ostream&, const DataBlock::Ptr&) const;
587  void unparse(std::ostream&, const Function::Ptr&) const;
588  void unparse(std::ostream&) const;
591  //
594  // Partitioner CFG queries
595  //
598 public:
604  size_t nBytes() const /*final*/ { return aum_.size(); }
605 
613  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
614  return undiscoveredVertex_;
615  }
616  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
617  return undiscoveredVertex_;
618  }
631  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
632  return indeterminateVertex_;
633  }
634  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
635  return indeterminateVertex_;
636  }
648  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
649  return nonexistingVertex_;
650  }
651  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
652  return nonexistingVertex_;
653  }
662  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
663 
670  const AddressUsageMap& aum() const /*final*/ { return aum_; }
671 
673  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
674 
679  std::vector<AddressUser> users(rose_addr_t) const /*final*/;
680 
688  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
689 
718  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
719  const Function::Ptr &function = Function::Ptr()) const /*final*/;
720  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
721  const Function::Ptr &function = Function::Ptr()) const /*final*/;
758  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
759  const Function::Ptr &sourceFunction = Function::Ptr(),
760  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
761  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
762  const Function::Ptr &sourceFunction = Function::Ptr(),
763  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
768  //
771  // Partitioner instruction operations
772  //
775 public:
781  size_t nInstructions() const /*final*/;
782 
792  AddressUser instructionExists(rose_addr_t startVa) const /*final*/ {
793  return aum_.findInstruction(startVa);
794  }
796  return aum_.findInstruction(insn);
797  }
806  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
807 
816  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
817 
826  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
827 
837  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
838 
846  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
847 
860  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
861 
866  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
867 
868 
871  //
872  // Partitioner basic block placeholder operations
873  //
876 public:
886  size_t nPlaceholders() const /*final*/;
887 
896  bool placeholderExists(rose_addr_t startVa) const /*final*/;
897 
908  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
909  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
910  return *found;
911  return cfg_.vertices().end();
912  }
913  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
914  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
915  return *found;
916  return cfg_.vertices().end();
917  }
936  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
937 
951  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
952  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
957  //
960  // Partitioner basic block operations
961  //
964 public:
978  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
990  void basicBlockDropSemantics() const /*final*/;
991 
1000  size_t nBasicBlocks() const /*final*/;
1001 
1009  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
1010 
1032  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
1033  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
1045  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
1046 
1057  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1058 
1068  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1069 
1076  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1077 
1087  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1088 
1094  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1095 
1120  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1121  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1122  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1137  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1138  SgAsmInstruction *insn) /*final*/;
1139 
1172  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1173  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1261  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1262  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1279  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
1280  Precision::Level precision = Precision::HIGH) const /*final*/;
1281 
1290  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1291 
1310  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1311 
1321  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;
1322 
1333  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1334 
1339  bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;
1340 
1380  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1381  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1392  void forgetStackDeltas() const /*final*/;
1393  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1405  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1406  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1459  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1460 
1461  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1470  void basicBlockMayReturnReset() const /*final*/;
1471 
1472 private:
1473  // Per-vertex data used during may-return analysis
1474  struct MayReturnVertexInfo {
1475  enum State {INIT, CALCULATING, FINISHED};
1476  State state; // current state of vertex
1477  bool processedCallees; // have we processed BBs this vertex calls?
1478  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1479  boost::logic::tribool result; // final result (eventually cached in BB)
1480  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1481  };
1482 
1483  // Is edge significant for analysis? See .C file for full documentation.
1484  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1485  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1486 
1487  // Determine (and cache in vertexInfo) whether any callees return.
1488  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1489  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1490 
1491  // Maximum may-return result from significant successors including phantom call-return edge.
1492  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1493  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1494 
1495  // The guts of the may-return analysis
1496  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1497  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1498 
1499 
1500 
1503  //
1504  // Partitioner data block operations
1505  //
1508 public:
1514  size_t nDataBlocks() const /*final*/;
1515 
1522  DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1523 
1532  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1533 
1545  DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;
1546 
1553  void detachDataBlock(const DataBlock::Ptr&) /*final*/;
1554 
1564  DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;
1565 
1578  DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;
1579 
1589  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1590 
1600  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1601 
1611  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1612 
1619  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1620 
1626  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1627 
1628 
1629 
1632  //
1633  // Partitioner function operations
1634  //
1637 public:
1643  size_t nFunctions() const /*final*/ { return functions_.size(); }
1644 
1663  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1664  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1665  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1673  std::vector<Function::Ptr> functions() const /*final*/;
1674 
1684  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1685 
1696  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1697 
1707  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1708 
1725  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1726  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1727  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1728  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1729  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1730  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1752  size_t attachFunction(const Function::Ptr&) /*final*/;
1753  size_t attachFunctions(const Functions&) /*final*/;
1769  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1770 
1787  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1788  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1804  void detachFunction(const Function::Ptr&) /*final*/;
1805 
1840  std::vector<Function::Ptr>
1841  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1842 
1843  std::vector<Function::Ptr>
1844  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1845 
1846  std::vector<Function::Ptr>
1847  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1848 
1849  std::vector<Function::Ptr>
1850  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1851 
1852  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1853  std::vector<Function::Ptr>
1854  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1855  std::vector<Function::Ptr> retval;
1856  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1857  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1858  insertUnique(retval, function, sortFunctionsByAddress);
1859  }
1860  return retval;
1861  }
1873  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1874 
1886  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1887 
1897  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1898 
1909  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1910 
1917  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1918 
1926  FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;
1927 
1947  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1948 
1952  void allFunctionStackDelta() const /*final*/;
1953 
1960  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1961 
1965  void allFunctionMayReturn() const /*final*/;
1966 
1993  const CallingConvention::Analysis&
1994  functionCallingConvention(const Function::Ptr&,
1995  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1996  const /*final*/;
1997 
2010  void
2011  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2012  const /*final*/;
2013 
2039  CallingConvention::Dictionary
2040  functionCallingConventionDefinitions(const Function::Ptr&,
2041  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
2042  const /*final*/;
2043 
2056  void
2057  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
2058  CallingConvention::Definition::Ptr()) const /*final*/;
2059 
2068  void fixInterFunctionEdges() /*final*/;
2069  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2089  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2090 
2096  void allFunctionIsNoop() const /*final*/;
2097 
2105  void forgetFunctionIsNoop() const /*final*/;
2106  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2113  std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;
2114 
2115 
2116 
2119  //
2120  // Callbacks
2121  //
2124 public:
2142  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2143  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2154  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2155  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2158 public:
2166  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2167  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2194  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2195  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa, rose_addr_t &lastSearchedVa /*out*/) /*final*/;
2198 public:
2204  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2205  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2215  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2216 
2217 
2218 
2221  //
2222  // Partitioner miscellaneous
2223  //
2226 public:
2238  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2239  bool computeProperties=true) const /*final*/;
2240 
2254  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2255  bool showNeighbors=true) const /*final*/;
2256 
2262  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2263  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2269  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2270 
2276  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2277  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2285  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2286  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2294  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2295  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2301  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2302 
2306  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2307 
2311  static std::string functionName(const Function::Ptr&) /*final*/;
2312 
2317  void expandIndeterminateCalls();
2318 
2336  Progress::Ptr progress() const /*final*/;
2337  void progress(const Progress::Ptr&) /*final*/;
2344  void updateProgress(const std::string &phase, double completion) const;
2345 
2347  void showStatistics() const;
2348 
2349  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2350  void checkConsistency() const;
2351 
2353  // Settings
2355 public:
2356 
2364  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2365  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2376  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2377  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2378  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2402  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2403  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2420  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2421  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2433  void addressName(rose_addr_t, const std::string&) /*final*/;
2434  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2435  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2443  const SourceLocations& sourceLocations() const /*final*/ { return sourceLocations_; }
2444  SourceLocations& sourceLocations() /*final*/ { return sourceLocations_; }
2445  void sourceLocations(const SourceLocations &locs) { sourceLocations_ = locs; }
2455  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2456  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2460  //
2463  // Instruction semantics
2464  //
2467 public:
2477  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2478  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2487  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2488 
2499  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2500  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2510  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2511 
2512 
2513 
2516  //
2517  // Python API support functions
2518  //
2521 #ifdef ROSE_ENABLE_PYTHON_API
2522  void pythonUnparse() const;
2523 #endif
2524 
2525 
2526 
2529  //
2530  // Partitioner internal utilities
2531  //
2534 private:
2535  void init(Disassembler*, const MemoryMap::Ptr&);
2536  void init(const Partitioner&);
2537  void updateCfgProgress();
2538 
2539 private:
2540  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2541  // and destination CFGs are identical.
2542  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2543  ControlFlowGraph::ConstVertexIterator otherIter);
2544 
2545  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2546  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2547  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2548 
2549  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2550  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2551  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2552 
2553  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2554  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2555 
2556  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2557  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2558  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2559 
2560  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2561  // The call happens immediately after the CFG/AUM are updated.
2562  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2563 
2564  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2565  void rebuildVertexIndices();
2566 };
2567 
2568 } // namespace
2569 } // namespace
2570 } // namespace
2571 
2572 // Class versions must be at global scope
2573 BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::Partitioner, 1);
2574 
2575 #endif
2576 #endif
Represents information about a thunk.
Definition: Partitioner.h:334
size_t size() const
Number of addresses represented by the map.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:329
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2167
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2487
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:335
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2166
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2434
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2377
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2456
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:634
const SourceLocations & sourceLocations() const
Property: Source locations.
Definition: Partitioner.h:2443
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:507
Base class for machine instructions.
Bidirectional mapping between addresses and source locations.
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2205
AddressUser instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:795
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:662
Provides and caches instructions.
Settings that directly control a partitioner.
Definition: BasicTypes.h:305
STL namespace.
Holds a value or nothing.
Definition: Optional.h:49
ControlFlowGraph::VertexIterator indeterminateVertex()
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:631
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:515
void sourceLocations(const SourceLocations &locs)
Property: Source locations.
Definition: Partitioner.h:2445
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:341
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2154
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:613
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2477
Name space for the entire library.
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:506
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2421
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:913
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:670
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2435
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: HashMap.h:434
void settings(const BasePartitionerSettings &s)
Partitioner settings.
Definition: Partitioner.h:2365
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2420
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:336
ControlFlowGraph::VertexIterator nonexistingVertex()
Returns the special "non-existing" vertex.
Definition: Partitioner.h:648
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:494
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2378
SemanticMemoryParadigm
Organization of semantic memory.
Definition: BasicTypes.h:85
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2155
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:979
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:1406
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:516
bool checkingCallBranch
Check for situations where CALL is used as a branch.
Definition: BasicTypes.h:310
bool usingSemantics
Whether instruction semantics are used.
Definition: BasicTypes.h:306
A general, thread-safe way to report progress made on some task.
Definition: Progress.h:165
void autoAddCallReturnEdges(bool b)
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2402
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:978
bool basicBlockSemanticsAutoDrop
Conserve memory by dropping semantics for attached basic blocks.
Definition: BasicTypes.h:311
ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:616
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:651
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:330
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2204
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2143
API and storage for attributes.
Definition: Attribute.h:208
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:528
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:322
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2455
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:534
Virtual base class for instruction disassemblers.
Definition: Disassembler.h:50
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:2376
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2403
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:328
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:331
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2478
Holds configuration information.
Definition: Config.h:282
SourceLocations & sourceLocations()
Property: Source locations.
Definition: Partitioner.h:2444