ROSE  0.9.9.139
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/SharedPointer.h>
23 
24 #include <BinaryUnparser.h>
25 #include <Progress.h>
26 
27 #include <boost/serialization/access.hpp>
28 #include <boost/serialization/split_member.hpp>
29 
30 #include <ostream>
31 #include <set>
32 #include <string>
33 #include <vector>
34 
35 // Derived classes needed for serialization
36 #include <BinaryYicesSolver.h>
37 #include <BinaryZ3Solver.h>
38 #include <DispatcherM68k.h>
39 #include <DispatcherX86.h>
40 
41 namespace Rose {
42 namespace BinaryAnalysis {
43 
75 namespace Partitioner2 {
76 
290 class ROSE_DLL_API Partitioner: public Sawyer::Attribute::Storage<> { // final
291 public:
294  typedef std::vector<FunctionPrologueMatcher::Ptr> FunctionPrologueMatchers;
295  typedef std::vector<FunctionPaddingMatcher::Ptr> FunctionPaddingMatchers;
298  struct Thunk {
300  rose_addr_t target;
301  Thunk(const BasicBlock::Ptr &bblock, rose_addr_t target): bblock(bblock), target(target) {}
302  };
303 
306 
307 private:
308  BasePartitionerSettings settings_; // settings adjustable from the command-line
309  Configuration config_; // configuration information about functions, blocks, etc.
310  InstructionProvider::Ptr instructionProvider_; // cache for all disassembled instructions
311  MemoryMap::Ptr memoryMap_; // description of memory, especially insns and non-writable
312  ControlFlowGraph cfg_; // basic blocks that will become part of the ROSE AST
313  CfgVertexIndex vertexIndex_; // Vertex-by-address index for the CFG
314  AddressUsageMap aum_; // How addresses are used for each address represented by the CFG
315  SmtSolver *solver_; // Satisfiable modulo theory solver used by semantic expressions
316  Functions functions_; // List of all attached functions by entry address
317  bool autoAddCallReturnEdges_; // Add E_CALL_RETURN edges when blocks are attached to CFG?
318  bool assumeFunctionsReturn_; // Assume that unproven functions return to caller?
319  size_t stackDeltaInterproceduralLimit_; // Max depth of call stack when computing stack deltas
320  AddressNameMap addressNames_; // Names for various addresses
321  SemanticMemoryParadigm semanticMemoryParadigm_; // Slow and precise, or fast and imprecise?
322  Unparser::BasePtr unparser_; // For unparsing things to pseudo-assembly
323  Unparser::BasePtr insnUnparser_; // For unparsing single instructions in diagnostics
324 
325  // Callback lists
326  CfgAdjustmentCallbacks cfgAdjustmentCallbacks_;
327  BasicBlockCallbacks basicBlockCallbacks_;
328  FunctionPrologueMatchers functionPrologueMatchers_;
329  FunctionPaddingMatchers functionPaddingMatchers_;
330 
331  // Special CFG vertices.
332  ControlFlowGraph::VertexIterator undiscoveredVertex_;
333  ControlFlowGraph::VertexIterator indeterminateVertex_;
334  ControlFlowGraph::VertexIterator nonexistingVertex_;
335  static const size_t nSpecialVertices = 3;
336 
337  // Protects the following data members
338  mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
339  Progress::Ptr progress_; // Progress reporter to update, or null
340  mutable size_t cfgProgressTotal_; // Expected total for the CFG progress bar; initialized at first report
341 
342 
345  //
346  // Serialization
347  //
350 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
351 private:
352  friend class boost::serialization::access;
353 
354  template<class S>
355  void serializeCommon(S &s, const unsigned version) {
356  s.template register_type<InstructionSemantics2::SymbolicSemantics::SValue>();
357  s.template register_type<InstructionSemantics2::SymbolicSemantics::RiscOperators>();
358  s.template register_type<InstructionSemantics2::DispatcherX86>();
359  s.template register_type<InstructionSemantics2::DispatcherM68k>();
360  s.template register_type<SymbolicExpr::Interior>();
361  s.template register_type<SymbolicExpr::Leaf>();
362  s.template register_type<YicesSolver>();
363  s.template register_type<Z3Solver>();
364  s.template register_type<Semantics::SValue>();
365  s.template register_type<Semantics::MemoryListState>();
366  s.template register_type<Semantics::MemoryMapState>();
367  s.template register_type<Semantics::RegisterState>();
368  s.template register_type<Semantics::State>();
369  s.template register_type<Semantics::RiscOperators>();
370  s & BOOST_SERIALIZATION_NVP(settings_);
371  // s & config_; -- FIXME[Robb P Matzke 2016-11-08]
372  s & BOOST_SERIALIZATION_NVP(instructionProvider_);
373  s & BOOST_SERIALIZATION_NVP(memoryMap_);
374  s & BOOST_SERIALIZATION_NVP(cfg_);
375  // s & vertexIndex_; -- initialized by rebuildVertexIndices
376  s & BOOST_SERIALIZATION_NVP(aum_);
377  s & BOOST_SERIALIZATION_NVP(solver_);
378  s & BOOST_SERIALIZATION_NVP(functions_);
379  s & BOOST_SERIALIZATION_NVP(autoAddCallReturnEdges_);
380  s & BOOST_SERIALIZATION_NVP(assumeFunctionsReturn_);
381  s & BOOST_SERIALIZATION_NVP(stackDeltaInterproceduralLimit_);
382  s & BOOST_SERIALIZATION_NVP(addressNames_);
383  s & BOOST_SERIALIZATION_NVP(semanticMemoryParadigm_);
384  // s & unparser_; -- not saved; restored from disassembler
385  // s & cfgAdjustmentCallbacks_; -- not saved/restored
386  // s & basicBlockCallbacks_; -- not saved/restored
387  // s & functionPrologueMatchers_; -- not saved/restored
388  // s & functionPaddingMatchers_; -- not saved/restored
389  // s & undiscoveredVertex_; -- initialized by rebuildVertexIndices
390  // s & indeterminateVertex_; -- initialized by rebuildVertexIndices
391  // s & nonexistingVertex_; -- initialized by rebuildVertexIndices
392  // s & progress_; -- not saved/restored
393  // s & cfgProgressTotal_; -- not saved/restored
394  }
395 
396  template<class S>
397  void save(S &s, const unsigned version) const {
398  const_cast<Partitioner*>(this)->serializeCommon(s, version);
399  }
400 
401  template<class S>
402  void load(S &s, const unsigned version) {
403  serializeCommon(s, version);
404  rebuildVertexIndices();
405  }
406 
407  BOOST_SERIALIZATION_SPLIT_MEMBER();
408 #endif
409 
410 
413  //
414  // Constructors
415  //
418 public:
423  Partitioner();
424 
429  Partitioner(Disassembler *disassembler, const MemoryMap::Ptr &map);
430 
431  // FIXME[Robb P. Matzke 2014-11-08]: This is not ready for use yet. The problem is that because of the shallow copy, both
432  // partitioners are pointing to the same basic blocks, data blocks, and functions. This is okay by itself since these
433  // things are reference counted, but the paradigm of locked/unlocked blocks and functions breaks down somewhat -- does
434  // unlocking a basic block from one partitioner make it modifiable even though it's still locked in the other partitioner?
435  // FIXME[Robb P. Matzke 2014-12-27]: Not the most efficient implementation, but saves on cut-n-paste which would surely rot
436  // after a while.
437  Partitioner(const Partitioner &other);
438  Partitioner& operator=(const Partitioner &other);
439 
440  ~Partitioner();
441 
448  bool isDefaultConstructed() const { return instructionProvider_ == NULL; }
449 
451  void clear() /*final*/;
452 
460  Configuration& configuration() { return config_; }
461  const Configuration& configuration() const { return config_; }
469  InstructionProvider& instructionProvider() /*final*/ { return *instructionProvider_; }
470  const InstructionProvider& instructionProvider() const /*final*/ { return *instructionProvider_; }
482  MemoryMap::Ptr memoryMap() const /*final*/ { return memoryMap_; }
488  bool addressIsExecutable(rose_addr_t va) const /*final*/ {
489  return memoryMap_!=NULL && memoryMap_->at(va).require(MemoryMap::EXECUTABLE).exists();
490  }
491 
501  Unparser::BasePtr unparser() const /*final*/;
502  void unparser(const Unparser::BasePtr&) /*final*/;
514  Unparser::BasePtr insnUnparser() const /*final*/;
515  void insnUnparser(const Unparser::BasePtr&) /*final*/;
526  std::string unparse(SgAsmInstruction*) const;
527  void unparse(std::ostream&, SgAsmInstruction*) const;
528  void unparse(std::ostream&, const BasicBlock::Ptr&) const;
529  void unparse(std::ostream&, const DataBlock::Ptr&) const;
530  void unparse(std::ostream&, const Function::Ptr&) const;
531  void unparse(std::ostream&) const;
534  //
537  // Partitioner CFG queries
538  //
541 public:
547  size_t nBytes() const /*final*/ { return aum_.size(); }
548 
556  ControlFlowGraph::VertexIterator undiscoveredVertex() /*final*/ {
557  return undiscoveredVertex_;
558  }
559  ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const /*final*/ {
560  return undiscoveredVertex_;
561  }
574  ControlFlowGraph::VertexIterator indeterminateVertex() /*final*/ {
575  return indeterminateVertex_;
576  }
577  ControlFlowGraph::ConstVertexIterator indeterminateVertex() const /*final*/ {
578  return indeterminateVertex_;
579  }
591  ControlFlowGraph::VertexIterator nonexistingVertex() /*final*/ {
592  return nonexistingVertex_;
593  }
594  ControlFlowGraph::ConstVertexIterator nonexistingVertex() const /*final*/ {
595  return nonexistingVertex_;
596  }
605  const ControlFlowGraph& cfg() const /*final*/ { return cfg_; }
606 
613  const AddressUsageMap& aum() const /*final*/ { return aum_; }
614 
616  AddressUsageMap aum(const Function::Ptr&) const /*final*/;
617 
625  std::set<rose_addr_t> ghostSuccessors() const /*final*/;
626 
655  bool isEdgeIntraProcedural(ControlFlowGraph::ConstEdgeIterator edge,
656  const Function::Ptr &function = Function::Ptr()) const /*final*/;
657  bool isEdgeIntraProcedural(const ControlFlowGraph::Edge &edge,
658  const Function::Ptr &function = Function::Ptr()) const /*final*/;
695  bool isEdgeInterProcedural(ControlFlowGraph::ConstEdgeIterator edge,
696  const Function::Ptr &sourceFunction = Function::Ptr(),
697  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
698  bool isEdgeInterProcedural(const ControlFlowGraph::Edge &edge,
699  const Function::Ptr &sourceFunction = Function::Ptr(),
700  const Function::Ptr &targetFunction = Function::Ptr()) const /*final*/;
705  //
708  // Partitioner instruction operations
709  //
712 public:
718  size_t nInstructions() const /*final*/;
719 
729  Sawyer::Optional<AddressUser> instructionExists(rose_addr_t startVa) const /*final*/ {
730  return aum_.instructionExists(startVa);
731  }
733  return insn==NULL ? Sawyer::Nothing() : instructionExists(insn->get_address());
734  }
743  ControlFlowGraph::ConstVertexIterator instructionVertex(rose_addr_t insnVa) const;
744 
753  std::vector<SgAsmInstruction*> instructionsOverlapping(const AddressInterval&) const /*final*/;
754 
763  std::vector<SgAsmInstruction*> instructionsSpanning(const AddressInterval&) const /*final*/;
764 
774  std::vector<SgAsmInstruction*> instructionsContainedIn(const AddressInterval&) const /*final*/;
775 
783  AddressInterval instructionExtent(SgAsmInstruction*) const /*final*/;
784 
797  SgAsmInstruction* discoverInstruction(rose_addr_t startVa) const /*final*/;
798 
803  CrossReferences instructionCrossReferences(const AddressIntervalSet &restriction) const /*final*/;
804 
805 
808  //
809  // Partitioner basic block placeholder operations
810  //
813 public:
823  size_t nPlaceholders() const /*final*/;
824 
833  bool placeholderExists(rose_addr_t startVa) const /*final*/;
834 
845  ControlFlowGraph::VertexIterator findPlaceholder(rose_addr_t startVa) /*final*/ {
846  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
847  return *found;
848  return cfg_.vertices().end();
849  }
850  ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const /*final*/ {
851  if (Sawyer::Optional<ControlFlowGraph::VertexIterator> found = vertexIndex_.getOptional(startVa))
852  return *found;
853  return cfg_.vertices().end();
854  }
873  ControlFlowGraph::VertexIterator insertPlaceholder(rose_addr_t startVa) /*final*/;
874 
888  BasicBlock::Ptr erasePlaceholder(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
889  BasicBlock::Ptr erasePlaceholder(rose_addr_t startVa) /*final*/;
894  //
897  // Partitioner basic block operations
898  //
901 public:
915  bool basicBlockSemanticsAutoDrop() const /*final*/ { return settings_.basicBlockSemanticsAutoDrop; }
927  void basicBlockDropSemantics() const /*final*/;
928 
937  size_t nBasicBlocks() const /*final*/;
938 
946  std::vector<BasicBlock::Ptr> basicBlocks() const /*final*/;
947 
969  BasicBlock::Ptr basicBlockExists(rose_addr_t startVa) const /*final*/;
970  BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr&) const /*final*/;
982  std::vector<BasicBlock::Ptr> basicBlocksOverlapping(const AddressInterval&) const /*final*/;
983 
994  std::vector<BasicBlock::Ptr> basicBlocksSpanning(const AddressInterval&) const /*final*/;
995 
1005  std::vector<BasicBlock::Ptr> basicBlocksContainedIn(const AddressInterval&) const /*final*/;
1006 
1013  BasicBlock::Ptr basicBlockContainingInstruction(rose_addr_t insnVa) const /*final*/;
1014 
1024  AddressIntervalSet basicBlockInstructionExtent(const BasicBlock::Ptr&) const /*final*/;
1025 
1031  AddressIntervalSet basicBlockDataExtent(const BasicBlock::Ptr&) const /*final*/;
1032 
1057  BasicBlock::Ptr detachBasicBlock(rose_addr_t startVa) /*final*/;
1058  BasicBlock::Ptr detachBasicBlock(const BasicBlock::Ptr &basicBlock) /*final*/;
1059  BasicBlock::Ptr detachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) /*final*/;
1074  ControlFlowGraph::VertexIterator truncateBasicBlock(const ControlFlowGraph::ConstVertexIterator &basicBlock,
1075  SgAsmInstruction *insn) /*final*/;
1076 
1107  void attachBasicBlock(const BasicBlock::Ptr&) /*final*/;
1108  void attachBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder, const BasicBlock::Ptr&) /*final*/;
1196  BasicBlock::Ptr discoverBasicBlock(rose_addr_t startVa) const /*final*/;
1197  BasicBlock::Ptr discoverBasicBlock(const ControlFlowGraph::ConstVertexIterator &placeholder) const /*final*/;
1210  BasicBlock::Successors basicBlockSuccessors(const BasicBlock::Ptr&) const /*final*/;
1211 
1220  std::vector<rose_addr_t> basicBlockConcreteSuccessors(const BasicBlock::Ptr&, bool *isComplete=NULL) const /*final*/;
1221 
1240  std::set<rose_addr_t> basicBlockGhostSuccessors(const BasicBlock::Ptr&) const /*final*/;
1241 
1251  bool basicBlockIsFunctionCall(const BasicBlock::Ptr&) const /*final*/;
1252 
1263  bool basicBlockIsFunctionReturn(const BasicBlock::Ptr&) const /*final*/;
1264 
1304  BaseSemantics::SValuePtr basicBlockStackDeltaIn(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1305  BaseSemantics::SValuePtr basicBlockStackDeltaOut(const BasicBlock::Ptr&, const Function::Ptr &function) const /*final*/;
1316  void forgetStackDeltas() const /*final*/;
1317  void forgetStackDeltas(const Function::Ptr&) const /*final*/;
1329  size_t stackDeltaInterproceduralLimit() const /*final*/ { return stackDeltaInterproceduralLimit_; }
1330  void stackDeltaInterproceduralLimit(size_t n) /*final*/ { stackDeltaInterproceduralLimit_ = std::max(size_t(1), n); }
1383  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const BasicBlock::Ptr&) const /*final*/;
1384 
1385  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
1394  void basicBlockMayReturnReset() const /*final*/;
1395 
1396 private:
1397  // Per-vertex data used during may-return analysis
1398  struct MayReturnVertexInfo {
1399  enum State {INIT, CALCULATING, FINISHED};
1400  State state; // current state of vertex
1401  bool processedCallees; // have we processed BBs this vertex calls?
1402  boost::logic::tribool anyCalleesReturn; // do any of those called BBs have a true may-return value?
1403  boost::logic::tribool result; // final result (eventually cached in BB)
1404  MayReturnVertexInfo(): state(INIT), processedCallees(false), anyCalleesReturn(false), result(boost::indeterminate) {}
1405  };
1406 
1407  // Is edge significant for analysis? See .C file for full documentation.
1408  bool mayReturnIsSignificantEdge(const ControlFlowGraph::ConstEdgeIterator &edge,
1409  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1410 
1411  // Determine (and cache in vertexInfo) whether any callees return.
1412  boost::logic::tribool mayReturnDoesCalleeReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1413  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1414 
1415  // Maximum may-return result from significant successors including phantom call-return edge.
1416  boost::logic::tribool mayReturnDoesSuccessorReturn(const ControlFlowGraph::ConstVertexIterator &vertex,
1417  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1418 
1419  // The guts of the may-return analysis
1420  Sawyer::Optional<bool> basicBlockOptionalMayReturn(const ControlFlowGraph::ConstVertexIterator &start,
1421  std::vector<MayReturnVertexInfo> &vertexInfo) const;
1422 
1423 
1424 
1427  //
1428  // Partitioner data block operations
1429  //
1432 public:
1438  size_t nDataBlocks() const /*final*/;
1439 
1445  bool dataBlockExists(const DataBlock::Ptr&) const /*final*/;
1446 
1455  DataBlock::Ptr findBestDataBlock(const AddressInterval&) const /*final*/;
1456 
1465  void attachDataBlock(const DataBlock::Ptr&) /*final*/;
1466 
1473  DataBlock::Ptr detachDataBlock(const DataBlock::Ptr&) /*final*/;
1474 
1484  std::vector<DataBlock::Ptr> dataBlocksOverlapping(const AddressInterval&) const /*final*/;
1485 
1495  std::vector<DataBlock::Ptr> dataBlocksSpanning(const AddressInterval&) const /*final*/;
1496 
1506  std::vector<DataBlock::Ptr> dataBlocksContainedIn(const AddressInterval&) const /*final*/;
1507 
1514  AddressInterval dataBlockExtent(const DataBlock::Ptr&) const /*final*/;
1515 
1521  std::vector<DataBlock::Ptr> dataBlocks() const /*final*/;
1522 
1523 
1524 
1527  //
1528  // Partitioner function operations
1529  //
1532 public:
1538  size_t nFunctions() const /*final*/ { return functions_.size(); }
1539 
1558  Function::Ptr functionExists(rose_addr_t entryVa) const /*final*/;
1559  Function::Ptr functionExists(const BasicBlock::Ptr &entryBlock) const /*final*/;
1560  Function::Ptr functionExists(const Function::Ptr &function) const /*final*/;
1568  std::vector<Function::Ptr> functions() const /*final*/;
1569 
1579  std::vector<Function::Ptr> functionsOverlapping(const AddressInterval&) const /*final*/;
1580 
1591  std::vector<Function::Ptr> functionsSpanning(const AddressInterval&) const /*final*/;
1592 
1602  std::vector<Function::Ptr> functionsContainedIn(const AddressInterval&) const /*final*/;
1603 
1620  AddressIntervalSet functionExtent(const Function::Ptr&) const /*final*/;
1621  void functionExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1622  AddressIntervalSet functionBasicBlockExtent(const Function::Ptr &function) const /*final*/;
1623  void functionBasicBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1624  AddressIntervalSet functionDataBlockExtent(const Function::Ptr &function) const /*final*/;
1625  void functionDataBlockExtent(const Function::Ptr &function, AddressIntervalSet &retval /*in,out*/) const /*final*/;
1647  size_t attachFunction(const Function::Ptr&) /*final*/;
1648  size_t attachFunctions(const Functions&) /*final*/;
1664  Function::Ptr attachOrMergeFunction(const Function::Ptr&) /*final*/;
1665 
1682  size_t attachFunctionBasicBlocks(const Functions&) /*final*/;
1683  size_t attachFunctionBasicBlocks(const Function::Ptr&) /*final*/;
1699  void detachFunction(const Function::Ptr&) /*final*/;
1700 
1711  DataBlock::Ptr attachFunctionDataBlock(const Function::Ptr&, rose_addr_t startVa, size_t nBytes) /*final*/;
1712 
1718  void attachFunctionDataBlock(const Function::Ptr&, const DataBlock::Ptr&) /*final*/;
1719 
1754  std::vector<Function::Ptr>
1755  functionsOwningBasicBlock(const ControlFlowGraph::Vertex&, bool doSort = true) const /*final*/;
1756 
1757  std::vector<Function::Ptr>
1758  functionsOwningBasicBlock(const ControlFlowGraph::ConstVertexIterator&, bool doSort = true) const /*final*/;
1759 
1760  std::vector<Function::Ptr>
1761  functionsOwningBasicBlock(rose_addr_t bblockVa, bool doSort = true) const /*final*/;
1762 
1763  std::vector<Function::Ptr>
1764  functionsOwningBasicBlock(const BasicBlock::Ptr&, bool doSort = true) const /*final*/;
1765 
1766  template<class Container> // container can hold any type accepted by functionsOwningBasicBlock
1767  std::vector<Function::Ptr>
1768  functionsOwningBasicBlocks(const Container &bblocks) const /*final*/ {
1769  std::vector<Function::Ptr> retval;
1770  BOOST_FOREACH (const typename Container::value_type& bblock, bblocks) {
1771  BOOST_FOREACH (const Function::Ptr &function, functionsOwningBasicBlock(bblock, false))
1772  insertUnique(retval, function, sortFunctionsByAddress);
1773  }
1774  return retval;
1775  }
1787  std::vector<Function::Ptr> discoverCalledFunctions() const /*final*/;
1788 
1800  std::vector<Function::Ptr> discoverFunctionEntryVertices() const /*final*/;
1801 
1811  Sawyer::Optional<Thunk> functionIsThunk(const Function::Ptr&) const /*final*/;
1812 
1823  void discoverFunctionBasicBlocks(const Function::Ptr &function) const /*final*/;
1824 
1831  std::set<rose_addr_t> functionGhostSuccessors(const Function::Ptr&) const /*final*/;
1832 
1840  FunctionCallGraph functionCallGraph(bool allowParallelEdges = true) const /*final*/;
1841 
1861  BaseSemantics::SValuePtr functionStackDelta(const Function::Ptr &function) const /*final*/;
1862 
1866  void allFunctionStackDelta() const /*final*/;
1867 
1874  Sawyer::Optional<bool> functionOptionalMayReturn(const Function::Ptr &function) const /*final*/;
1875 
1879  void allFunctionMayReturn() const /*final*/;
1880 
1907  const CallingConvention::Analysis&
1908  functionCallingConvention(const Function::Ptr&,
1909  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1910  const /*final*/;
1911 
1924  void
1925  allFunctionCallingConvention(const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1926  const /*final*/;
1927 
1953  CallingConvention::Dictionary
1954  functionCallingConventionDefinitions(const Function::Ptr&,
1955  const CallingConvention::Definition::Ptr &dflt = CallingConvention::Definition::Ptr())
1956  const /*final*/;
1957 
1970  void
1971  allFunctionCallingConventionDefinition(const CallingConvention::Definition::Ptr &dflt =
1972  CallingConvention::Definition::Ptr()) const /*final*/;
1973 
1982  void fixInterFunctionEdges() /*final*/;
1983  void fixInterFunctionEdge(const ControlFlowGraph::ConstEdgeIterator&) /*final*/;
2003  bool functionIsNoop(const Function::Ptr&) const /*final*/;
2004 
2010  void allFunctionIsNoop() const /*final*/;
2011 
2019  void forgetFunctionIsNoop() const /*final*/;
2020  void forgetFunctionIsNoop(const Function::Ptr&) const /*final*/;
2025  //
2028  // Callbacks
2029  //
2032 public:
2050  CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() /*final*/ { return cfgAdjustmentCallbacks_; }
2051  const CfgAdjustmentCallbacks& cfgAdjustmentCallbacks() const /*final*/ { return cfgAdjustmentCallbacks_; }
2062  BasicBlockCallbacks& basicBlockCallbacks() /*final*/ { return basicBlockCallbacks_; }
2063  const BasicBlockCallbacks& basicBlockCallbacks() const /*final*/ { return basicBlockCallbacks_; }
2066 public:
2074  FunctionPrologueMatchers& functionPrologueMatchers() /*final*/ { return functionPrologueMatchers_; }
2075  const FunctionPrologueMatchers& functionPrologueMatchers() const /*final*/ { return functionPrologueMatchers_; }
2097  std::vector<Function::Ptr> nextFunctionPrologue(rose_addr_t startVa) /*final*/;
2098 
2099 public:
2105  FunctionPaddingMatchers& functionPaddingMatchers() /*final*/ { return functionPaddingMatchers_; }
2106  const FunctionPaddingMatchers& functionPaddingMatchers() const /*final*/ { return functionPaddingMatchers_; }
2116  DataBlock::Ptr matchFunctionPadding(const Function::Ptr&) /*final*/;
2117 
2118 
2119 
2122  //
2123  // Partitioner miscellaneous
2124  //
2127 public:
2139  void dumpCfg(std::ostream&, const std::string &prefix="", bool showBlocks=true,
2140  bool computeProperties=true) const /*final*/;
2141 
2155  void cfgGraphViz(std::ostream&, const AddressInterval &restrict = AddressInterval::whole(),
2156  bool showNeighbors=true) const /*final*/;
2157 
2163  static std::string vertexName(const ControlFlowGraph::Vertex&) /*final*/;
2164  std::string vertexName(const ControlFlowGraph::ConstVertexIterator&) const /*final*/;
2170  static std::string vertexNameEnd(const ControlFlowGraph::Vertex&) /*final*/;
2171 
2177  static std::string edgeNameSrc(const ControlFlowGraph::Edge&) /*final*/;
2178  std::string edgeNameSrc(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2186  static std::string edgeNameDst(const ControlFlowGraph::Edge&) /*final*/;
2187  std::string edgeNameDst(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2195  static std::string edgeName(const ControlFlowGraph::Edge&) /*final*/;
2196  std::string edgeName(const ControlFlowGraph::ConstEdgeIterator&) const /*final*/;
2202  static std::string basicBlockName(const BasicBlock::Ptr&) /*final*/;
2203 
2207  static std::string dataBlockName(const DataBlock::Ptr&) /*final*/;
2208 
2212  static std::string functionName(const Function::Ptr&) /*final*/;
2213 
2221  const BasePartitionerSettings& settings() const /*final*/ { return settings_; }
2222  void settings(const BasePartitionerSettings &s) /*final*/ { settings_ = s; }
2242  Progress::Ptr progress() const /*final*/;
2243  void progress(const Progress::Ptr&) /*final*/;
2250  void updateProgress(const std::string &phase, double completion) const;
2251 
2260  void enableSymbolicSemantics(bool b=true) /*final*/ { settings_.usingSemantics = b; }
2261  void disableSymbolicSemantics() /*final*/ { settings_.usingSemantics = false; }
2262  bool usingSymbolicSemantics() const /*final*/ { return settings_.usingSemantics; }
2286  void autoAddCallReturnEdges(bool b) /*final*/ { autoAddCallReturnEdges_ = b; }
2287  bool autoAddCallReturnEdges() const /*final*/ { return autoAddCallReturnEdges_; }
2304  void assumeFunctionsReturn(bool b) /*final*/ { assumeFunctionsReturn_ = b; }
2305  bool assumeFunctionsReturn() const /*final*/ { return assumeFunctionsReturn_; }
2317  void addressName(rose_addr_t, const std::string&) /*final*/;
2318  const std::string& addressName(rose_addr_t va) const /*final*/ { return addressNames_.getOrDefault(va); }
2319  const AddressNameMap& addressNames() const /*final*/ { return addressNames_; }
2329  bool checkingCallBranch() const /*final*/ { return settings_.checkingCallBranch; }
2330  void checkingCallBranch(bool b) /*final*/ { settings_.checkingCallBranch = b; }
2334  //
2337  // Instruction semantics
2338  //
2341 public:
2351  SemanticMemoryParadigm semanticMemoryParadigm() const { return semanticMemoryParadigm_; }
2352  void semanticMemoryParadigm(SemanticMemoryParadigm p) { semanticMemoryParadigm_ = p; }
2361  SmtSolver *smtSolver() const /*final*/ { return solver_; }
2362 
2373  BaseSemantics::RiscOperatorsPtr newOperators() const /*final*/;
2374  BaseSemantics::RiscOperatorsPtr newOperators(SemanticMemoryParadigm) const /*final*/;
2384  BaseSemantics::DispatcherPtr newDispatcher(const BaseSemantics::RiscOperatorsPtr&) const /*final*/;
2385 
2386 
2387 
2388 
2391  //
2392  // Partitioner internal utilities
2393  //
2396 private:
2397  void init(Disassembler*, const MemoryMap::Ptr&);
2398  void init(const Partitioner&);
2399  void updateCfgProgress();
2400 
2401 private:
2402  // Convert a CFG vertex iterator from one partitioner to another. This is called during copy construction when the source
2403  // and destination CFGs are identical.
2404  ControlFlowGraph::VertexIterator convertFrom(const Partitioner &other,
2405  ControlFlowGraph::ConstVertexIterator otherIter);
2406 
2407  // Adjusts edges for a placeholder vertex. This method erases all outgoing edges for the specified placeholder vertex and
2408  // then inserts a single edge from the placeholder to the special "undiscovered" vertex. */
2409  ControlFlowGraph::EdgeIterator adjustPlaceholderEdges(const ControlFlowGraph::VertexIterator &placeholder);
2410 
2411  // Adjusts edges for a non-existing basic block. This method erases all outgoing edges for the specified vertex and
2412  // then inserts a single edge from the vertex to the special "non-existing" vertex. */
2413  ControlFlowGraph::EdgeIterator adjustNonexistingEdges(const ControlFlowGraph::VertexIterator &vertex);
2414 
2415  // Implementation for the discoverBasicBlock methods. The startVa must not be the address of an existing placeholder.
2416  BasicBlock::Ptr discoverBasicBlockInternal(rose_addr_t startVa) const;
2417 
2418  // Checks consistency of internal data structures when debugging is enable (when NDEBUG is not defined).
2419  void checkConsistency() const;
2420 
2421  // This method is called whenever a new placeholder is inserted into the CFG or a new basic block is attached to the
2422  // CFG/AUM. The call happens immediately after the CFG/AUM are updated.
2423  void bblockAttached(const ControlFlowGraph::VertexIterator &newVertex);
2424 
2425  // This method is called whenever a basic block is detached from the CFG/AUM or when a placeholder is erased from the CFG.
2426  // The call happens immediately after the CFG/AUM are updated.
2427  void bblockDetached(rose_addr_t startVa, const BasicBlock::Ptr &removedBlock);
2428 
2429  // Rebuild the vertexIndex_ and other cache-like data members from the control flow graph
2430  void rebuildVertexIndices();
2431 };
2432 
2433 } // namespace
2434 } // namespace
2435 } // namespace
2436 
2437 #endif
Represents information about a thunk.
Definition: Partitioner.h:298
size_t size() const
Number of addresses represented by the map.
Sawyer::Callbacks< BasicBlockCallback::Ptr > BasicBlockCallbacks
See basicBlockCallbacks.
Definition: Partitioner.h:293
const FunctionPrologueMatchers & functionPrologueMatchers() const
Ordered list of function prologue matchers.
Definition: Partitioner.h:2075
SmtSolver * smtSolver() const
SMT solver.
Definition: Partitioner.h:2361
BasicBlock::Ptr bblock
The one and only basic block for the thunk.
Definition: Partitioner.h:299
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:486
FunctionPrologueMatchers & functionPrologueMatchers()
Ordered list of function prologue matchers.
Definition: Partitioner.h:2074
const std::string & addressName(rose_addr_t va) const
Property: Name for address.
Definition: Partitioner.h:2318
void disableSymbolicSemantics()
Use or not use symbolic semantics.
Definition: Partitioner.h:2261
void checkingCallBranch(bool b)
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2330
ControlFlowGraph::ConstVertexIterator indeterminateVertex() const
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:577
const Configuration & configuration() const
Configuration information.
Definition: Partitioner.h:461
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:732
const FunctionPaddingMatchers & functionPaddingMatchers() const
Ordered list of function padding matchers.
Definition: Partitioner.h:2106
const ControlFlowGraph & cfg() const
Returns the control flow graph.
Definition: Partitioner.h:605
Provides and caches instructions.
Settings that directly control a partitioner.
Definition: BasicTypes.h:239
STL namespace.
Holds a value or nothing.
Definition: Optional.h:49
ControlFlowGraph::VertexIterator indeterminateVertex()
Returns the special "indeterminate" vertex.
Definition: Partitioner.h:574
InstructionProvider & instructionProvider()
Returns the instruction provider.
Definition: Partitioner.h:469
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1454
Main namespace for the ROSE library.
Bidirectional vertex node iterator.
Definition: Graph.h:1036
Sawyer::Container::Map< rose_addr_t, std::string > AddressNameMap
Map address to name.
Definition: Partitioner.h:305
BasicBlockCallbacks & basicBlockCallbacks()
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2062
ControlFlowGraph::VertexIterator undiscoveredVertex()
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:556
SemanticMemoryParadigm semanticMemoryParadigm() const
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2351
Name space for the entire library.
Definition: Access.h:11
Configuration & configuration()
Configuration information.
Definition: Partitioner.h:460
bool assumeFunctionsReturn() const
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2305
ControlFlowGraph::ConstVertexIterator findPlaceholder(rose_addr_t startVa) const
Find the CFG vertex for a basic block placeholder.
Definition: Partitioner.h:850
const AddressUsageMap & aum() const
Returns the address usage map.
Definition: Partitioner.h:613
const AddressNameMap & addressNames() const
Property: Name for address.
Definition: Partitioner.h:2319
Base classes for instruction semantics.
void settings(const BasePartitionerSettings &s)
Partitioner settings.
Definition: Partitioner.h:2222
void assumeFunctionsReturn(bool b)
Property: Assume (or not) that function calls return.
Definition: Partitioner.h:2304
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:300
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:591
bool isDefaultConstructed() const
Return true if this is a default constructed partitioner.
Definition: Partitioner.h:448
bool usingSymbolicSemantics() const
Use or not use symbolic semantics.
Definition: Partitioner.h:2262
SemanticMemoryParadigm
Organization of semantic memory.
Definition: BasicTypes.h:60
An efficient mapping from an address space to stored data.
Definition: MemoryMap.h:96
const BasicBlockCallbacks & basicBlockCallbacks() const
Callbacks for adjusting basic block during discovery.
Definition: Partitioner.h:2063
void basicBlockSemanticsAutoDrop(bool b)
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:916
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:513
void stackDeltaInterproceduralLimit(size_t n)
Property: max depth for inter-procedural stack delta analysis.
Definition: Partitioner.h:1330
const InstructionProvider & instructionProvider() const
Returns the instruction provider.
Definition: Partitioner.h:470
bool checkingCallBranch
Check for situations where CALL is used as a branch.
Definition: BasicTypes.h:244
bool usingSemantics
Whether instruction semantics are used.
Definition: BasicTypes.h:240
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:2286
bool basicBlockSemanticsAutoDrop() const
Property: Automatically drop semantics for attached basic blocks.
Definition: Partitioner.h:915
bool basicBlockSemanticsAutoDrop
Conserve memory by dropping semantics for attached basic blocks.
Definition: BasicTypes.h:245
ControlFlowGraph::ConstVertexIterator undiscoveredVertex() const
Returns the special "undiscovered" vertex.
Definition: Partitioner.h:559
ControlFlowGraph::ConstVertexIterator nonexistingVertex() const
Returns the special "non-existing" vertex.
Definition: Partitioner.h:594
std::vector< FunctionPrologueMatcher::Ptr > FunctionPrologueMatchers
See functionPrologueMatchers.
Definition: Partitioner.h:294
FunctionPaddingMatchers & functionPaddingMatchers()
Ordered list of function padding matchers.
Definition: Partitioner.h:2105
const CfgAdjustmentCallbacks & cfgAdjustmentCallbacks() const
List of all callbacks invoked when the CFG is adjusted.
Definition: Partitioner.h:2051
API and storage for attributes.
Definition: Attribute.h:208
Interface to Satisfiability Modulo Theory (SMT) solvers.
Represents no value.
Definition: Optional.h:32
MemoryMap::Ptr memoryMap() const
Returns the memory map.
Definition: Partitioner.h:482
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
bool checkingCallBranch() const
Property: Whether to look for function calls used as branches.
Definition: Partitioner.h:2329
bool addressIsExecutable(rose_addr_t va) const
Returns true if address is executable.
Definition: Partitioner.h:488
Virtual base class for instruction disassemblers.
Definition: Disassembler.h:41
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:322
bool autoAddCallReturnEdges() const
Property: Insert (or not) function call return edges.
Definition: Partitioner.h:2287
Sawyer::Callbacks< CfgAdjustmentCallback::Ptr > CfgAdjustmentCallbacks
See cfgAdjustmentCallbacks.
Definition: Partitioner.h:292
std::vector< FunctionPaddingMatcher::Ptr > FunctionPaddingMatchers
See functionPaddingMatchers.
Definition: Partitioner.h:295
void semanticMemoryParadigm(SemanticMemoryParadigm p)
Property: Whether to use map- or list-based memory states.
Definition: Partitioner.h:2352
Holds configuration information.
Definition: Config.h:210