ROSE  0.9.11.42
Partitioner.h
1 #ifndef ROSE_Partitioner2_Partitioner_H
2 #define ROSE_Partitioner2_Partitioner_H
3 
4 #include <Partitioner2/AddressUsageMap.h>
5 #include <Partitioner2/BasicBlock.h>
6 #include <Partitioner2/BasicTypes.h>
7 #include <Partitioner2/Config.h>
8 #include <Partitioner2/ControlFlowGraph.h>
9 #include <Partitioner2/DataBlock.h>
10 #include <Partitioner2/Function.h>
11 #include <Partitioner2/FunctionCallGraph.h>
12 #include <Partitioner2/InstructionProvider.h>
13 #include <Partitioner2/Modules.h>
14 #include <Partitioner2/Reference.h>
15 
16 #include <Sawyer/Attribute.h>
17 #include <Sawyer/Callbacks.h>
18 #include <Sawyer/IntervalSet.h>
19 #include <Sawyer/Map.h>
20 #include <Sawyer/Message.h>
21 #include <Sawyer/Optional.h>
22 #include <Sawyer/ProgressBar.h>
23 #include <Sawyer/SharedPointer.h>
24 
25 #include <BinaryUnparser.h>
26 #include <Progress.h>
27 
28 #include <boost/filesystem.hpp>
29 #include <boost/serialization/access.hpp>
30 #include <boost/serialization/split_member.hpp>
31 
32 #include <ostream>
33 #include <set>
34 #include <string>
35 #include <vector>
36 
37 // Derived classes needed for serialization
38 #include <BinaryYicesSolver.h>
39 #include <BinaryZ3Solver.h>
40 #include <DispatcherM68k.h>
41 #include <DispatcherPowerpc.h>
42 #include <DispatcherX86.h>
43 
44 namespace Rose {
45 namespace BinaryAnalysis {
46 
78 namespace Partitioner2 {
79 
293 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
294 public:
297  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
298  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
301  struct Thunk {
303  rose_addr_t target;
304  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
305  };
306 
309 
310 private:
311  BasePartitionerSettings settings_; // settings adjustable from the command-line
312  Configuration config_; // configuration information about functions, blocks, etc.
313  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
314  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
315  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
316  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
317  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
318  SmtSolverPtr solver_; // Satisfiable modulo theory solver used by semantic expressions
319  Functions functions_; // List of all attached functions by entry address
320  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
321  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
322  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
323  AddressNameMap addressNames_; // Names for various addresses
324  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
325  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
326  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
327 
328  // Callback lists
329  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
330  BasicBlockCallbacks basicBlockCallbacks_;
331  FunctionPrologueMatchers functionPrologueMatchers_;
332  FunctionPaddingMatchers functionPaddingMatchers_;
333 
334  // Special CFG vertices.
335  ControlFlowGraph::VertexIterator undiscoveredVertex_;
336  ControlFlowGraph::VertexIterator indeterminateVertex_;
337  ControlFlowGraph::VertexIterator nonexistingVertex_;
338  static const size_t nSpecialVertices = 3;
339 
340  // Protects the following data members
341  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
342  Progress::Ptr progress_; // Progress reporter to update, or null
343  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
344 
345 
348  //
349  // Serialization
350  //
353 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
354 private:
355  friend class boost::serialization::access;
356 
357  template<class S>
358  void serializeCommon(S &s, const unsigned /*version*/) {
359  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
360  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
361  s.template register_type<InstructionSemantics2::DispatcherX86>();
362  s.template register_type<InstructionSemantics2::DispatcherM68k>();
363  s.template register_type<InstructionSemantics2::DispatcherPowerpc>();
364  s.template register_type<SymbolicExpr::Interior>();
365  s.template register_type<SymbolicExpr::Leaf>();
366  s.template register_type<YicesSolver>();
367  s.template register_type<Z3Solver>();
368  s.template register_type<Semantics::SValue>();
369  s.template register_type<Semantics::MemoryListState>();
370  s.template register_type<Semantics::MemoryMapState>();
371  s.template register_type<Semantics::RegisterState>();
372  s.template register_type<Semantics::State>();
373  s.template register_type<Semantics::RiscOperators>();
374  s & BOOST_SERIALIZATION_NVP(settings_);
375  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
376  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
377  s & BOOST_SERIALIZATION_NVP(memoryMap_);
378  s & BOOST_SERIALIZATION_NVP(cfg_);
379  // s & vertexIndex_; -- initialized by rebuildVertexIndices
380  s & BOOST_SERIALIZATION_NVP(aum_);
381  // s & BOOST_SERIALIZATION_NVP(solver_); -- not saved/restored in order to override from command-line
382  s & BOOST_SERIALIZATION_NVP(functions_);
383  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
384  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
385  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
386  s & BOOST_SERIALIZATION_NVP(addressNames_);
387  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
388  // s & unparser_; -- not saved; restored from disassembler
389  // s & cfgAdjustmentCallbacks_; -- not saved/restored
390  // s & basicBlockCallbacks_; -- not saved/restored
391  // s & functionPrologueMatchers_; -- not saved/restored
392  // s & functionPaddingMatchers_; -- not saved/restored
393  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
394  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
395  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
396  // s & progress_; -- not saved/restored
397  // s & cfgProgressTotal_; -- not saved/restored
398  }
399 
400  template<class S>
401  void save(S &s, const unsigned version) const {
402  const_cast<Partitioner*>(this)->serializeCommon(s, version);
403  }
404 
405  template<class S>
406  void load(S &s, const unsigned version) {
407  serializeCommon(s, version);
408  rebuildVertexIndices();
409  }
410 
411  BOOST_SERIALIZATION_SPLIT_MEMBER();
412 #endif
413 
414 
417  //
418  // Constructors
419  //
422 public:
427  Partitioner();
428 
433  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
434 
435  // FIXME[Robb P. Matzke 2014-11-08]: This is not ready for use yet. The problem is that because of the shallow copy, both
436  // partitioners are pointing to the same basic blocks, data blocks, and functions. This is okay by itself since these
437  // things are reference counted, but the paradigm of locked/unlocked blocks and functions breaks down somewhat -- does
438  // unlocking a basic block from one partitioner make it modifiable even though it's still locked in the other partitioner?
439  // FIXME[Robb P. Matzke 2014-12-27]: Not the most efficient implementation, but saves on cut-n-paste which would surely rot
440  // after a while.
441  Partitioner(const Partitioner &other);
442  Partitioner& operator=(const Partitioner &other);
443 
444  ~Partitioner();
445 
452  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
453 
455  void clear() /*final*/;
456 
464  Configuration& configuration() { return config_; }
465  const Configuration& configuration() const { return config_; }
473  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
474  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
486  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
492  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
493  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
494  }
495 
498  //
499  // Unparsing
500  //
503 
513  Unparser::BasePtr unparser() const /*final*/;
514  void unparser(const Unparser::BasePtr&) /*final*/;
526  Unparser::BasePtr insnUnparser() const /*final*/;
527  void insnUnparser(const Unparser::BasePtr&) /*final*/;
538  std::string unparse(SgAsmInstruction*) const;
539  void unparse(std::ostream&, SgAsmInstruction*) const;
540  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
541  void unparse(std::ostream&, const DataBlock::Ptr&) const;
542  void unparse(std::ostream&, const Function::Ptr&) const;
543  void unparse(std::ostream&) const;
546  //
549  // Partitioner CFG queries
550  //
553 public:
559  size_t nBytes() const /*final*/ { return aum_.size(); }
560 
568  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
569  return undiscoveredVertex_;
570  }
571  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
572  return undiscoveredVertex_;
573  }
586  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
587  return indeterminateVertex_;
588  }
589  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
590  return indeterminateVertex_;
591  }
603  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
604  return nonexistingVertex_;
605  }
606  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
607  return nonexistingVertex_;
608  }
617  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
618 
625  const AddressUsageMap& aum() const /*final*/ { return aum_; }
626 
628  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
629 
634  std::vector<AddressUser> users(rose_addr_t) const /*final*/;
635 
643  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
644 
673  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
674  const Function::Ptr &function = Function::Ptr()) const /*final*/;
675  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
676  const Function::Ptr &function = Function::Ptr()) const /*final*/;
713  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
714  const Function::Ptr &sourceFunction = Function::Ptr(),
715  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
716  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
717  const Function::Ptr &sourceFunction = Function::Ptr(),
718  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
723  //
726  // Partitioner instruction operations
727  //
730 public:
736  size_t nInstructions() const /*final*/;
737 
747  Sawyer::Optional<AddressUser> instructionExists(rose_addr_t startVa) const /*final*/ {
748  return aum_.instructionExists(startVa);
749  }
751  return insn==NULL ? Sawyer::Nothing() : instructionExists(insn->get_address());
752  }
761  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
762 
771  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
772 
781  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
782 
792  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
793 
801  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
802 
815  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
816 
821  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
822 
823 
826  //
827  // Partitioner basic block placeholder operations
828  //
831 public:
841  size_t nPlaceholders() const /*final*/;
842 
851  bool placeholderExists(rose_addr_t startVa) const /*final*/;
852 
863  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
864  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
865  return *found;
866  return cfg_.vertices().end();
867  }
868  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
869  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
870  return *found;
871  return cfg_.vertices().end();
872  }
891  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
892 
906  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
907  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
912  //
915  // Partitioner basic block operations
916  //
919 public:
933  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
945  void basicBlockDropSemantics() const /*final*/;
946 
955  size_t nBasicBlocks() const /*final*/;
956 
964  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
965 
987  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
988  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
1000  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
1001 
1012  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
1013 
1023  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1024 
1031  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1032 
1042  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1043 
1049  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1050 
1075  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1076  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1077  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1092  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1093  SgAsmInstruction *insn) /*final*/;
1094 
1127  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1128  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1216  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1217  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1234  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&,
1235  Precision::Level precision = Precision::HIGH) const /*final*/;
1236 
1245  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1246 
1265  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1266 
1276  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&, Precision::Level precision = Precision::HIGH) const /*final*/;
1277 
1288  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1289 
1294  bool basicBlockPopsStack(const BasicBlock::Ptr&) const /*final*/;
1295 
1335  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1336  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1347  void forgetStackDeltas() const /*final*/;
1348  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1360  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1361  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1414  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1415 
1416  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1425  void basicBlockMayReturnReset() const /*final*/;
1426 
1427 private:
1428  // Per-vertex data used during may-return analysis
1429  struct MayReturnVertexInfo {
1430  enum State {INIT, CALCULATING, FINISHED};
1431  State state; // current state of vertex
1432  bool processedCallees; // have we processed BBs this vertex calls?
1433  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1434  boost::logic::tribool result; // final result (eventually cached in BB)
1435  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1436  };
1437 
1438  // Is edge significant for analysis? See .C file for full documentation.
1439  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1440  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1441 
1442  // Determine (and cache in vertexInfo) whether any callees return.
1443  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1444  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1445 
1446  // Maximum may-return result from significant successors including phantom call-return edge.
1447  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1448  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1449 
1450  // The guts of the may-return analysis
1451  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1452  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1453 
1454 
1455 
1458  //
1459  // Partitioner data block operations
1460  //
1463 public:
1469  size_t nDataBlocks() const /*final*/;
1470 
1477  DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1478 
1487  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1488 
1500  DataBlock::Ptr attachDataBlock(const DataBlock::Ptr&) /*final*/;
1501 
1508  DataBlock::Ptr detachDataBlock(const DataBlock::Ptr&) /*final*/;
1509 
1519  DataBlock::Ptr attachDataBlockToFunction(const DataBlock::Ptr&, const Function::Ptr&) /*final*/;
1520 
1533  DataBlock::Ptr attachDataBlockToBasicBlock(const DataBlock::Ptr&, const BasicBlock::Ptr&) /*final*/;
1534 
1544  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1545 
1555  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1556 
1566  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1567 
1574  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1575 
1581  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1582 
1583 
1584 
1587  //
1588  // Partitioner function operations
1589  //
1592 public:
1598  size_t nFunctions() const /*final*/ { return functions_.size(); }
1599 
1618  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1619  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1620  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1628  std::vector<Function::Ptr> functions() const /*final*/;
1629 
1639  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1640 
1651  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1652 
1662  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1663 
1680  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1681  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1682  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1683  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1684  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1685  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1707  size_t attachFunction(const Function::Ptr&) /*final*/;
1708  size_t attachFunctions(const Functions&) /*final*/;
1724  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1725 
1742  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1743  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1759  void detachFunction(const Function::Ptr&) /*final*/;
1760 
1795  std::vector<Function::Ptr>
1796  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1797 
1798  std::vector<Function::Ptr>
1799  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1800 
1801  std::vector<Function::Ptr>
1802  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1803 
1804  std::vector<Function::Ptr>
1805  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1806 
1807  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1808  std::vector<Function::Ptr>
1809  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1810  std::vector<Function::Ptr> retval;
1811  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1812  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1813  insertUnique(retval, function, sortFunctionsByAddress);
1814  }
1815  return retval;
1816  }
1828  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1829 
1841  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1842 
1852  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1853 
1864  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1865 
1872  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1873 
1881  FunctionCallGraph functionCallGraph(AllowParallelEdges::Type allowParallelEdges) const /*final*/;
1882 
1902  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1903 
1907  void allFunctionStackDelta() const /*final*/;
1908 
1915  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1916 
1920  void allFunctionMayReturn() const /*final*/;
1921 
1948  const CallingConvention::Analysis&
1949  functionCallingConvention(const Function::Ptr&,
1950  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1951  const /*final*/;
1952 
1965  void
1966  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1967  const /*final*/;
1968 
1994  CallingConvention::Dictionary
1995  functionCallingConventionDefinitions(const Function::Ptr&,
1996  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1997  const /*final*/;
1998 
2011  void
2012  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
2013  CallingConvention::Definition::Ptr()) const /*final*/;
2014 
2023  void fixInterFunctionEdges() /*final*/;
2024  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2044  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2045 
2051  void allFunctionIsNoop() const /*final*/;
2052 
2060  void forgetFunctionIsNoop() const /*final*/;
2061  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2068  std::set<rose_addr_t> functionDataFlowConstants(const Function::Ptr&) const /*final*/;
2069 
2070 
2071 
2074  //
2075  // Callbacks
2076  //
2079 public:
2097  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2098  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2109  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2110  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2113 public:
2121  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2122  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2144  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2145 
2146 public:
2152  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2153  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2163  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2164 
2165 
2166 
2169  //
2170  // Partitioner miscellaneous
2171  //
2174 public:
2186  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2187  bool computeProperties=true) const /*final*/;
2188 
2202  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2203  bool showNeighbors=true) const /*final*/;
2204 
2210  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2211  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2217  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2218 
2224  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2225  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2233  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2234  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2242  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2243  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2249  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2250 
2254  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2255 
2259  static std::string functionName(const Function::Ptr&) /*final*/;
2260 
2278  Progress::Ptr progress() const /*final*/;
2279  void progress(const Progress::Ptr&) /*final*/;
2286  void updateProgress(const std::string &phase, double completion) const;
2287 
2289  void showStatistics() const;
2290 
2291  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2292  void checkConsistency() const;
2293 
2295  // Settings
2297 public:
2298 
2306  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2307  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2318  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2319  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2320  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2344  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2345  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2362  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2363  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2375  void addressName(rose_addr_t, const std::string&) /*final*/;
2376  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2377  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2387  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2388  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2392  //
2395  // Instruction semantics
2396  //
2399 public:
2409  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2410  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2419  SmtSolverPtr smtSolver() const /*final*/ { return solver_; }
2420 
2431  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2432  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2442  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2443 
2444 
2445 
2448  //
2449  // Python API support functions
2450  //
2453 #ifdef ROSE_ENABLE_PYTHON_API
2454  void pythonUnparse() const;
2455 #endif
2456 
2457 
2458 
2461  //
2462  // Partitioner internal utilities
2463  //
2466 private:
2467  void init(Disassembler*, const MemoryMap::Ptr&);
2468  void init(const Partitioner&);
2469  void updateCfgProgress();
2470 
2471 private:
2472  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2473  // and destination CFGs are identical.
2474  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2475  ControlFlowGraph::ConstVertexIterator otherIter);
2476 
2477  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2478  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2479  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2480 
2481  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2482  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2483  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2484 
2485  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2486  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2487 
2488  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2489  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2490  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2491 
2492  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2493  // The call happens immediately after the CFG/AUM are updated.
2494  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2495 
2496  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2497  void rebuildVertexIndices();
2498 
2499  // Attach a data block with ownership information to the AUM. This is private because it doesn't check that the owners
2500  // specified in the argument are actually already attached to the AUM. Returns an updated OwnedDataBlock record containing
2501  // the specified owners plus any owners that were already present in the AUM for an equivalent data block. The data block
2502  // pointed to by the return value is the one that's in the AUM, which might be other than the one that was specified in the
2503  // argument.
2504  OwnedDataBlock attachDataBlock(const OwnedDataBlock&);
2505 };
2506 
2507 } // namespace
2508 } // namespace
2509 } // namespace
2510 
2511 #endif
Represents information about a thunk.
Definition: Partitioner.h:301
size_t size() const
Number of addresses represented by the map.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:296
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2122
SmtSolverPtr smtSolver() const
SMT solver.
Definition: Partitioner.h:2419
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:302
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2121
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2376
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2319
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2388
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:589
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:465
Base class for machine instructions.
Sawyer::Optional< AddressUser > instructionExists(SgAsmInstruction *insn) const
Determines whether an instruction is attached to the CFG/AUM.
Definition: Partitioner.h:750
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2153
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:617
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:586
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:473
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:308
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2109
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:568
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2409
Name space for the entire library.
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:464
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2363
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:868
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:625
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2377
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:2307
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2362
bool instructionExists(SgAsmInstruction *) const
Determines whether an instruction exists in the map.
rose_addr_t target
The one and only successor for the basic block.
Definition: Partitioner.h:303
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:603
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:452
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2320
SemanticMemoryParadigm
Organization of semantic memory.
Definition: BasicTypes.h:80
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2110
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:934
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:1361
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:474
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:2344
bool basicBlockSemanticsAutoDrop() const
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:933
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:571
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:606
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:297
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2152
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2098
API and storage for attributes.
Definition: Attribute.h:208
Represents no value.
Definition: Optional.h:32
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:486
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:293
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2387
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:492
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:2318
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2345
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:295
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:298
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2410
Holds configuration information.
Definition: Config.h:210